未解決問題、応用数学と計算数学, 数学の基礎、1971年に提起
P対NP問題
未解決ミレニアム賞
入力サイズに関して多項式時間の決定的アルゴリズムで解ける判定問題のクラスをP、提案された解を多項式時間で検証できる判定問題のクラスをNPとする。問題は P = NP かどうか、つまり効率よく検証できる問題はすべて効率よく解けるアルゴリズムを持つかということである。
2026年時点で、P対NP問題は未解決のままであり、大多数の計算機科学者は P ≠ NP であると予想している。数十年にわたる研究により、相対化(ベイカー–ギル–ソロヴェイ、1975年)、自然な証明(ラズボロフ–ルディッチ、1994年)、代数化(アーロンソン–ウィグダーソン、2008年)といった形式的な障壁が明らかになっており、既知の証明手法の系統全体だけではこの問題を解決できないことが示されている。これがこの中心的な問題で進展が停滞している理由の一つである。
既知の最良の結果
- いかなるNP完全問題に対しても多項式時間アルゴリズムは知られておらず、3-SATのような問題に対する最良の既知アルゴリズムも最悪計算量は指数的である。
- 回路の下界は、単調回路や深さ制限回路といった制限されたモデルに対してのみ証明されており、PとNPを分離するために必要な一般回路にははるかに及ばない。
- 障壁となる結果(相対化、自然な証明、代数化)は、既知の証明手法の系統全体だけではP対NP問題を単独では解決できないことを示している。
使われた手法と限界
| 手法 | 達成したこと | 限界 |
|---|---|---|
| 対角線論法と相対化議論 | より弱い複雑性クラスを分離する(例:時間階層定理) | この問題は「相対化」しないため、P対NP問題自体を解決できないことが証明されている(ベイカー–ギル–ソロヴェイ、1975年) |
| 組合せ論的な回路下界 | 単調回路やAC0のような制限された回路クラスに対して指数的な下界を証明する | 自然な証明の障壁(ラズボロフ–ルディッチ、1994年)は、強い疑似乱数生成器が存在すると仮定すると、これらの手法が一般回路には拡張できないことを示す |
未解決の問い
- P = NP なのか、それとも P ≠ NP なのか。
- P ≠ NP の場合、PとNP完全の間に厳密に中間的な複雑さを持つ問題は存在するか(ラドナーの定理はそのような問題が存在することを証明しているが、自然な具体例は知られていない)。
参考文献
- Stephen A. Cook (1971). The complexity of theorem-proving procedures
- Richard M. Karp (1972). Reducibility among combinatorial problems
- Stephen Cook (Clay Mathematics Institute) (2000). P vs NP Problem
- Alexander A. Razborov, Steven Rudich (1997). Natural proofs