計算複雑性理論

計算複雑性理論（けいさんふくざつせいりろん、computational complexity theory）とは、計算機科学における計算理論の一分野であり、アルゴリズムのスケーラビリティや、特定の計算問題の解法の複雑性（計算問題の困難さ）などを数学的に扱う。計算量理論、計算の複雑さの理論、計算複雑度の理論ともいう。
「計算量」と「計算複雑性」はともに computational complexity に対応する語であるが、個々のアルゴリズムの効率に着目する文脈では「計算量」が広く用いられるのに対し、問題に内在する本質的困難さを表す意識からは「複雑性」「複雑さ」が好まれる傾向がある。

概要

計算複雑性理論は計算可能関数の計算の複雑さを扱う。計算理論のもう一つの重要な分野である計算可能性理論では問題の解法があるかどうかだけを扱い、その複雑さや必要とする計算資源量は問わない点が異なる。
具体的には、計算複雑性理論は「あるアルゴリズムへの入力データの長さを増やしたとき、実行時間や必要な記憶量はどのように増えるか？」という問いに答える。これは、計算機の実際的な限界を与えるものであり、この理論は産業や社会にとって重要な意味を持つ。なぜならば、計算機の性能は向上しているが、解析すべき情報も増加しているため、アルゴリズムが入力データ長の増大にうまく対応できるか否かで、計算機が現実的な問題を解決するのに役に立つか否かが決まるからである。
計算複雑性理論では、計算問題やそれを解くアルゴリズムを、NPやPといった複雑性クラスに分類する。個々の計算問題を少ない計算資源で解くアルゴリズムを発見することはもちろん計算機科学の重要な課題だが、複雑性理論ではこれにとどまらず、計算問題が何らかの複雑性クラスに属すること、あるいは属しないことを証明したり、クラス間の階層構造を解明することも目標とする。
計算量 tC をもつ複雑性クラス C に 或る計算問題 X が属する とは、あるアルゴリズム A が存在して、問題 X が A により tC以下で解決されることを意味し、問題 X の複雑性の上界を与える。そして、よりよい上界を求めることは、問題 X をより少ない計算資源で解くアルゴリズムを発見する(あるいはその存在を示す)ことに他ならず、産業界において有意義である。また、ある計算問題 X が、ある複雑性クラス C に属しないとは、問題 X は、いかなるアルゴリズムをもってしても、計算量 tC 以下では解決できないことを意味し、問題 X の複雑性の下界を与える。計算問題の下界を示すことは、理論的意義を有するだけではなくて、暗号理論においては、ある暗号方式が計算量的に解読不能であることを示すことを意味し、実際的な価値がある。
現在の計算複雑性理論の最も重要な課題は、P≠NP予想の証明である。この予想は提起された当初それほど重要とは見なされなかったが、産業において重要なオペレーションズリサーチの問題の多くがNPの部分クラスに属するNP完全問題であることが明らかになるにつれて重要性を増してきた。NP完全問題は、解が正しいかどうかは簡単に確かめられるが、正確な解を探す方法はスケーラブルではない問題である。NPクラスがPクラスより範囲が広いことが確定すると、それらの問題にはスケーラブルな解が存在しないことが確定する。このため、P≠NP予想の証明は重要とされているのである。

決定問題

計算複雑性理論で扱う計算問題の多くは決定問題である。決定問題とは、答えが「はい」か「いいえ」になる問題を指す。
決定問題を主に扱うのは、任意の計算問題を何らかの決定問題に還元することが常に可能だからである。例えば、HAS-FACTOR を与えられた整数 n と k（どちらも二進数で与えるとする）について、n が k より小さい素因数をもつかどうかに答える決定問題とする。すると、計算問題 FACTORIZE（素因数分解）の解法は、HAS-FACTOR を使って実現でき、その際に追加の資源はそれほど要しない。具体的には k について二分探索を行い、n の最小素因数を探索し、その値で n を割る。そして、商について再び同じ作業を繰り返していけばよい。このことは、HAS-FACTOR の解法をある計算資源量で実現できるか否かが分れば、FACTORIZE の解法についても分るということを意味する。
計算複雑性理論では、答えが「はい」かどうかを確認する問題と、答えが「いいえ」かどうかを確認する問題を区別する。「はい」と「いいえ」を逆転させた問題は、元の問題の補問題と呼ばれる。
例えば、決定問題 IS-PRIME（素数判定問題）は、入力が素数の場合に「はい」、そうでなければ「いいえ」を返す。一方、問題 IS-COMPOSITE は与えられた整数が素数でない（すなわち合成数である）ことを決定する。IS-PRIME が「はい」を返すなら、IS-COMPOSITE は「いいえ」を返す。逆も成り立つ。したがって IS-COMPOSITE は IS-PRIME の補問題であり、同様に IS-PRIME は IS-COMPOSITE の補問題である。
ある問題の解を求める計算量とその補問題の解を求める計算量は同じであるが、問題のあるインスタンスについて「はい」となる証拠を与えられて、その証拠が正しいかを判定する計算量は同じとは限らない。例えば、IS-COMPOSITE問題で、ある整数について、証拠として素因子を一つ与えられれば、除算を行うことで検算することができる。しかし、IS-PRIME問題では、どのような証拠を与えればよいかは、しばらくの間、自明ではなかった。補問題を区別することは、後述する複雑性クラスNPとco-NPなどで重要となる。
計算複雑性理論の重要な成果の1つとして、ある難しい問題があったとき（それがいかに大量の時間資源や空間資源を要したとしても）、それよりさらに難しい問題が必ず存在するという事実がある。時間計算量については時間階層定理によってこれが証明されている。同様に領域階層定理も導かれる。

