P≠NP予想(P≠NPよそう、: P is not NP)は、計算複雑性理論(計算量理論)におけるクラスPクラスNPが等しくないという予想である。P対NP問題(PたいNPもんだい、: P versus NP)と呼ばれることもある。

理論計算機科学と現代数学上の未解決問題の中でも最も重要な問題の一つであり、2000年クレイ数学研究所ミレニアム懸賞問題の一つとして、この問題に対して100万ドルの懸賞金がかけられた。

目次

概要編集

クラスPとは、決定性チューリング機械において、多項式時間で判定可能な問題のクラスであり、クラスNPは、Yesとなる証拠(Witnessという)が与えられたとき、多項式時間でWitnessの正当性の判定(これを検証という)が可能な問題のクラスである。多項式時間で判定可能な問題は、多項式時間で検証可能であるので、P⊆NPであることは明らかであるが、PがNPの真部分集合であるか否かについては明確ではない。証明はまだないが、多くの研究者はP≠NPだと信じている。そして、このクラスPとクラスNPが等しくないという予想を「P≠NP予想」という。

仮にP=NPであると示された場合、多項式時間で検証可能な問題は全て多項式時間で判定可能であることを意味し、未だ効率の悪い指数時間アルゴリズムしかないさまざまな分野の問題に効率的な計算アルゴリズムが与えられる可能性が示される。しかし、多くの研究者が長年にわたって多項式時間オーダーのアルゴリズムの開発に取り組んでいるにもかかわらず、そのような効率的なアルゴリズムは見つかっていない。このことがP≠NP予想の根拠の一つとなっている。

歴史編集

重要性編集

他の問題との関係編集

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となることが示されている。

参考文献編集

  • 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)

関連項目編集