計算複雑性理論

計算複雑性理論とは、計算機科学における計算理論の一分野であり、アルゴリズムの効率性や、特定の計算問題の解法の複雑さ（計算問題の困難さ）を数学的に研究する学問です。計算量理論、計算の複雑さの理論、計算複雑度の理論などとも呼ばれています。

概要

計算複雑性理論の中心的なテーマは、計算問題を解くためのアルゴリズムが、入力データのサイズが増加した際に、計算時間やメモリ使用量などの計算資源をどのように消費するかを分析することです。これは、アルゴリズムのスケーラビリティを評価することに他なりません。計算機の性能向上は著しいものの、扱うデータ量も同様に増加しており、アルゴリズムがデータサイズの増大に適切に対応できるかどうかが、現実の問題解決に重要な意味を持ちます。

計算複雑性理論では、計算問題やアルゴリズムを、P、NPなどの複雑性クラスに分類することで、問題の複雑さを体系的に理解しようとします。個々の問題に対する効率的なアルゴリズムの発見も重要ですが、複雑性理論ではさらに、問題がどの複雑性クラスに属するかを証明したり、複雑性クラス間の関係性を解明することも重要な目標です。

ある計算問題が特定の複雑性クラスに属するとは、その問題をある計算量内で解くアルゴリズムが存在することを意味し、問題の複雑さの上界を示します。より少ない計算資源で解くアルゴリズムを発見することは、産業においても大きな意義を持ちます。逆に、ある計算問題が特定の複雑性クラスに属しないことを証明できれば、その問題の下界を示すことになり、暗号理論などでも重要な意味を持ちます。

現在、計算複雑性理論における最も重要な未解決問題は、P≠NP予想です。これは、簡単に解の正しさは検証できるが、解を見つけるのが難しい問題（NP完全問題）が、効率的に解けるかどうかという問題です。もしP=NPならば、多くの現実世界の重要な問題に効率的な解法が存在することになります。しかし、P≠NPであることが証明されれば、それらの問題には本質的に効率的な解法が存在しないことが示唆されます。

計算問題と計算量・複雑性

計算複雑性理論が扱う計算問題は、有限長の文字列で表現される問いと、その問いに対する解を出力する処理の組み合わせです。例えば、「与えられた整数の素因数を求める」という問題は、FACTORIZE問題として定式化できます。各々の問いはインスタンスと呼ばれ、「15の素因数を求めよ」などはFACTORIZE問題のインスタンスです。

アルゴリズムの計算量は、アルゴリズムの実行に必要な計算資源の量を表し、アルゴリズムの効率性を示す指標となります。計算機をチューリング機械やランダムアクセス機械などの計算モデルとして抽象化し、計算資源量を入力データ長に対する関数として表します。計算モデルの細かい違いの影響を受けないように、計算量の漸近的な挙動（O記法）に注目することが一般的です。計算資源としては、時間計算量（実行ステップ数）、空間計算量（メモリ使用量）、回路計算量などがあります。

時間計算量は、アルゴリズムが問題のインスタンスを解くのに必要なステップ数を、入力データ長nの関数として表したものです。例えば、n²ステップで動作するアルゴリズムの時間計算量はO(n²)です。空間計算量は、アルゴリズムに必要なメモリ容量を表します。計算モデルによっては、論理回路の規模で計算量を表す回路計算量も用いられます。

計算問題の複雑性は、それを解くための最も効率的なアルゴリズムの計算量で測られます。しかし、最良のアルゴリズムを見つけるのは困難なため、通常は上界を示す形で複雑性を記述します。複雑性クラスを導入し、クラス間の関係性を調べることで、計算問題の複雑性を明らかにします。

決定問題

計算複雑性理論では、答えが「はい」か「いいえ」の2値のみをとる決定問題を多く扱います。これは、任意の計算問題を何らかの決定問題に帰着できるためです。例えば、素因数分解問題（FACTORIZE）は、ある整数にkより小さい素因数があるかどうかを判定する決定問題（HAS-FACTOR）を用いて解くことができます。

