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)と呼ばれることもある。


  1. ^ a b Knuth, Donald E. (2014年5月20日). “Twenty Questions for Donald Knuth”. informit.com. InformIT. 2017年6月10日閲覧。
  2. ^ NSA (2012年). “Letters from John Nash” (PDF). 2017年6月10日閲覧。
  3. ^ 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. https://doi.org/10.1142/9789812794499_0033.  この論文にはゲーデルの手紙の英訳(抄)も記載されている


「P≠NP予想」の続きの解説一覧

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予想」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。 お問い合わせ


英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「P≠NP予想」の関連用語

P≠NP予想のお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



P≠NP予想のページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアのP≠NP予想 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。
ウィキペディアウィキペディア
Text is available under GNU Free Documentation License (GFDL).
Weblio辞書に掲載されている「ウィキペディア小見出し辞書」の記事は、Wikipediaの計算機科学の未解決問題 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。

©2024 GRAS Group, Inc.RSS