計算複雑性理論
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2023/04/28 16:32 UTC 版)
イントラクタブル
「組合せ爆発」も参照
理論上計算可能な問題であっても、実際に解くことができない問題をイントラクタブル (英: intractable, 手に負えない、処理しにくい) であるという。「実際に」解けるとはどういうことかという問題もあるが、多項式時間の解法がある問題が一般に（小さな入力だけでなく）解けるとされている。イントラクタブルな問題として知られているものとしては、EXPTIME完全な問題がある。NP が P と同じでなかった場合、NP完全な問題もイントラクタブルだということになる。
指数関数時間の解法がなぜ実際には使えないかを考えるため、2n 回の操作を必要とする問題を考える（n は入力のサイズである）。比較的小さな入力数 n = 100 のときについて、1秒間に 1010（10 ギガ）回命令を実行できる計算機を想定すると、その問題を解くには約 4 × 1012 年かかる。これは現在の宇宙の年齢よりも長い。
主な研究者
- マヌエル・ブラム: ブラムの公理に基づいた公理的複雑性理論を構築した
- スティーブン・クック
- ユリス・ハルトマニス
- リチャード・カープ
- アディ・シャミア
- リチャード・スターンズ
- アンドリュー・チーチー・ヤオ
- レスリー・ヴァリアント
- Leonid Levin
脚注
参考文献
- L. Fortnow, Steve Homer (2002/2003). A Short History of Computational Complexity (PDF) . 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日）.
関連項目
- ^ 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
「計算複雑性理論」の続きの解説一覧
- 計算複雑性理論のページへのリンク
