P≠NP予想
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2024/03/09 14:32 UTC 版)
重要性
他の問題との関係
- NP完全
- 1971年にスティーブン・クックが定式化した概念で、クラスNPに属し、クラスNPに属する他の全問題が多項式時間帰着される問題をNP完全という。充足可能性問題をはじめとして、数千個以上の問題がNP完全であることが示されている。これらのNP完全問題の一つでもクラスPに属することを示せれば、P＝NPとなる。
- NP完全には含まれない問題
- NP-(P∪NP完全)となる問題のクラスをNPIとする。P≠NPであれば、NPIは空集合ではないことが示されている。そのような問題の候補としてグラフ同型問題がある。
- coNP
- NP問題の補問題からなるクラスをcoNPという。NP≠coNPならば、P≠NPとなることが示されている。
参考文献
- Mulmuley, Ketan D.; Sohoni, Milind (2001), “Geometric Complexity Theory I: An Approach to the P vs. NP and Related Problems”, SIAM J. Compput. 31 (2): 496-526 2017年6月10日閲覧。
- Stephen Cook, "The P versus NP Problem", 2000. [1] (PDF)
- Michael Sipser, Introduction to the Theory of Computation, PWS Publishing Company, 1997. ISBN 0-534-94728-X. pp.372-377. (渡辺治・太田和夫 監訳, 『計算理論の基礎』, 共立出版社, 2000. ISBN 4-320-02948-8. pp.436-444)
- Aaronson, Scott; Wigderson, Avi (2009), “Algebrization: A New Barrier in Complexity Theory”, ACM Transactions on Computation Theory(TOCT) 1 (1) 2017年6月10日閲覧。
- Vinodchandran, N.V. (2005), “A Note on the Circuit Complexity of PP”, Theoretical Computer Science 347 (1-2): 415-418 2017年6月10日閲覧。
- Buhrman, Harry; Fortnow, Lance; Thierauf, Thomas (1998), Nonrelativizing Separations 2017年6月10日閲覧。
- Razborov, Alexander A. (1985), “Lower bounds for the monotone complexity of some boolean functions”, Soviet Math. Dokl. 31 (2) 2017年6月10日閲覧。
- Furst, Merrick; Saxe, James B.; Sipser, Michael (1984), “Parity, Circuits, and the Polynomial-Time Hierarchy” (PDF), Math. Systems Theory 17: 13-27 2017年6月10日閲覧。
- Hartmanis, Juris; Stearns, Richard E. (1965), “On the computational complexity of algorithms”, Transactions of the American Mathematical Society 117: 285-306, doi:10.2307/1994208, JSTOR 1994208, MR0170805 2017年6月10日閲覧。
- 岡本, 龍明 (2009-12-01), “相対化,自然な証明,代数化／P≠NP予想の難しさ”, 数学セミナー (日本評論社) 48 (12): 20-25
- Razborov, Alexander A.; Rudich, Steven (1997). “Natural proofs”. Journal of Computer and System Sciences 55: 24-35. doi:10.1006/jcss.1997.1494. (Draft)
- Baker, Theodore; Gill, John; Solovay, Robert (1975), “Relativizations of the P=?NP question”, SIAM J. Comput. 4 (4): 431-442 2017年6月10日閲覧。
- Williams, Ryan (2010-11-23), Non-Uniform ACC Circuit Lower Bounds 2017年6月10日閲覧。
関連項目
- 数学上の未解決問題
- 計算機科学の未解決問題
- 懸賞金問題
- 多項式階層
- 法月綸太郎……推理小説におけるこの問題に関しての考察がある。
 | この項目は、応用数学に関連した書きかけの項目です。この項目を加筆・訂正などしてくださる協力者を求めています。 |
- ^ a b Knuth, Donald E. (2014年5月20日). “Twenty Questions for Donald Knuth”. informit.com. InformIT. 2017年6月10日閲覧。
- ^ NSA (2012年). “Letters from John Nash” (PDF). 2017年6月10日閲覧。
- ^ a b Hartmanis, Juris. “Godel, von Neumann, and the P = NP problem”. Bulletin of the European Association for Theoretical Computer Science 38: 101-107. doi:10.1142/9789812794499_0033. この論文にはゲーデルの手紙の英訳（抄）も記載されている
[前の解説]
「P≠NP予想」の続きの解説一覧
- P≠NP予想のページへのリンク
