50年越しの未解決問題
「P対NP問題」に挑む
コンピューター科学者たち

1.

この記事はマガジン「量子時代のコンピューティング」に収録されています。 マガジンの紹介

2021年7月19日月曜日。新型コロナウイルス感染症（COVID-19）のパンデミックが2年目の夏を迎えた真っ只中、複雑性理論分野で著名なコンピューター科学者が、ある学術誌の管理上の不手際についてメッセージをツイートした。締めの言葉が物議を醸した。

「ハッピー・マンデー」。

パラレル・ワールドならば、本当に幸せな月曜日だったかもしれない。その日、ある証明が、「実現可能な計算の限界を探る優れた独創的研究」を扱う権威ある雑誌「ACM・トランザクション・オン・コンピュテーショナル・セオリー（ACM Transactions on Computational Theory）」のオンライン版に掲載されたのだ。その証明は、あらゆる問題の中で最も困難とされる問題を解決し、100万ドルの賞金と、アリストテレスに匹敵する名声を永遠にもたらす、理論コンピューター科学界の聖杯となるはずだった。

その問題とは、「P対NP問題」である。P対NP問題は、100万ドルの懸賞金がかけられており、理論コンピューター科学や数学において最も重要であると同時に、極めて解くのが難しいと考えられている。計算の決まりや限界、そして野心に関わる中心的な問題を扱うこの問題とは、次のように問いかける。

「なぜ、一部の問題は他の問題より難しいのか？」

「コンピューターが現実的に解決できる問題とはどれか？」

「時間はどのくらいかかるのか？」

そして、この問題を解き明かすことは、哲学的にも実用的にも大きな見返りのある探求だ。

テキサス大学オースティン校のコンピューター科学者スコット・アーロンソン教授は、自らの考えをまとめた著書『デモクリトスと量子計算 （原題：Quantum computing Since Democritus、2020年）』の中でこう書いている。「このP対NP問題を見て下さい。何と言えばいいのでしょうか。人はこの問題を『おそらく理論コンピューター科学における中心的な未解決問題』だと表現したがりますが、滑稽なほど控えめな表現です。P対NP問題は、人類史上最も深い問題の1つだからです」。

この話の支持者の考えに、次のようなものがある。

「P問題」は、コンピューターが簡単に解決できる問題を表す。

「NP問題」とは、ジグソーパズルや数独のように、いったん解けてしまえば、正しいかどうかの確認が容易な問題を指す。NP問題の多くは、社会が直面する最も困難かつ緊急な問題に対応している。

100万ドルの懸賞金のかかったP対NP問題とは、「P問題とNP問題は同じなのだろうか？」というものだ。つまり、「極めて困難に見える問題も、途方もなく速く適切なアルゴリズムを見つけられた場合、それを用いれば妥当な時間で解けるだろうか？」ということだ。もしそうであれば、多くの難問がいきなり解けるようになるだろう。アルゴリズムによる解決策は、医学や工学、経済学、生物学、生態学、神経科学、社会学、産業、芸術、さらには政治などの分野にまでユートピア的な社会変化をもたらす可能性がある。

分類が進化すると、難しい問題でも、研究者がより効率的な解決策を見い出すようになり、簡単な問題であることが明らかになることもある。例えば、ある自然数が素数かどうかを判定する問題は、1970年代半ばからNP問題に属することであることが知られていた。だが2002年、インド工科大学カーンプル校の3人のコンピューター科学者が、無条件下での証明と巧妙なアルゴリズムを考案し、この問題がP問題に属することをついに確認した。

あらゆる困難な問題がこういったアルゴリズムによる巧みな操作で変換されるとしたら、人類や地球、社会にもたらされる影響は甚大だろう。

まず、暗号化システムは、そのほとんどがNP問題に基づいているため、解読されてしまうだろう。安全に通信するには、まったく別のアプローチを見つけなければならない。生物学における50年来の大きな課題であるタンパク質の折り畳みも、より扱いやすくなり、新たな治療薬の設計や産業廃棄物を分解する酵素の発見が促されるだろう。また、最短距離で目的地に到着できるドライブ旅行を計画したり、披露宴の席次表で友人だけのテーブルを作ったりするなど、日常的な難問の最適解を見出せるようになるだろう。

P対NP問題は、50年前、数理論理学と電子計算技術の融合という極めて重大な出来事以来、世界中の研究者がその解決に向け、壮大な試みに挑んできた。コンピューター科学者の中には、その努力をシーシュポスにたとえる人もいる（日本版注：ギリシャ神話に登場する人物。山頂まで引き上げた岩が自重で転がり落ちるという苦行を永遠に繰り返す）。だが、この問題を最初に探求し始めた研究者たちが解決策を見い出せないまま時間切れになる一方で、新しい世代は喜んで取り組んでいる。

カリフォルニア大学バークレー校で博士号を取得したばかりのコンピューター科学者マニュエル・セービンは、P対NP問題の魅力は、「太陽が地球を飲み込むまで答えが分からない」くらい困難な問題の不可能性を探る点にあるという。答えに到達するのは非現実的かもしれないが、この問題に取り組まなければ後悔するだろうと、セービン博士は言う。

