【ピーノットイコールエヌピーよそう】
P≠NP予想 とは？
💡 答え合わせは簡単でも、答えを見つけるのは難しい...はず
📌 このページのポイント
- Pは多項式時間で解ける問題、NPは多項式時間で解の正しさを検証できる問題のクラス
- P≠NPが正しければ「検証は簡単だが解くのは本質的に難しい」問題が存在することになる
- 100万ドルの懸賞金がかかったミレニアム懸賞問題7つのうちの1つ
ひよこ PとかNPって何のこと？
ペンギン先生 Pは「効率的に解ける問題」の集合で、NPは「解が正しいか効率的に検証できる問題」の集合だよ。たとえばソートはPだけど、巡回セールスマン問題の最適解はNPに属するんだ
ひよこ 検証が簡単なら、解くのも簡単にできそうな気がするけど...
ペンギン先生 そこがこの問題の核心なんだ。たとえば数独を解くのは大変だけど、解けた答えが正しいかチェックするのは簡単だよね。「チェックが簡単＝解くのも簡単」とは限らないんじゃないか、というのがP≠NP予想だよ
ひよこ まだ証明されてないの？
ペンギン先生 そう、1971年にスティーブン・クックが定式化してから50年以上未解決のままなんだ。クレイ数学研究所が100万ドルの懸賞金をかけているミレニアム懸賞問題の1つでもあるよ
ひよこ もしP＝NPだと証明されたらどうなるの？
ペンギン先生 暗号が根本から崩壊する可能性があるよ。RSA暗号などは「素因数分解は解くのが難しいが検証は簡単」という前提に依存しているからね
ひよこ 逆にP≠NPが証明されたら？
ペンギン先生 「どうやっても効率的に解けない問題が存在する」ことが確定して、暗号の安全性に理論的な裏付けが生まれるよ。ほとんどの研究者はP≠NPだと信じているけど、証明にはまったく新しい数学的手法が必要だと考えられているんだ
まとめ：ざっくりこれだけ覚えればOK！
「P≠NP予想」って出てきたら「答え合わせは簡単でも、答えを見つけるのは本質的に難しい問題があるはず、というコンピュータ科学最大の未解決問題」と思えればだいたいOK！
📖 おまけ：英語の意味
「P versus NP problem」 ＝ P対NP問題
💬 P（Polynomial time＝多項式時間）とNP（Nondeterministic Polynomial time＝非決定性多項式時間）が等しいかどうかを問う問題だよ