計算複雑性理論
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2023/04/28 16:32 UTC 版)
計算資源
計算複雑性理論は計算問題の難しさを様々な計算資源の観点で分析する。時間、空間、無作為性、反復性、その他のより直観的でない尺度などで必要とする計算資源量によって、同じ問題を説明する。複雑性クラスはある特定の計算資源をある特定の量つかって解くことができる全計算問題の集合である。
最も研究が進んでいる計算資源は決定性時間(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完全問題から多項式時間で還元できない問題ということである。このような問題のクラスをNP-intermediateと呼び、候補としてグラフ同型問題や整数の因数分解、離散対数問題などがある。もしP ≠ NPが真ならば、そのような問題が存在することが証明されている[5]。
NP = co-NP
co-NPクラスはNP問題の補問題の集合である（すなわち、「はい」と「いいえ」が逆転している問題）。両者は等しくないと考えられているが証明されていない。2つの複雑性クラスが等しくないことが判明すると、NP完全問題は co-NP には含まれず、co-NP完全問題は NP には含まれないことが明らかになる[5]。
- ^ a b c d Sipser, Michael (2006年). “Time Complexity”. Introduction to the Theory of Computation (2nd edition ed.). USA: Thomson Course Technology. ISBN 0-534-95097-3
- ^ Berger, Bonnie A.; Leighton, Terrance (1998年). “Protein folding in the hydrophobic-hydrophilic (HP) model is NP-complete.”. Journal of Computational Biology 5 (1): p27-40.、PubMed
- ^ Cook, Stephen (2000年4月) (PDF). The P versus NP Problem. クレイ数学研究所 2006年10月18日閲覧。.
- ^ Jaffe, Arthur M.. “The Millennium Grand Challenge in Mathematics” (PDF). Notices of the AMS 53 (6) 2006年10月18日閲覧。.
- ^ a b Du, Ding-Zhu; Ko, Ker-I (2000年). Theory of Computational Complexity. John Wiley & Sons. ISBN 978-0-471-34506-0
固有名詞の分類
- 計算複雑性理論のページへのリンク
