「計算複雑性理論」の版間の差分

'''計算複雑性理論'''（けいさんふくざつせいりろん、{{lang|Lang-en-short|computational complexity theory}}）とは、[[計算機科学]]における[[計算理論]]の一分野であり、[[アルゴリズム]]の[[スケーラビリティ]]や、特定の計算問題の解法の[[複雑性]]（計算問題の困難さ）などを数学的に扱う。'''計算量理論'''、'''計算の複雑さの理論'''、'''計算複雑度の理論'''ともいう。

計算複雑性理論では、計算問題やそれを解くアルゴリズムを、'''NP'''や'''P'''といった複雑性クラスに分類する。個々の計算問題を少ない計算資源で解くアルゴリズムを発見することはもちろん計算機科学の重要な課題だが、複雑性理論ではこれにとどまらず、計算問題が何らかの複雑性クラスに属すること、あるいは属しないことを証明したり、クラス間の階層構造を解明することも目標とする。

現在の計算複雑性理論の最も重要な課題は、[[P≠NP予想]]の証明である。この予想は提起された当初それほど重要とは見なされなかったが、産業において重要な[[オペレーションズリサーチ]]の問題の多くが '''[[NP]]'''の部分クラスに属する[[NP完全問題]]であることが明らかになるにつれて重要性を増してきた。NP完全問題は、解法が正しいかどうかは簡単に確かめられるが、正確な解を探す方法はスケーラブルではない問題である。'''NP'''クラスが'''P'''クラスより範囲が広いことが確定すると、それらの問題にはスケーラブルな解が存在しないことが確定する。このため、P≠NP予想の証明は重要とされているのである。

[[アルゴリズム]]の'''計算量'''（けいさんりょう）とは、[[計算機]]がそのアルゴリズムの実行に要する計算資源の量をいい、アルゴリズムの[[スケーラビリティ]]を示す。形式的には計算機を[[チューリング機械]]や[[即時呼出ランダムアクセス機械]]（{{lang|en|random access machine}}）などの[[計算模型|計算モデル]]として定式化したうえで、アルゴリズムの使用する資源の量を入力データ長などに対する[[関数 (数学)|関数]]として表す。計算モデルの瑣末な詳細に影響を受けないよう、計算量はその漸近的な挙動のみに注目し、定数倍を無視する[[ランダウの記号|O記法]]で書き表すことが多い。計算モデルとしては、[[チューリング機械]]や[[論理回路]]などがある。計算資源の量としては、チューリング機械における'''時間計算量'''（動作ステップ数）や'''空間計算量'''（テープ長）、また論理回路における素子数や深さなどがある。

ある問題の解を求める計算量とその補問題の解を求める計算量は同じであるが、問題のあるインスタンスについて「はい」となる証拠を与えられて、その証拠が正しいかを判定する計算量は同じとは限らない。例えば、''IS-COMPOSITE''問題で、ある整数について、証拠として素因子を一つ与えられれば、除算を行うことで検算することができる。しかし、''IS-PRIME''問題では、どのような証拠を与えればよいかは、しばらくの間、自明ではなかった。補問題を区別することは、後述する複雑性クラス'''[[NP]]'''と'''[[co-NP]]'''などで重要となる。

複雑性クラス [[P (計算複雑性理論)|'''P''']] は、[[チューリング機械]]で[[多項式時間]]で解ける決定問題の集合である。このクラスは、直感的に言えば最悪の場合でも効率的に解くことができる問題である<ref name="Sipser2006">{{cite book|last=Sipser|first=Michael|title=Introduction to the Theory of Computation|edition=2nd edition|chapter=Time Complexity|date=2006年|publisher=Thomson Course Technology|location=USA|id=ISBN 0-534-95097-3}}</ref>。

各クラスに対し、そのクラスの'''完全問題'''を考えることがある。クラス''C''の完全問題とは''C''に属する問題のうちで最も計算するのが難しい問題のことである。具体的な定義は以下のようになる。

; —困難 (—hard{{lang-en-short|— hard}})

; —完全 (—complete{{lang-en-short|— complete}})

* [[NP]] （[[NP困難]], [[NP完全]]）

