【ピーノットイコールエヌピーよそう】
P≠NP予想 とは？
最終更新:
💡 答え合わせが速くても、答えを見つけるのは難しい？
答えの候補を効率よく確かめられる問題は、答えも効率よく見つけられるのか。PとNPという問題の集合が異なるはずだ、という未解決の予想。
📌 このページのポイント
- Pは多項式時間で解ける判定問題の集合
- NPは「はい」の証拠を多項式時間で検証できる判定問題の集合
- PはNPに含まれる。二つが等しいかは未解決
- P≠NPは、NPの中にPに属さない問題があるという予想
ひよこ PとNPって、何を分けているの？
ペンギン先生 「条件を満たすものがあるか？」に、はい・いいえで答える判定問題を分類しているよ。Pは入力の長さに対して多項式時間で解けるもの。NPは、答えが「はい」のとき、その証拠を多項式時間で確かめられるものだよ。証拠の長さも入力の長さの多項式に収まる必要があるんだ。
ひよこ 答え合わせだけなら簡単、というのは？
ペンギン先生 たとえば「すべての町を1回ずつ通る道がある？」という問題。候補の道を渡されれば、町を重複なく全部通り、道がつながっているかを確かめられる。でも、そんな道を最初から探す方法が同じように効率的かは別の話なんだ。
ひよこ PとNPは、別々の集合なの？
ペンギン先生 PはNPの中に含まれるよ。自分で効率よく答えを計算できれば、「はい」かどうかも確かめられるからね。未解決なのは、NPのすべてがPにも入るか、Pに入らない問題があるかという点。NPは「多項式時間ではない」の略ではないよ。
ひよこ 「効率がよい」なら、いつでもすぐ終わる？
ペンギン先生 ここでは入力が大きくなるときの計算量が、多項式で抑えられるという理論上の意味だよ。多項式でも次数や定数が大きければ、実際の計算に長い時間がかかることがある。特定の小さな例を速く解けたことだけで、問題全体がPだと証明したことにもならないんだ。
ひよこ P≠NPは、もう証明されているの？
ペンギン先生 まだだよ。クレイ数学研究所のミレニアム懸賞問題の一つで、PとNPが等しくないという予想も、等しいという結論も確立していない。図も「PはNPに含まれる」という既知の関係と、「等しいかは未解決」を分けているよ。
まとめ：ざっくりこれだけ覚えればOK！
「P≠NP予想」って出てきたら「答え合わせは速くても、答えを見つけるのは難しい問題があるはず、という未解決の予想」と思えばだいたいOK！
📖 おまけ：英語の意味
「P versus NP problem」 ＝ P対NP問題
💬 P（Polynomial time＝多項式時間）とNP（Nondeterministic Polynomial time＝非決定性多項式時間）が等しいかどうかを問う問題だよ