P≠NP予想
(P≠NP問題 から転送)
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2024/03/09 14:32 UTC 版)
P≠NP予想（P≠NPよそう、英語: P is not NP）は、計算複雑性理論（計算量理論）における予想 (未解決問題) の1つであり、「クラスPとクラスNPが等しくない」すなわち「クラスNPの元だがクラスPの元でないような決定問題（判定問題）が存在する」というものである。P対NP問題（PたいNPもんだい、英: P versus NP）と呼ばれることもある。
- ^ 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予想」の続きの解説一覧
- 1 P≠NP予想とは
- 2 P≠NP予想の概要
- 3 概要
- 4 歴史
- 5 重要性
- P≠NP問題のページへのリンク
