解けたら100万ドル､ただし地球は滅亡する…どんな病気の薬も開発できるとされる数学の未解決問題の奥深さ

数学界には、証明することで世界におそろしい影響を与えるとされる未解決問題がある。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」問題は、数学の枠を超えた、非常に大きなスケールの問題なのです。どうでしょうか、興味が湧いてきましたでしょうか。
■解くコツがあるP問題、ないNP問題
それでは、「P対NP」問題に迫っていくことにしましょう。
そもそも、先ほどから出てくる「P」とか「NP」とは、一体なんなのか、説明していきたいと思います。
「P対NP」で扱う問題は、答えがYESかNOとなる「判定問題」といわれる問題です。
「P問題」は、判定問題の中でも、しらみつぶしに調べなくても、多項式時間（簡単に言うと“ほどほどの時間”）でYESかNOを判定できる、つまり計算に「コツ」が存在するような問題のことです。
一方、「NP問題」は、判定問題の中でも、答えがYESとなる証拠（特定のルートやお菓子の組合せ方など）を教えて貰ったらそれが正しいかどうかを多項式時間で検証できる問題です。
NP問題の中には、しらみつぶしに調べないといけないような、確実に答えを出すまでには莫大な時間を要すると予想されている問題が含まれています。YESかNOを判定するための「コツ」が現状では少なくとも知られておらず、「コツ」が存在しないと予想されている問題です。
■しらみつぶしには限界がある
それでは、実際の問題例を見てみましょう。
ここでは「巡回セールスマン問題」と呼ばれる次の問題を考えます。
巡回セールスマン問題

セールスマンが担当の家をちょうど1回ずつ訪ねて営業所に帰って来たい。このとき、総移動時間が一定値以内の経路は存在するか？
図表1は、回る家が4軒の場合で、数字はそれぞれの道を通過するのにかかる時間です。さて、30分以内で回れる経路はあるでしょうか？
この図であれば、調べなければならない経路の数はABCDやCDBAなど、全部で12通りです。
全経路をしらみつぶしに調べた結果は図表2のとおりとなります。
最短で回れるのはADBC（CBDAも同じ）の経路で、30分以内が達成できることがわかりました。したがって、この図の場合の答えはYESです。
もっと熱心なセールスマンなら、4軒以上回るはずですので、思い切って、家の数を50に増やしてみます。
すると、調べなければならない経路の数は、
15207046600856689021806304083032384422188820784480256000000000000通り。とんでもない数になりました。
それでもコンピュータを使えば、そんなに時間をかけずに調べつくしてくれると思われるかもしれません。
しかし、実はこの数は、たとえコンピュータが超優秀で、1つの経路の総移動時間をチェックするのに、光が水素原子を横切るほどの僅かな時間、「1000京分の3」秒しかかからなかったとしても、すべての経路を調べるのに、
約1267253883000000000000000000000000000000000時間
かかります。
これは年に換算すると、約144663685300000000000000000000000000000年であり、宇宙の年齢138億年を超えています。ちなみに、宇宙の年齢の何倍かというと、
約10482875740000000000000000000倍です。
このように、家が50軒の場合にすべてを回る経路をしらみつぶしに調べてみようとしても、宇宙の年齢以上に時間がかかります。それは人類には解けないのと同じことでしょう。「しらみつぶし」に調べないと判定結果が出せない面倒なNP問題は、それほど大変な問題なのです。
■実は解くコツがあったNP問題
NP問題は他にもたくさんあります。
例えば、最初にお話した遠足のおやつを選ぶ問題。実は、これに似た問題も、数学の世界では「ナップサック問題」と呼ばれ、れっきとしたNP問題にあげられています。
ナップサック問題

ナップサックから溢れないような品物の入れ方の組合せの中から、品物の価値の合計が「決められた額」以上になる組合せがあるかどうかを判定する問題
NP問題は他にもたくさんあり、世の中には「しらみつぶし」に調べなければならないほど面倒と思われているNP問題がたくさん溢れているのです。
それでは、次はP問題について説明していきます。
P問題は、「しらみつぶし」に調べなくても、簡単に判定するための「コツ」が存在する問題だったことを思い出してください。
わかりやすい例を紹介したいと思います。図表3は18世紀のヨーロッパにあった、ケーニヒスベルク（現ロシア・カリーニングラード）という町の地図です。
町には川が流れていて、7つの橋がかかっていました。ある時、町の人たちの間で、次の問題が話題にあがります。
ケーニヒスベルクの橋の問題