ケンブリッジ大学の数学者ティモシー・ガワーズ教授は、これは「わたしがよく罹る数学病の一種です」と言う。学生たちに、このテーマに関する小論文を書く課題を出したところ、ガワーズ教授は2013年の夏をすべてこの問題に費やす羽目になった。自身のブログでこう振り返る。「6月に学生たちの小論文を採点した後、1〜2時間だけこの問題についてもう一度考えてみようと思ったところ、それが3カ月になってしまいました」。

この問題を提起して1971年に重要な論文を発表し、計算複雑性理論を立ち上げたトロント大学のコンピューター科学者スティーブン・クック教授ですら、この問題には手を焼いた。この業績により、クック教授はコンピューター科学分野のノーベル賞として知られるチューリング賞を受賞している。だが、クック教授は解決策を見いだせなかった。良い考えが思い浮かばなかったのだという。「あまりにも難しすぎるのです」。

2.

マサチューセッツ工科大学（MIT）のコンピューター科学者マイケル・シプサ教授は、この問題に10年は費やしたと言う。1970年代の大学院生時代に、シプサ教授はこの問題に興味を持ち、友人のレン・アドルマンに20世紀末までの解決に1オンス（約30グラム）の金を賭けた（賭けに負けたシプサ教授は金を支払った）。

1980年代には、シプサ教授が「制限付き」計算モデルでこの問題の一部を解くという目覚ましい結果を出したお陰で、この分野が脚光を浴び、いくつかの成果も得られ、解決はそう遠くないという期待が持たれた。

シプサ教授は、今でも時々この問題に立ち戻り、不動の大使として数え切れないほどの講演をしている。

シプサ教授はP対NP問題をわかりやすく説明するため、基本的な掛け算の問題から始める。7 × 13＝はいくつになるだろうか？

簡単に暗算できるだろう。答えは91だ。これ以上大きな数字になると、多少難しくなるが、それでもコンピューターを使えば一瞬で計算できるだろう。

だが、こういった問題も見方を変えると、別の問題が発生する。たとえば、97桁の素数を2つ掛け合わせると、次のような莫大な数字になる。

310 7418240490 0437213507 5003588856 7930037346 0228427275 4572016194 8823206440 5180815045 5634682967 1723286782 4379162728 3803341547 1073108501 9195485290 0733772482 2783525742 3864540146 9173660247 7652346609

この素因数分解問題は、暗号に用いられるRSA鍵の解読の難易度を評価する課題の一部だった。シプサ教授によれば、この問題を解くのに80台のプロセッサーで5カ月間計算し続けたという。プロセッサーが1台では約33年かかる計算だ。素因数分解が難しいのは、天文学的な数の可能性を一つずつ確認する「力づくの方法」によるしかないからだ。コンピューターといえども、これでは時間がかかる。

「ここで興味深いのは、『本当に検索する必要があるのか』ということです」と、シプサ教授はいう。「あるいは、検索せずに素早く素因数分解の解を見つけられるような解法があるのでしょうか。それはまだわかりません」。

これは、「計算複雑性」の核心に触れる問題だ。「計算複雑性」の分野には、研究者たちが理解を深めようと取り組む多くの難解な問題であふれている。アーロンソン教授は、オンライン・カタログ「コンプレクシティ・ズー（Complexity Zoo）」を構築し、545種類（数は増え続けている）の問題を掲載した。各々の問題は、その複雑さや難易度、解を求めるために必要な資源（時間、メモリ、エネルギー）に応じて分類されている。P対NP問題が主な見所だ。

P問題は「すべての始まりのクラス」であり、コンピューターが合理的な時間で解くことができる問題のクラスだ。具体的には、解を求めるのにかかる時間がn^2のような多項式関数で記述できる問題をP問題と呼ぶ。多項式時間アルゴリズムでは、nは入力の大きさ（入力サイズ）であり、その入力に対して解を求めるのにかかる時間は、合理的な割合（この場合はnの2乗）で成長する。

一方、困難なNP問題の中には、実行時間が2^nのような指数関数（新型コロナウイルス感染症の拡散スピードのような急激な増加のこと）で定義されるアルゴリズムでなければ解けないものもある。アーロンソン教授曰く、NP問題は「破れた希望と空しい夢のクラス」だという。しかしながら、「あらゆるNP問題が難しいわけではない」という、よくある誤解についても明らかにした。実際、クラスNPはクラスPを含む。簡単に解ける問題は、当然ながら検証も簡単だからだ。

難易度の高いNP問題は、極めて重要な実用性があることが多い。こういった問題を解く際に、力づくで徹底的に探索する方法をとると、解を得るのに非現実的なほど長い時間（数億年単位）がかかる可能性がある。力まかせの探索アルゴリズムが最良のアルゴリズムならば、クラスPとクラスNPは等しくないことになる（P≠NP）。

どうやら、専門家の間でこれはコンセンサスになっているようだ。P≠NPを宗教的信念にたとえる人もいる。クラスPとク …