計算複雑性理論
計算複雑性理論（けいさんふくざつせいりろん、computational complexity theory）とは、計算機科学における計算理論の一分野であり、アルゴリズムのスケーラビリティや、特定の計算問題の解法の複雑性（計算問題の困難さ）などを数学的に扱う。計算量理論、計算の複雑さの理論、計算複雑度の理論ともいう。
目次
概要
計算複雑性理論は計算可能関数の計算の複雑さを扱う。計算理論のもう一つの重要な分野である計算可能性理論では問題の解法があるかどうかだけを扱い、その複雑さや必要とする計算資源量は問わない点が異なる。
具体的には、計算複雑性理論は「あるアルゴリズムへの入力データの長さを増やしたとき、実行時間や必要な記憶量はどのように増えるか？」という問いに答える。これは、計算機の実際的な限界を与えるものであり、この理論は産業や社会にとって重要な意味を持つ。なぜならば、計算機の性能は向上しているが、解析すべき情報も増加しているため、アルゴリズムが入力データ長の増大にうまく対応できるか否かで、計算機が現実的な問題を解決するのに役に立つか否かが決まるからである。
計算複雑性理論では、計算問題やそれを解くアルゴリズムを、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予想の証明は重要とされているのである。
計算問題と計算量・複雑性
計算複雑性理論で扱う問題とは、ある一連の問いの集合があり、各問いは有限長の文字列で表され、与えられた問いに対して解を求めて出力する計算問題である。例えば、FACTORIZE問題とは「二進数で書かれた1つの整数について、その素因数を全部求めて返す」という問題である。問題に属する個別の問いをインスタンスと呼ぶ。例えば、「15 の素因数を求めよ」は FACTORIZE 問題のインスタンスである。
アルゴリズムの計算量（けいさんりょう）とは、計算機がそのアルゴリズムの実行に要する計算資源の量をいい、アルゴリズムのスケーラビリティを示す。形式的には計算機をチューリング機械や即時呼出機械（random access machine）などの計算モデルとして定式化したうえで、アルゴリズムの使用する資源の量を入力データ長などに対する関数として表す。計算モデルの瑣末な詳細に影響を受けないよう、計算量はその漸近的な挙動のみに注目し、定数倍を無視するO記法で書き表すことが多い。計算モデルとしては、チューリング機械や論理回路などがある。計算資源の量としては、チューリング機械における時間計算量（動作ステップ数）や空間計算量（テープ長）、また論理回路における素子数や深さなどがある。
- 時間計算量は、あるアルゴリズムを使ったときに問題のインスタンスを解くのに要するステップ数を意味し、入力データの長さ（ビット数などで表現できる）の関数として表される。シンプルな例として、ある問題に対する解法が nビットの入力に対して、ある計算モデルで n2 ステップで動作する場合、時間計算量は n2 であるが、他のほとんどの計算モデルでも、時間計算量は漸近的には定数倍の違いしかなく、O記法を使えば計算モデルによらず問題の時間計算量をO(n2) と表せる。計算を芝生を刈る作業にたとえれば、その時間計算量は線型であり、芝生の面積が2倍になれば時間も2倍かかる。この面積が2倍になれば時間も2倍になるという関係は、芝刈機の速度には関係しない。しかし、辞書を二分探索する場合の時間計算量は対数時間であり、辞書の厚さが2倍になっても、二分探索のステップが1増加するだけである。
- 空間計算量は、同様の概念であり、アルゴリズムが必要とする記憶容量を意味する。例えば、紙とペンを使って計算を行う際に要する紙の枚数に相当する。空間計算量にもO記法が使われる。
計算モデルによっては、これらとは異なる計算量が使われることもあり、例えば回路計算量がある。これは問題の解法をブール論理による論理回路ゲートに置き換え、その回路の規模で計算量を現すものである。これは集積回路の設計などで利用される。
計算問題の複雑性（または計算量）とは、それがどの計算モデルにおいて、どれほどの計算量のアルゴリズムによって解けるかで測られる。直感的には、問題の計算量は、最も効率のよいアルゴリズムを使ったときに問題のインスタンスを解くのに要する計算量だと考えるのが自然である。しかし、最良のアルゴリズムであることを示すのは通常困難で、多くの場合、O記法を用いて「ある時間以下で計算できる」ことを示すことになる。そのため、複雑性クラスを導入し、クラス間の相互関係を示すことで、計算問題の複雑性を明らかにする。
決定問題
計算複雑性理論で扱う計算問題の多くは決定問題である。決定問題とは、答えが「はい」か「いいえ」になる問題を指す。
決定問題を主に扱うのは、任意の計算問題を何らかの決定問題に還元することが常に可能だからである。例えば、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 は、チューリング機械で多項式時間で解ける決定問題の集合である。このクラスは、直感的に言えば最悪の場合でも効率的に解くことができる問題である[1]。
複雑性クラス NP は、非決定性チューリング機械で多項式時間で解ける決定問題の集合である。このクラスには効率的に解くことが望ましいとされる様々な問題が含まれている。例えば、充足可能性問題、ハミルトン閉路問題、頂点被覆問題などである。このクラスの全問題は、その解法を効率的に検証する方法があるという特徴を持つ[1]。
多くの複雑性クラスは、それを表現するのに必要となる数理論理学によって特徴付けられる。これは、記述計算量の概念と関係がある。
各クラスに対し、そのクラスの完全問題を考えることがある。 クラスCの完全問題とはCに属する問題のうちで最も計算するのが難しい問題のことである。 具体的な定義は以下のようになる。
- —困難 (—hard)
- クラスCに対して、問題PがC困難であるとは、Cに属する任意の問題をPに帰着（多くの場合多項式時間帰着を考えるが、そうでない場合もある）できるということである。すなわちPはCに属するいかなる問題よりも、同等かそれ以上に難しいということである。ただし、C完全と異なり、P自身はCに属するとは限らない。
- —完全 (—complete)
- クラスCに対して、問題PがC完全であるとは、PがCに属しかつC困難ということである。すなわちPはCに属する問題の中で、本質的に最も難しい問題であるということである。
主な複雑性クラス
未解決の問題
P = NP 問題
NPがPと同じかどうかという疑問（換言すれば、非決定的な多項式時間で解くことのできる問題は決定的な多項式時間でも解くことができるか）は、理論計算機科学における最重要問題の1つであり、その解決が様々な意味を持っている[1]。同じであった場合に都合が悪い影響として、暗号理論の多くがNPの困難さに依存しているため、Pと同じであることが判明すると使い物にならなくなるのである。しかし、よい影響も多々あり、様々な重要な問題に効率的な解法があることが明らかとなることが重要である。例えば、オペレーションズリサーチにおける整数計画問題、物流合理化、生物学におけるタンパク質構造予測、純粋数学の定理を計算機で効率的に形式的に証明する可能性などがある[2][3]。クレイ数学研究所は2000年に、この問題を最初に解いた人に100万ドルを支払うと発表した[4]。
この問題を考えるにあたって重要となるのは、NP完全の概念である。NP完全な問題はNPの中では最もPから遠い問題ということになる。P = NPが証明されていないため、ある問題をNP完全と判明している問題に還元できるということは、その問題の多項式時間の解法が未知であることを示している。逆に、すべての NP問題はNP完全問題に還元できるため、NP完全問題の多項式時間の解法を発見すれば、P = NPが証明される[1]。（一方、例えP = NPが成立しても、NP困難な問題は多項式時間で解けるとは限らない。理由はNP困難のページを参照のこと）
NPにおける不完全問題
上の問題に関連して、NPクラスに属する問題でPクラスには属しないがNP完全でもない問題は存在するか、という問題もある。つまり、非決定的な多項式時間の解法はあるが、多項式時間に還元できない問題ということである。そのような問題でNP完全かどうかが不明な問題として、グラフ同型問題がある。P ≠ NPであることが示されれば、そのような問題が存在することが確定する[5]。
NP = co-NP
co-NPクラスはNP問題の補問題の集合である（すなわち、「はい」と「いいえ」が逆転している問題）。両者は等しくないと考えられているが証明されていない。2つの複雑性クラスが等しくないことが判明すると、NP完全問題は co-NP には含まれず、co-NP完全問題は NP には含まれないことが明らかになる[5]。
Intractability
テンプレート:See also 理論上計算可能な問題であっても、実際に解くことができない問題を intractable（手に負えない、処理しにくい） であるという。「実際に」解けるとはどういうことかという問題もあるが、多項式時間の解法がある問題が一般に（小さな入力だけでなく）解けるとされている。intractable な問題として知られているものとしては、EXPTIME完全な問題がある。NP が P と同じでなかった場合、NP完全な問題も intractable だということになる。
指数関数時間の解法がなぜ実際には使えないかを考えるため、2n 回の操作を必要とする問題を考える（n は入力のサイズである）。比較的小さな入力数 n = 100 のときについて、1秒間に 1010 （10 ギガ）回命令を実行できる計算機を想定すると、その問題を解くには約 4*1012 年かかる。これは現在の宇宙の年齢よりも長い。
主な研究者
- マヌエル・ブラム ブラムの公理に基づいた公理的複雑性理論を構築した
- スティーブン・クック
- ユリス・ハルトマニス
- リチャード・カープ
- アディ・シャミア
- リチャード・スターンズ
- アンドリュー・チーチー・ヤオ
- レスリー・ヴァリアント
- Leonid Levin
脚注
関連項目
参考文献
- L. Fortnow, Steve Homer (2002/2003). A Short History of Computational Complexity. In D. van Dalen, J. Dawson, and A. Kanamori, editors, The History of Mathematical Logic. North-Holland, Amsterdam.
- Jan van Leeuwen, ed. Handbook of Theoretical Computer Science, Volume A: Algorithms and Complexity, The MIT Press/Elsevier, 1990. ISBN 978-0-444-88071-0 (Volume A). QA 76.H279 1990. 解説が豊富で、様々な文献で引用・参照されている。
外部リンク