この7つの橋をちょうど1回ずつ渡って、すべての橋を渡り切る経路はあるか？
それでは、皆さん、そのような経路があるか調べてみてください。
やってみるとわかるのですが、調べなければならない経路がたくさんあります。ごく単純に数え上げたとすると、最大5040通りも調べないといけませんので、7つの橋をちょうど1回ずつ渡って、すべての橋を渡り切る経路があるかどうかを調べるのは非常に大変そうです。
町の人たちにとってこの問題は、「しらみつぶし」に調べないと解けない、今でいう「NP問題」だと思われていたでしょう。
■橋を1回だけ渡る問題を一筆書き問題に置き換えた
しかし、実はこの問題は、簡単に解く「コツ」が存在するP問題だったことがわかりました。簡単に解く「コツ」を見つけたのは、18世紀の天才数学者レオンハルト・オイラーです。
まず、オイラーは、7つの橋と陸地の関係を簡単なグラフに示すことから始めました。すなわち、図表4のようにそれぞれの陸地を点で表し、橋を通る線で結びました。
そして、オイラーは「7つの橋を1回ずつだけ渡り、すべての橋を渡り切る経路はあるのか」という問題は、「このグラフにあるすべての線を、一筆書きでなぞれるか」という問題に置き換えられることに気づいたのです。
ケーニヒスベルクの橋の問題（オイラーによる置き換え）

このグラフにあるすべての線を、一筆書きでなぞれるか？
あるグラフに対し、一筆書きができるのかどうかを、どうやって判別すればよいのでしょうか？
■しらみつぶしに調べなくても答えがわかる
オイラーは、「それぞれの点から伸びる線の数」に注目し、一筆書きができるかどうかを判別する「コツ」が存在することを発見しました。
一筆書きができるグラフの条件

①各点から伸びる線の数が、すべて偶数

