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 . この論文にはゲーデルの手紙の英訳(抄)も記載されている
- 1 P≠NP予想とは
- 2 P≠NP予想の概要
- 3 概要
- 4 歴史
- 5 重要性
P≠NP予想
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2022/07/25 09:14 UTC 版)
「計算機科学の未解決問題」の記事における「P≠NP予想」の解説
Pとは多項式時間で解答の見つかる問題のクラスを表し、これに対しNPは多項式時間で解答が検証できる問題のクラスを表す。クラスPの問題は同時にクラスNPであることは証明されている(つまりP⊆NP)。 ここでP≠NP問題とは、NPがPに含まれるのかどうか(P⊃NPかどうか)、すなわちPとNPは等しいのか(P=NPかどうか)という問題のことである。この問題の解決は、計算機がもつある種の限界を証明することにあたるため、広く注目されている。 もしPとNPが同じクラスであれば(つまりP=NPであれば)、素因数分解や充足可能性問題など現在効率的な算法の存在しない問題を解くことができる。P≠NP予想という名前も示すとおり、現在PとNPは異なるクラスであろうと予想されているが、証明されていない。
※この「P≠NP予想」の解説は、「計算機科学の未解決問題」の解説の一部です。
「P≠NP予想」を含む「計算機科学の未解決問題」の記事については、「計算機科学の未解決問題」の概要を参照ください。
- P≠NP予想のページへのリンク