P対NP問題

P対NP問題は、その解を迅速に検証できるすべての問題が、迅速に解くこともできるのかを問うものであり、理論計算機科学における中心的な未解決問題であり、クレイミレニアム賞問題の一つでもあります。

Definition

Pは多項式時間で解ける問題のクラスであり、NPは提案された解が多項式時間で検証可能な問題のクラスです。P対NP問題は、これら2つのクラスが等しいかどうかを問うものであり、これは、あるNP完全問題が多項式時間で解ける場合にのみ成り立ちます。

Scope

このトピックでは、P対NPの正式な記述、任意のNP完全問題が多項式時間アルゴリズムを持つかどうかの等価性、いずれかの回答がもたらす結果、相対化、自然証明、代数化といった進展を阻んできた障壁、そしてクラスが異なるとする広範な予想について扱います。

Core questions

• 解を見つけることは、解を検証することよりも本質的に難しいのでしょうか？
• なぜこの答えは、単一のNP完全問題がPに属するかどうかにかかっているのでしょうか？
• PがNPに等しい場合、そして等しくない場合、世界はどのように見えるでしょうか？
• なぜ何十年もの努力がこの問題を解決できなかったのでしょうか？

Key theories

NP完全性との等価性

PがNPに等しいのは、任意のNP完全問題が多項式時間アルゴリズムを持つ場合に限られるため、この広範な問題は、充足可能性問題のような単一の具体的な問題の扱いやすさに帰着されます。

証明の障壁

相対化、自然証明、代数化の結果は、主要な既知の証明手法がP対NP問題を解決できないことを示しており、その困難さを説明し、根本的に新しい方法の探求を導いています。

Clinical relevance

PとNPの不等式が推定されていることは、NP困難な問題を手に負えないものとして扱う際の前提であり、暗号のセキュリティの根拠でもあります。なぜなら、NP問題を効率的に解くことができれば、広く使用されている暗号化が破られることになるからです。PとNPが等しいという建設的な証明は、最適化、ロジスティクス、科学を変革するでしょう。

History

クックは1971年にNP完全性とともにこの問題を提起し、それはすぐに根本的なものとして認識されました。1980年代の回路下限による試みは、ラズボロフとルディッチによって特定された自然証明の障壁に直面し、2000年にはクレイ数学研究所がこれをミレニアム賞問題として100万ドルの賞金をかけました。

Debates

P対NP問題は解決されるのか、そしてその答えは何なのか？

ほとんどの研究者はPがNPに等しくないと推測していますが、証明は存在せず、既知の手法では明らかに不十分です。解決が近いのか、根本的に新しい数学が必要なのか、あるいはこの問題が標準的な公理から独立している可能性さえあるのかについて、意見は分かれています。

Key figures

• Stephen Cook
• Leonid Levin
• Richard Karp
• Alexander Razborov

Seminal works

• cook1971
• aroraBarak2009

Frequently asked questions

PがNPに等しい場合、何が起こるでしょうか？

最適なスケジューリングから暗号コードの解読まで、現在手に負えないと考えられている多くの問題が効率的なアルゴリズムを持つようになり、解を見つける行為はそれを検証する行為よりも難しくなくなるでしょう。商業、セキュリティ、科学への影響は甚大であり、これがほとんどの専門家がPがNPに等しくないと考えている理由の一部です。

なぜこの問題は解決するのがそれほど難しいのでしょうか？

PがNPに等しいことを証明するには、NP完全問題に対する高速アルゴリズムが必要ですが、誰もそれを見つけていません。それらが異なることを証明するには、そのようなアルゴリズムが存在しないことを示す必要があります。相対化と自然証明に関する結果は、標準的な手法が後者を確立するのに本質的に不適格であることを示しており、そのため、真に新しいアプローチが必要とされています。