P≠NP予想
P≠NP予想（P≠NPよそう、テンプレート:Lang-en-short）は、計算複雑性理論（計算量理論）におけるクラスPとクラスNPが等しくないという予想である。P対NP問題（PたいNPもんだい、テンプレート:Lang-en-short）ということもある。
理論計算機科学と現代数学上の未解決問題の中でも最も重要な問題の一つであり、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となることが示されている。
現代暗号との関係
P≠NP予想は、暗号理論の分野でも重要な位置を占めている。
例えば、RSA暗号は素因数分解、ElGamal暗号および楕円曲線暗号(楕円曲線上のDLP)は離散対数問題の多項式時間による解法が存在しないことを安全性の根拠とした暗号であるが、これらの問題はどちらもクラスNPに属する問題に多項式時間帰着できる。仮にP≠NP予想が否定された場合（P＝NPの場合）、素因数分解などが多項式時間で計算可能であることになり、これらの暗号の安全性は根底から覆ることになる。
- 2002年8月6日にマニンドラ・アグラワル教授らによってAKS素数判定法が発表された。これによると与えられた自然数が素数であるかどうかを log n の多項式を上界とする決定的多項式時間で判定できる。これにより素数判定が実際にクラスPに属することが示された。しかし、素因数分解が多項式時間でできるかどうかははっきりしていない。
それだけではなく、P＝NPであれば「一方向性関数が存在しない」ことも証明できる。そして「一方向性関数が存在しない」ならば、多項式時間で破れない（暗号学的に安全な）公開鍵暗号やハッシュ関数、擬似乱数が存在しないことが導かれる。逆に「一方向性関数が存在する」ならば、少なくとも多項式時間では破れない共通鍵暗号が構成できること、擬似乱数が存在することが証明されている。
また、暗号方式とその平文・暗号文ペアを与えられて鍵の1ビットを判定する問題は、(通常)多項式時間で検証可能であるから、この暗号方式が既知平文攻撃の条件で鍵探索が困難であることを証明できるならば、多項式時間で判定不可能であることを示したことになり、P≠NP予想を証明できたことになる。
このように、P≠NP予想は計算量的安全性を通じて現代暗号理論と密接に関係している。
参考文献
- Stephen Cook, "The P versus NP Problem", 2000. テンプレート:PDFlink
- 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)
