当サイトを閲覧いただきありがとうございます。 本記事はコンピュータ科学最大の未解決問題「P対NP問題」について解説します。
数独を解くのは大変ですが、解けたと主張する人の答案を検算するのは一瞬です。ジグソーパズルを組むのは一苦労ですが、完成写真と見比べるのは一目です。この日常の実感を突き詰めると、とんでもない問いに行き着きます。「答え合わせが一瞬でできる問題は、実は解くのも一瞬でできるのではないか？」まさかと思うでしょう。ところが、この「まさか」を証明した人は誰もいません。これがP対NP問題で、解決には100万ドルの懸賞金がかかっています。
「解く」と「確かめる」は別の仕事
P対NP問題の主役は、問題の「難しさ」を測るという発想です。コンピュータ科学では、問題の規模が大きくなったときに計算時間がどう伸びるかで難しさを測ります。
Pは、規模が大きくなっても計算時間が現実的なペースでしか伸びない問題の集まりです。かけ算、並べ替え、地図上の最短経路探し。これらは規模が10倍になっても時間は緩やかにしか増えず、「効率よく解ける問題」と呼ばれます。
NPは、「答えの候補を渡されれば、正しいかどうかを効率よく確かめられる問題」の集まりです。数独は代表例です。マスが増えると解くのは急激に苦しくなりますが、記入済みの盤面の検算はすぐ終わります。
ここで大事なのは、効率よく解ける問題は、必ず効率よく確かめられるということです（解いてしまえば確かめられるので）。つまりPはNPに含まれます。問題は逆方向です。「確かめるのが速い問題は、すべて解くのも速いのか？」つまりPとNPは同じものなのか、それとも本当に別物なのか。これがP対NP問題の全文です。
1971年、問題に「王様」がいると分かった
この問いを数学の土俵に載せたのは、1971年のスティーブン・クックの論文です（旧ソ連のレオニード・レヴィンも独立に同じ発見をしています）。クックが証明したのは、驚くべき事実でした。
NPに属する問題の中に、「この問題さえ効率よく解ければ、NPのすべての問題が効率よく解ける」という万能の問題が存在するのです。この種の問題は「NP完全」と呼ばれます。最初にNP完全と証明されたのは、論理式のつじつま合わせ問題（充足可能性問題）でした。
翌1972年にはリチャード・カープが、実社会の有名問題21個が軒並みNP完全であることを示します。以後リストは増え続け、現在では数千の問題がNP完全と分かっています。例を挙げます。
・巡回セールスマン問題：多数の都市を全部回る最短ルートはどれか ・ナップサック問題：容量制限内で価値最大の荷物の組み合わせはどれか ・時間割編成：制約をすべて満たす授業の割り当ては存在するか ・数独（一般化版）：n×nの数独に解はあるか
NP完全問題は互いに翻訳可能な運命共同体です。どれか1つでも効率的な解法が見つかれば全員が一斉に陥落してP=NPが確定し、どれか1つでも「効率的に解けない」と証明されれば全員が不落と確定してP≠NPが決まります。数千の問題が手を繋いで、まとめて崖っぷちに立っている。この構図の鮮やかさが、P対NP問題を特別な存在にしています。
誤解のないよう付け加えると、NP完全は「現実には手も足も出ない」という意味ではありません。最初のNP完全問題だった論理式のつじつま合わせを解く「SATソルバー」というプログラムは、最悪ケースの理論とは裏腹に、数百万変数規模の実例を日常的に解いており、半導体の設計検証やソフトウェアのテストで実際に活躍しています。理論上の最悪と実務上の典型がこれほど乖離する理由も、実はよく分かっていません。大きな謎の足元に、小さな謎が積もっているのがこの分野です。
P=NPなら世界はどう変わってしまうのか
多くの未解決問題は、解けても日常は変わりません。P対NP問題は違います。答え次第で文明の景色が変わると言われる、実利直結の問題です。
もしP=NPが（実用的な解法込みで）証明されたら、まずインターネットの公開鍵暗号は崩壊します。現在の暗号は「答え合わせは簡単だが、解読は事実上不可能な計算」を安全性の根拠にしていますが、P=NPの世界ではその「事実上不可能」が消滅するからです。
一方で、恩恵も桁外れです。物流の最適ルート、創薬でのタンパク質の設計、工場のスケジューリングといったNP完全の実務問題が軒並み効率よく解けるようになります。さらに奇妙なことに、「定理の証明を確かめるのは機械的にできる」ことから、短い証明を持つ数学の定理は機械が効率よく発見できることになり、数学者の創造性の一部が計算に置き換わる可能性まで議論されています。
では専門家はどちらだと考えているのか。研究者への意識調査では、8割以上がP≠NPと予想しています。つまり「確かめるのが速くても、解くのが速いとは限らない。世の中には本質的に難しい問題が存在する」という見立てです。日常の実感にも合いますし、もしP=NPなら誰かがとっくに魔法の解法を見つけていそうなものだ、という経験則もあります。それでも証明はない。「みんなが正しいと信じる常識に、証明がない」という点で、リーマン予想と双璧の存在です。
証明の試みを阻む「壁の証明」
P対NP問題の面白さは、「なぜ証明できないのか」自体が研究されて定理になっていることです。
証明の試みが盛んだった時代を経て、研究者たちは奇妙な事実に気づきました。有望に見えた証明技法の一群には共通の型があり、その型に属する技法では原理的にP対NP問題を解決できないことが、それぞれ定理として証明されてしまったのです。相対化の壁、自然な証明の壁などと呼ばれるこれらの結果は、いわば「この山はこの装備では登れない」という登山禁止の看板です。
つまり現状は、山が高いだけでなく、知られているルートのほとんどに通行止めの証明が立っている状態です。解決には、既存の型のどれにも当てはまらない、まったく新しい数学が必要だと考えられています。クレイ数学研究所のミレニアム懸賞問題7問の中でも、P対NP問題は「最も解決が遠い」と評されることが多い問題です。
私はこの「不可能性の証明が積み上がっていく」展開が、このジャンルで一番SFめいた景色だと思っています。人類は問題を解けないだけでなく、「この方法では解けない」ということなら証明できてしまう。数学の自己言及的な力強さと不気味さが、ここに凝縮されています。
量子コンピュータなら解決できるのか
スーパーコンピュータや量子コンピュータで解決できないのですか？
できません。P対NP問題は「速い機械があるか」ではなく「速い手順（アルゴリズム）が存在するか」という数学の問題なので、機械の進歩では決着しません。なお量子コンピュータについては、素因数分解のような一部の問題を高速化できることが知られていますが、素因数分解はNP完全とは考えられておらず、量子コンピュータでもNP完全問題を効率よく解けるとは予想されていません。「量子でP対NP解決」という見出しには注意が必要です。
実務ではNP完全問題をどう扱っているのですか？
正面から最適解を求めるのを諦め、うまく付き合っています。具体的には、「最適でなくても十分良い解」で妥協する近似アルゴリズム、実用上の入力では高速に動くヒューリスティック、規模が小さければ力ずくで解くソルバー、の三本柱です。カーナビも物流も工場も、この妥協の技術の上で回っています。NP完全は「絶対解けない」ではなく「最悪の場合に厳密な最適を求めると手に負えない」という意味であり、ここを取り違えると実務の会話がかみ合わなくなります。
100万ドルはどうすればもらえるのですか？
P=NPとP≠NPのどちらを証明しても対象です。クレイ数学研究所のミレニアム懸賞問題の規定では、専門誌に掲載され、数学界の検証に2年間耐えることが条件とされています。毎年のように「証明した」と主張する論文が発表されては専門家の検証で崩れており、その顛末をまとめた記録サイトまで存在します。挑戦は自由ですが、まずはNP完全という概念の教科書を1冊楽しむところから始めるのが、遠回りに見えて一番の近道だと思います。
関連する未解決問題・パズル
同じミレニアム懸賞問題の「リーマン予想」、計算の限界と無限を巡る「カントールの対角線論法」、NP的な探索の凄みを体感できる「シマウマパズル」の記事です。
まとめ
本記事は「P対NP問題」について解説しました。如何だったでしょうか。
数独の検算とジグソーの見比べという日常の実感から出発して、暗号の運命と数学の未来まで賭け金が積み上がっていく。問いの入り口の低さと、賭けられているものの大きさの落差では、全未解決問題の中でも屈指だと思います。
「解くことと確かめることは、本質的に違う営みなのか」この問いは、コンピュータのない時代には数学の問題ですらありませんでした。人類が計算機を持ったからこそ見えた新しい謎だという点で、P対NP問題は未解決問題の中で最も若く、最も現代的な一問です。
未解決問題の一覧に戻りたい方は以下のリンクからどうぞ。
それでは次の記事も閲覧いただけると幸いです。
📚 シリーズ：数学・科学の未解決問題（8/16）
