P≠NP予想との関係
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/06/01 16:46 UTC 版)
もし、いずれかのNP困難な問題を多項式時間で解くアルゴリズムが存在したなら、NPの全ての問題について多項式時間で解けることになり、P = NP が成り立つ。ところが、P＝NPが成立しても「任意のNP困難な問題が多項式時間で解ける」とは言えない。この関係を右上のベン図に示す。
※この「P≠NP予想との関係」の解説は、「NP困難」の解説の一部です。
「P≠NP予想との関係」を含む「NP困難」の記事については、「NP困難」の概要を参照ください。
ウィキペディア小見出し辞書の「P≠NP予想との関係」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。 お問い合わせ。
- P≠NP予想との関係のページへのリンク
