解けたら100万ドル､ただし地球は滅亡する…どんな病気の薬も開発できるとされる数学の未解決問題の奥深さ すべての問題にはコツがあるかを問う｢P対NP｣問題

数学界には、証明することで世界におそろしい影響を与えるとされる未解決問題がある。NHKの知的エンターテインメント番組「笑わない数学」の放送内容を再構成した書籍より、100万ドルの懸賞金がかけられた難問「P対NP」問題を紹介する――。

※本稿は、NHK「笑わない数学」制作班編『笑わない数学3』（KADOKAWA）の一部を再編集したものです。

数学界で最も重要な未解決問題の1つ「P対NP問題」

今回のテーマは「P対NP問題」。

「P対NP問題」は、数学の世界で最も重要な未解決問題の1つで、なんと100万ドルの懸賞金までかかっている超難問です。

何が問われているのかと言えば、「P=NPなのか、それともP≠NPなのか」ということです。これだけでは何がなんだか、さっぱりわからないかと思いますので、身近な例でご説明しましょう。

皆さんは、「遠足のおやつ選び」をやったことありませんか？　子どもの頃、お小遣いを握りしめて、どのお菓子を買おうか悩みましたよね？

今ここに、おやつが40種類あって、全部をナップサックに入れると溢れてしまうとしましょう。ここで次の「問題」を考えます。

問題 ナップサックから溢れないようにおやつを入れて持っていきたいのだけれど、値段の合計を5000円以上にできる組合せはあるか？

40種類あるおやつに対し、それぞれ「買うか、買わないか」を選択する組合せは1兆995億1162万7776通りとなります。

その中から、ナップサックにちゃんと収まって合計が5000円以上になる組合せを探すのは、非常に面倒です。1兆を超える組合せを一つひとつ調べているうちに、折角の遠足も終わってしまいます。

解ければ楽園が訪れるかもしれないし、世界が滅びるかもしれない

「P対NP」問題をざっくり説明するならば、次のような問題です。

未解決問題　「P対NP」問題 数多く存在する組合せを一つひとつ「しらみつぶし」に調べないと答えが見つからないのか。それとも、「しらみつぶし」に調べなくても答えにたどり着ける「コツ」が存在するのか。

皆さんの中には、子どものおやつ選びみたいなことを、そんなに難しく考えなくてもよいのではないかと思われる方もいらっしゃるかもしれません。

しかし実は、おやつ選びのような「問題」に、もし簡単に解ける「コツ」が見つかったとすると、世界が一気にひっくり返ってしまうようなことが起きるかもしれないと言われています。経済や医療、流通といった、人類が悩み続けてきた問題がすっかり解決された、楽園のような世界が訪れるかもしれないし、戦争で世界の半分がなくなってしまう、地獄のような世界が訪れるかもしれないのです。

「P対NP」問題は、数学の枠を超えた、非常に大きなスケールの問題なのです。どうでしょうか、興味が湧いてきましたでしょうか。