'''NP'''が'''P'''と同じかどうかという疑問（換言すれば、非決定的な多項式時間で解くことのできる問題は決定的な多項式時間でも解くことができるか）は、理論計算機科学における最重要問題の1つであり、その解決が様々な意味を持っている<ref name="Sipser2006"/>。同じであった場合に都合が悪い影響として、[[暗号理論]]の多くが'''NP'''の困難さに依存しているため、'''P'''と同じであることが判明すると使い物にならなくなるのである。しかし、よい影響も多々あり、様々な重要な問題に効率的な解法があることが明らかとなることが重要である。例えば、[[オペレーションズリサーチ]]における[[整数計画問題]]、物流合理化、[[生物学]]における[[タンパク質構造予測]]、[[純粋数学]]の定理を[[計算機]]で効率的に形式的に証明する可能性などがある<ref>{{cite journal|title=Protein folding in the hydrophobic-hydrophilic (HP) model is NP-complete.|last=Berger|first=Bonnie A.|coauthors=Leighton, Terrance|journal=Journal of Computational Biology|date=1998年|volume=5|number=1|pages=p27-40}}、[http://www.ncbi.nlm.nih.gov/entrez/query.fcgi?cmd=Retrieve&db=pubmed&dopt=Abstract&list_uids=9541869&query_hl=14&itool=pubmed_docsum PubMed]</ref><ref>{{cite journal|last=Cook|first=Stephen|authorlink=スティーブン・クック|title=The P versus NP Problem|publisher=[[クレイ数学研究所]]|date=2000年|month=April4月|url=http://www.claymath.org/millennium/P_vs_NP/Official_Problem_Description.pdf|accessdate=2006-10-18|format=PDF}}</ref>。[[クレイ数学研究所]]は[[2000年]]に、この問題を最初に解いた人に100万ドルを支払うと発表した<ref>{{cite journal|title=The Millennium Grand Challenge in Mathematics|last=Jaffe|first=Arthur M.|journal=Notices of the AMS|volume=53|issue=6|url=http://www.ams.org/notices/200606/fea-jaffe.pdf|accessdate=2006-10-18|format=PDF}}</ref>。

この問題を考えるにあたって重要となるのは、[[NP完全問題|'''NP'''完全]]の概念である。'''NP'''完全な問題は'''NP'''の中では最も'''P'''から遠い問題ということになる。'''P'''<nowiki> = </nowiki>'''NP'''が証明されていないため、ある問題を'''NP'''完全と判明している問題に[[還元 (計算複雑性理論)|還元]]できるということは、その問題の多項式時間の解法が未知であることを示している。逆に、すべての '''NP'''問題は'''NP'''完全問題に還元できるため、'''NP'''完全問題の多項式時間の解法を発見すれば、'''P'''<nowiki> = </nowiki>'''NP'''が証明される<ref name="Sipser2006"/>。（一方、たとえ'''P'''<nowiki> = </nowiki>'''NP'''が成立しても、[[NP困難|'''NP'''困難]]な問題は多項式時間で解けるとは限らない。理由はNP困難のページを参照のこと）

上の問題に関連して、'''NP'''クラスに属する問題で'''P'''クラスには属しないが'''NP'''完全でもない問題は存在するか、という問題もある。つまり、非決定的な多項式時間の解法はあるが、'''NP'''完全問題から多項式時間で還元できない問題ということである。このような問題のクラスを{{仮リンク|NP-intermediate|en|NP-intermediate}}と呼び、候補として[[同型グラフ|グラフ同型問題]]や[[素因数分解|整数の因数分解]]、[[離散対数問題]]などがある。もし'''P'''<nowiki> ≠ </nowiki>'''NP'''が真ならば、そのような問題が存在することが証明されている<ref name="DuKo2000">{{cite book|last=Du|first=Ding-Zhu|coauthors=Ko, Ker-I|title=Theory of Computational Complexity|publisher=John Wiley & Sons|date=2000年|country=USA|id=ISBN 978-0-471-34506-0}}</ref>。

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

理論上計算可能な問題であっても、実際に解くことができない問題を'''イントラクタブル'''<ref> ({{lang-en-short|intractable}}、, 手に負えない、処理しにくい。</ref>) であるという。「実際に」解けるとはどういうことかという問題もあるが、多項式時間の解法がある問題が一般に（小さな入力だけでなく）解けるとされている。イントラクタブルな問題として知られているものとしては、'''[[EXPTIME]]'''完全な問題がある。'''NP''' が '''P''' と同じでなかった場合、'''NP'''完全な問題もイントラクタブルだということになる。

[[指数関数時間]]の解法がなぜ実際には使えないかを考えるため、2<mathsup>2^''n''</mathsup> 回の操作を必要とする問題を考える（<math>''n</math>'' は入力のサイズである）。比較的小さな入力数 <math>''n'' = 100</math> のときについて、1秒間に 10<mathsup>10^{10}</mathsup> （10 [[ギガ]]）回命令を実行できる計算機を想定すると、その問題を解くには約 <math>4\ &times{}; 10^{<sup>12}</mathsup> 年かかる。これは現在の[[宇宙#宇宙の年齢・大きさ|宇宙の年齢]]よりも長い。

* [[マヌエル・ブラム]]: [[ブラムの公理]]に基づいた公理的複雑性理論を構築した

* [[:en:{{ill2|Leonid Levin|en|Leonid Levin]]}}

* L. Fortnow, Steve Homer (2002/2003). {{PDFlink|[http://people.cs.uchicago.edu/~fortnow/papers/history.pdf A Short History of Computational Complexity]}}. In D. van Dalen, J. Dawson, and A. Kanamori, editors, ''The History of Mathematical Logic''. North-Holland, Amsterdam.

* [https://complexityzoo.uwaterloo.ca/Complexity_Zoo The Complexity Zoo] - 複雑性理論に関する[[Wiki]]