計算資源

計算複雑性理論は計算問題の難しさを様々な計算資源の観点で分析する。時間、空間、無作為性、反復性、その他のより直観的でない尺度などで必要とする計算資源量によって、同じ問題を説明する。複雑性クラスはある特定の計算資源をある特定の量つかって解くことができる全計算問題の集合である。
最も研究が進んでいる計算資源は決定性時間(DTIME) と決定性空間(DSPACE) である。これらの資源はそれぞれ、決定性のある計算機（例えば実在する普通の計算機）で問題を解くのに必要な「計算時間（演算回数）」と「記憶装置」の量に対応している。これらの資源の使用量を求めることは実用的な意味もあり、研究が進んでいるのである。
いくつかの計算問題は非現実的な量の資源を想定すれば、より容易に解析可能である。例えば、非決定性チューリング機械は、分岐して様々な可能性を同時にチェックできるという計算モデルである。したがって、非決定性チューリング機械はアルゴリズムを使って具体的に計算する作業とは全く関係ないが、その分岐によって分析したい計算モデルの大部分を捉える。このため非決定性時間は計算問題を分析するにあたって非常に重要な資源である。
計算複雑性理論では他にもいろいろな計算資源を考慮する。技術的には、複雑性尺度として計算資源量が扱われ、これに関してはブラムの公理で非常に一般的な定義が与えられている。

P = NP 問題

NPがPと同じかどうかという疑問（換言すれば、非決定的な多項式時間で解くことのできる問題は決定的な多項式時間でも解くことができるか）は、理論計算機科学における最重要問題の1つであり、その解決が様々な意味を持っている。同じであった場合に都合が悪い影響として、暗号理論の多くがNPの困難さに依存しているため、Pと同じであることが判明すると使い物にならなくなるのである。しかし、よい影響も多々あり、様々な重要な問題に効率的な解法があることが明らかとなることが重要である。例えば、オペレーションズリサーチにおける整数計画問題、物流合理化、生物学におけるタンパク質構造予測、純粋数学の定理を計算機で効率的に形式的に証明する可能性などがある。クレイ数学研究所は2000年に、この問題を最初に解いた人に100万ドルを支払うと発表した。
この問題を考えるにあたって重要となるのは、NP完全の概念である。NP完全な問題はNPの中では最もPから遠い問題ということになる。P = NPが証明されていないため、ある問題をNP完全と判明している問題に還元できるということは、その問題の多項式時間の解法が未知であることを示している。逆に、すべての NP問題はNP完全問題に還元できるため、NP完全問題の多項式時間の解法を発見すれば、P = NPが証明される。（一方、たとえP = NPが成立しても、NP困難な問題は多項式時間で解けるとは限らない。理由はNP困難のページを参照のこと）

NPにおける不完全問題

上の問題に関連して、NPクラスに属する問題でPクラスには属しないがNP完全でもない問題は存在するか、という問題もある。つまり、非決定的な多項式時間の解法はあるが、NP完全問題から多項式時間で還元できない問題ということである。このような問題のクラスをNP-intermediateと呼び、候補としてグラフ同型問題や整数の因数分解、離散対数問題などがある。もしP ≠ NPが真ならば、そのような問題が存在することが証明されている。

NP = co-NP

co-NPクラスはNP問題の補問題の集合である（すなわち、「はい」と「いいえ」が逆転している問題）。両者は等しくないと考えられているが証明されていない。2つの複雑性クラスが等しくないことが判明すると、NP完全問題は co-NP には含まれず、co-NP完全問題は NP には含まれないことが明らかになる。

イントラクタブル

理論上計算可能な問題であっても、実際に解くことができない問題をイントラクタブル (英: intractable, 手に負えない、処理しにくい) であるという。「実際に」解けるとはどういうことかという問題もあるが、多項式時間の解法がある問題が一般に（小さな入力だけでなく）解けるとされている。イントラクタブルな問題として知られているものとしては、EXPTIME完全な問題がある。NP が P と同じでなかった場合、NP完全な問題もイントラクタブルだということになる。
指数関数時間の解法がなぜ実際には使えないかを考えるため、2ⁿ 回の操作を必要とする問題を考える（n は入力のサイズである）。比較的小さな入力数 n = 100 のときについて、1秒間に 10¹⁰（10 ギガ）回命令を実行できる計算機を想定すると、その問題を解くには約 4 × 10¹² 年かかる。これは現在の宇宙の年齢よりも長い。