②各点から伸びる線の数が、2点は奇数で、それ以外の点は偶数
それでは、ケーニヒスベルクの橋の場合はどうなのでしょうか？
左上の点からは3本、その下の点からは5本、その下は3本、それぞれ線が出ていますからこの時点で、点から伸びる線の数が奇数の点が2点を超えて存在しますので、一筆書きができる条件①、②のどちらも満たしません。
よって、7つの橋をちょうど1回ずつ渡る経路は、「存在しない」ということです。
このように、ケーニヒスベルクの橋の問題は、「しらみつぶし」に線をなぞらなくても、点から伸びる線の数さえ数えれば、すぐに判別することができます。つまり、ケーニヒスベルクの橋の問題は、解く「コツ」があって、簡単に答えがわかるP問題だったのです。
■この世のすべてのNP問題は解くコツのあるP問題か
NP問題の中には、解く「コツ」がある「問題」（P問題）と、解くコツがなく「しらみつぶし」に調べないと解けないと思われている「問題」があります。
現在、数学の世界には、「しらみつぶし」に調べないと解けないと思われているNP問題が数多くあります。一方、簡単に解く「コツ」がわかっているP問題は、「しらみつぶし」に調べないと解けないと思われているNP問題に比べて数は少ないのです。
ここで思い出していただきたいのは、そもそも「P対NP」問題とは、P=NPなのか、P≠NPなのか、を問う問題だということです。すなわち「すべてのNP問題が、実は「コツ」が存在するP問題であるか？」を問う難問なのです。
NP問題の中には、解く「コツ」が見つかり、本当はP問題だったことがわかった、というケースがあります。
例えば、2002年、インド工科大学のアグラワル教授らによって発表された「素数判定問題」があります。
ある巨大な数が、素数かどうかを判定する問題は「簡単に解くコツがないNP問題」と考えられてきましたが、教授らは短時間で判定できる方法を発見し、P問題であることが証明されたのです。
でもまだ、たった1つのNPの石がPになっただけです。
ということは、残るNP問題一つひとつに解く「コツ」があるのかどうか、調べなければならないのでしょうか？
実は、とんでもない発見をした数学者がいました。
■冷戦時代に研究された「スケジューリング問題」
時は1970年代、世界は、アメリカを中心とする西側諸国と、ソビエト連邦中心の東側諸国とが対立する冷戦が続いていました。
当時、両陣営では、戦力を最大化するために、多くの兵士や兵器をどのように割り振ればよいのか、という問題を数学的に考える研究を推し進めていました。これは、NP問題の1つである「スケジューリング問題」という問題に通じる研究です。
アメリカとソ連にいた数学者たちは、お互いに交流することもなく、それぞれが別々に研究をすすめていました。
そうであるにもかかわらず、東西でほぼ同じ時代に「P対NP」問題に関わる重大な事実に気づきました。
その重大な事実に気づいたのは、西側ではアメリカで研究していたスティーブン・クック、東側ではソ連のレオニード・レビンでした。2人は、NP問題の一つひとつをいちいち調べなくても、たった1つのNP問題だけを調べればよいことに気づきました。
実は、NP問題の中には「特に難しいNP問題」がいくつも存在します。この「特に難しいNP問題」には先ほど紹介した「巡回セールスマン問題」や「ナップサック問題」も含まれています。
クックとレビンが気づいたのは、「特に難しいNP問題」のどれか1つでも簡単に解く「コツ」が見つかれば、つまり、P問題であることが示せれば、ほかのすべてのNP問題も一気にP問題に引きずりおろせる、ということだったのです。
■もしP=NPが証明されたら…
NP問題の中でも「特に難しいNP問題」がどれか1つでもP問題であることがわかれば、すべてのNP問題が一気にP問題であることがわかるというのは、皆さん驚かれたかと思います。
しかし、たった1つだけでよいのであれば、P=NPが証明できるかもと思われるかもしれません。
もし、P=NPの証明ができてしまったら、世の中の複雑な問題の多くが、一気に解決する可能性があると言われています。
例えば、医学の分野。これまで、「しらみつぶし」に調べなければならなかったタンパク質の構造が簡単に解明されるようになり、新薬の開発がスピードアップし、これまで治療が難しいとされてきた病気もすぐに治せる、という日が来る可能性が出てくるのです。
さらに、P=NPの世界では運送業界も一変します。もっとも効率の良い配送スケジュールが短時間で得られる可能性が広がり、ネットショッピングはますます便利になるかもしれません。
■戦争に利用され、世界の破滅につながるかも
しかし、P=NPの世界はいいことばかりではありません。
P=NPが証明され、複雑な問題が一気に解決する方法が見つかれば、戦争に利用されることを危惧する専門家もいます。
ある専門家はこう言います。
「P=NPが証明されれば、核兵器の開発やサイバー攻撃、敵対する国の電力を停止することなどが簡単になり、世界に大変な損害をもたらすかもしれません。
例えば、P=NPによってアメリカの戦力が上がるようなことがあれば、敵対する国がパニックになって核兵器を使用するかもしれない。
そんなことを考えると、ゾッとします。
もし、私がP=NPとなる証明方法を知っていて、タイムマシンで冷戦期に戻れたとしても、その方法はどちらにも教えませんね」
皆さん、このお話どう感じましたでしょうか？　P=NPだったら、世界の破滅につながるかもしれないというのは恐ろしい話です。
しかしながら、実は多くの数学者がP≠NPと予想しているようです。
果たしてP=NPなのか、P≠NPなのか。この世紀の難問が解決される日が来るかは、誰にもわかりません。

----------

NHK「笑わない数学」制作班
パンサー尾形貴弘が難解な数学の世界を大真面目に解説する異色の知的エンターテインメント番組。レギュラー番組としてNHK総合テレビで、シーズン1が2022年7月から9月まで、シーズン2が2023年10月から12月まで放送された。シーズン1はギャラクシー賞テレビ部門の2022年9月度月間賞に選ばれた。過去の番組はNHKオンデマンドやDVDで確認することができる。

----------

（NHK「笑わない数学」制作班）