「計算複雑性理論」の版間の差分
削除された内容 追加された内容
Sillycrown (会話 | 投稿記録) |
|||
(20人の利用者による、間の28版が非表示) | |||
1行目:
'''計算複雑性理論'''(けいさんふくざつせいりろん、{{
{{注|「計算量」と「計算複雑性」はともに {{lang|en|computational complexity}} に対応する語であるが、個々のアルゴリズムの効率に着目する文脈では「計算量」が広く用いられるのに対し、問題に内在する本質的困難さを表す意識からは「複雑性」「複雑さ」が好まれる傾向がある。}}
8行目:
具体的には、計算複雑性理論は「あるアルゴリズムへの入力データの長さを増やしたとき、実行時間や必要な記憶量はどのように増えるか?」という問いに答える。これは、[[計算機]]の実際的な限界を与えるものであり、この理論は産業や社会にとって重要な意味を持つ。なぜならば、計算機の性能は向上しているが、解析すべき情報も増加しているため、アルゴリズムが入力データ長の増大にうまく対応できるか否かで、計算機が現実的な問題を解決するのに役に立つか否かが決まるからである。
計算複雑性理論では、計算問題やそれを解くアルゴリズムを、
計算量 t<sub>C</sub> をもつ複雑性クラス C に 或る計算問題 X が属する とは、あるアルゴリズム A が存在して、問題 X が A により t<sub>C</sub>以下で解決されることを意味し、問題 X の複雑性の上界を与える。そして、よりよい上界を求めることは、問題 X をより少ない計算資源で解くアルゴリズムを発見する(あるいはその存在を示す)ことに他ならず、産業界において有意義である。また、ある計算問題 X が、ある複雑性クラス C に属しないとは、問題 X は、いかなるアルゴリズムをもってしても、計算量 t<sub>C</sub> 以下では解決できないことを意味し、問題 X の複雑性の下界を与える。計算問題の下界を示すことは、理論的意義を有するだけではなくて、[[暗号理論]]においては、ある暗号方式が計算量的に解読不能であることを示すことを意味し、実際的な価値がある。
現在の計算複雑性理論の最も重要な課題は、[[P≠NP予想]]の証明である。この予想は提起された当初それほど重要とは見なされなかったが、産業において重要な[[オペレーションズリサーチ]]の問題の多くが
== 計算問題と計算量・複雑性 ==
計算複雑性理論で扱う'''問題'''とは、ある一連の問いの集合があり、各問いは有限長の[[文字列]]で表され、与えられた問いに対して解を求めて出力する計算問題である。例えば、[[素因数分解|''FACTORIZE'']]問題とは「[[二進記数法|二進数]]で書かれた1つの整数について、その[[素数|素因数]]を全部求めて返す」という問題である。問題に属する個別の問いを'''インスタンス'''と呼ぶ。例えば、「15 の素因数を求めよ」は ''FACTORIZE'' 問題のインスタンスである。
[[アルゴリズム]]の'''計算量'''(けいさんりょう)とは、[[計算機]]がそのアルゴリズムの実行に要する計算資源の量をいい、アルゴリズムの[[スケーラビリティ]]を示す。形式的には計算機を[[チューリング機械]]や[[
* '''時間計算量'''は、あるアルゴリズムを使ったときに問題のインスタンスを解くのに要するステップ数を意味し、入力データの長さ(ビット数などで表現できる)の関数として表される。シンプルな例として、ある問題に対する解法が ''n''ビットの入力に対して、ある計算モデルで ''n''<sup>2</sup> ステップで動作する場合、時間計算量は ''n''<sup>2</sup> であるが、他のほとんどの計算モデルでも、時間計算量は漸近的には定数倍の違いしかなく、[[ランダウの記号|O記法]]を使えば計算モデルによらず問題の時間計算量をO(''n''<sup>2</sup>) と表せる。計算を芝生を刈る作業にたとえれば、その時間計算量は線型であり、芝生の面積が2倍になれば時間も2倍かかる。この面積が2倍になれば時間も2倍になるという関係は、芝刈機の速度には関係しない。しかし、辞書を[[二分探索]]する場合の時間計算量は対数時間であり、辞書の厚さが2倍になっても、二分探索のステップが1増加するだけである。
* '''空間計算量'''は、同様の概念であり、アルゴリズムが必要とする記憶容量を意味する。例えば、紙とペンを使って計算を行う際に要する紙の枚数に相当する。空間計算量にも[[ランダウの記号|O記法]]が使われる。
36 ⟶ 35行目:
例えば、決定問題 ''IS-PRIME''([[素数判定|素数判定問題]])は、入力が[[素数]]の場合に「はい」、そうでなければ「いいえ」を返す。一方、問題 ''IS-COMPOSITE'' は与えられた整数が素数で'''ない'''(すなわち[[合成数]]である)ことを決定する。''IS-PRIME'' が「はい」を返すなら、''IS-COMPOSITE'' は「いいえ」を返す。逆も成り立つ。したがって ''IS-COMPOSITE'' は ''IS-PRIME'' の補問題であり、同様に ''IS-PRIME'' は ''IS-COMPOSITE'' の補問題である。
ある問題の解を求める計算量とその補問題の解を求める計算量は同じであるが、問題のあるインスタンスについて「はい」となる証拠を与えられて、その証拠が正しいかを判定する計算量は同じとは限らない。例えば、''IS-COMPOSITE''問題で、ある整数について、証拠として素因子を一つ与えられれば、除算を行うことで検算することができる。しかし、''IS-PRIME''問題では、どのような証拠を与えればよいかは、しばらくの間、自明ではなかった。補問題を区別することは、後述する複雑性クラス
計算複雑性理論の重要な成果の1つとして、ある難しい問題があったとき(それがいかに大量の時間資源や空間資源を要したとしても)、それよりさらに難しい問題が必ず存在するという事実がある。時間計算量については{{仮リンク|時間階層定理|en|Time hierarchy theorem}}によってこれが証明されている。同様に{{仮リンク|領域階層定理|en|Space hierarchy theorem}}も導かれる。
52 ⟶ 51行目:
ある量の計算資源を使って解くことができるすべての計算問題の集合を[[複雑性クラス]]という。
複雑性クラス [[P (計算複雑性理論)|
複雑性クラス
多くの複雑性クラスは、それを表現するのに必要となる[[形式体系|論理体系]]によって特徴付けられる。これは、[[記述計算量]]の概念と関係がある。
各クラスに対し、そのクラスの'''完全問題'''を考えることがある。クラス''C''の完全問題とは''C''に属する問題のうちで最も計算するのが難しい問題のことである。具体的な定義は以下のようになる。
; —困難 ({{lang-en-short|— hard}})
; —完全 ({{lang-en-short|— complete}})
:クラス''C''に対して、問題''P''が''C'''''完全'''であるとは、''P''が''C''に属しかつ''C''困難ということである。すなわち''P''は''C''に属する問題の中で、本質的に最も難しい問題であるということである。
=== 主な複雑性クラス ===
* [[L (計算複雑性理論)|
* [[NL (計算複雑性理論)|
* [[NC (計算複雑性理論)|
* [[P (計算複雑性理論)|
* [[NP
* [[co-NP
* [[PSPACE
* [[EXPTIME
* [[BPP (計算複雑性理論)|
* [[BQP
== 未解決の問題 ==
81 ⟶ 80行目:
{{Main|P≠NP予想}}
この問題を考えるにあたって重要となるのは、[[NP完全問題|
=== NPにおける不完全問題 ===
上の問題に関連して、
=== NP<nowiki> = </nowiki>co-NP ===
'''[[co-NP]]'''クラスは
==イントラクタブル==
{{see also|組合せ爆発}}
理論上計算可能な問題であっても、実際に解くことができない問題を
[[指数関数時間]]の解法がなぜ実際には使えないかを考えるため、2<sup>''n''</sup> 回の操作を必要とする問題を考える
== 主な研究者 ==
* [[マヌエル・ブラム]]: [[ブラムの公理]]に基づいた公理的複雑性理論を構築した
* [[スティーブン・クック]]
* [[ユリス・ハルトマニス]]
106 ⟶ 105行目:
* [[アンドリュー・チーチー・ヤオ]]
* [[レスリー・ヴァリアント]]
*
== 脚注 ==
{{脚注ヘルプ}}
{{reflist}}
== 参考文献 ==▼
* 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.▼
* 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. 解説が豊富で、様々な文献で引用・参照されている。▼
* Dexter C. Kozen: "Theory of Computation", Springer, ISBN 978-1849965712(2010年10月21日).
== 関連項目 ==
* [[P≠NP
* [[多項式時間]]
* [[加速定理]]
* [[理論計算機科学]]
* [[還元 (計算複雑性理論)
▲== 参考文献 ==
▲* L. Fortnow, Steve Homer (2002/2003). [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.
▲* 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. 解説が豊富で、様々な文献で引用・参照されている。
== 外部リンク ==
* [https://complexityzoo.uwaterloo.ca/Complexity_Zoo The Complexity Zoo] - 複雑性理論に関する[[Wiki]]
* [http://www.cs.princeton.edu/theory/complexity/ Free (at least for now) book on computational complexity]
{{Computer-stub}}
{{authority control}}
{{
[[Category:計算複雑性理論|*]]
[[Category:理論計算機科学]]
[[Category:計算理論]]
[[Category:組合せ最適化]]
[[Category:研究の計算分野]]
[[Category:数学に関する記事]]
|