決定問題では、「はい」と「いいえ」を逆転させた補問題も考えます。ある問題とその補問題の計算量は同じとは限りません。例えば、ある整数が合成数であることを示す証拠（素因子）は簡単に検証できますが、素数であることを示す証拠は簡単には検証できません。この違いは、複雑性クラスNPとco-NPの定義で重要となります。

時間計算量や空間計算量に関して、「ある問題より難しい問題が必ず存在する」ということが、時間階層定理や領域階層定理によって証明されています。

計算資源

計算複雑性理論では、時間、空間、無作為性など様々な計算資源を考慮して計算問題の難しさを分析します。複雑性クラスは、特定の計算資源を特定の量だけ使用して解けるすべての計算問題の集合です。

最も研究されている資源は、決定性時間(DTIME)と決定性空間(DSPACE)で、通常の計算機の時間とメモリに対応します。非決定性チューリング機械のような、様々な可能性を同時に探索できる計算モデルも用いられ、非決定性時間も重要な資源となります。複雑性尺度としては、ブラムの公理に基づく一般的な定義が与えられています。

複雑性クラス

複雑性クラスは、特定の計算資源量で解ける全ての計算問題の集合です。代表的な複雑性クラスとして、P（多項式時間で解ける決定問題の集合）、NP（非決定性多項式時間で解ける決定問題の集合）などがあります。NPクラスには、効率的な解法が望まれる多くの問題が含まれています。

複雑性クラスでは、完全問題という概念が重要です。クラスCの完全問題は、Cに属する問題の中で最も難しい問題であり、Cに属する任意の問題が多項式時間でこの問題に帰着できます。

主要な複雑性クラス

L, NL, NC, P, NP（NP困難, NP完全）, co-NP, PSPACE, EXPTIME, BPP, BQP など

未解決の問題

P = NP 問題

P=NP問題は、計算複雑性理論における最重要問題の一つです。NP問題がPと等しいかどうか（非決定性多項式時間で解ける問題は、決定性多項式時間でも解けるか）という問いは、暗号理論や様々な応用分野に大きな影響を与えます。この問題の解決には、クレイ数学研究所から100万ドルの賞金が懸けられています。

NP完全問題はNPの中で最もPから遠い問題です。P≠NPが証明されていないため、ある問題がNP完全問題に帰着できることは、その問題が多項式時間で解けるかどうかが不明であることを意味します。逆に、全てのNP問題がNP完全問題に帰着できるため、NP完全問題の多項式時間アルゴリズムを発見できればP=NPが証明されます。しかし、P=NPであっても、NP困難な問題全てが多項式時間で解けるとは限りません。

NPにおける不完全問題

NPクラスに属する問題で、Pクラスには属さないがNP完全でもない問題は存在するのかという問題も未解決です。このような問題のクラスをNP-intermediateと呼び、グラフ同型問題などが候補として挙げられています。P≠NPならば、NP-intermediateな問題が存在することが証明されています。

NP = co-NP

co-NPクラスはNP問題の補問題の集合です。NP=co-NPかどうかは未解決です。

イントラクタブル

理論上計算可能であっても、実際には解くことができない問題をイントラクタブルといいます。多項式時間アルゴリズムを持たない問題は、入力サイズが大きくなると現実的な時間で解くことが不可能になります。EXPTIME完全な問題などは、イントラクタブルな問題として知られています。P≠NPならば、NP完全問題もイントラクタブルになります。

主な研究者

マヌエル・ブラム、スティーブン・クック、ユリス・ハルトマニス、リチャード・カープ、アディ・シャミア、リチャード・スターンズ、アンドリュー・チーチー・ヤオ、レスリー・ヴァリアント、Leonid Levinなど

もう一度検索