複雑性理論の知識の限界への 50 年の旅 | クアンタマガジン

2007 年の秋学期の最初の週、マルコ カルモシーノはマサチューセッツ大学アマースト校のすべてのコンピュータ サイエンス専攻に必須の数学の授業に引きずり込まれました。 XNUMX 年生のカルモシーノさんは、ビデオ ゲームをデザインするために大学を中退することを検討していました。 それから教授は、彼の人生の流れを変えるような単純な質問を投げかけました。「数学が実際に機能することをどのようにして知っていますか?」

「そのおかげで、私は座って注意を払うようになりました」と振り返ります カルモシーノ, 現在はIBMの理論コンピュータ科学者です。 彼は、クルト・ゲーデルの研究に関するオプションのセミナーに申し込みました。ゲーデルの目まぐるしい自己言及的議論は、数学的推論の限界を初めて明らかにし、計算の基本的な限界に関する将来のすべての研究の基礎を築きました。 吸収することがたくさんありました。

「100％理解できませんでした」とカルモシーノ氏は語った。 「でも、そうしたいのは分かっていたんです。」

今日、経験豊富な研究者でも、P 対 NP 問題として知られる理論コンピューター サイエンスの中心的な未解決の問題に直面すると、理解が不足していることがわかります。 本質的に、この質問は、長らく非常に難しいと考えられてきた多くの計算問題が実際に (まだ発見されていない秘密のショートカットを介して) 簡単に解決できるのか、それともほとんどの研究者が疑っているように、本当に難しいのかを問うものです。 危機に瀕しているのは、知ることができるものの性質に他なりません。

計算複雑性理論（さまざまな問題の本質的な難しさに関するそのような問題の研究）の分野の研究者による数十年の努力にもかかわらず、P 対 NP の問題の解決は依然として得られないままです。 そして、証明をどこから始めるべきかさえ明確ではありません。

「ロードマップはない」と彼は言った マイケル・シプサー、マサチューセッツ工科大学のベテランの複雑性理論家であり、1980 年代にこの問題に何年も取り組んできました。 「まるで荒野に行っているような気分です。」

計算問題が解決するのが難しいことを証明すること自体が難しい仕事のようです。 しかし、なぜそんなに難しいのでしょうか？ そしてそれはどれほど難しいのでしょうか？ カルモシーノとメタ複雑性のサブ分野の他の研究者は、このような問題を計算問題として再定式化し、複雑性理論のレンズをそれ自体に戻すことでこの分野を前進させています。

「あなたはこう思うかもしれない、『それはいいことだ』。 おそらく複雑性理論家は気が狂ったのでしょう」と述べた。 ラーフル・イランゴ、MIT の大学院生で、この分野で最もエキサイティングな最近の成果をいくつか生み出しています。

これらの内向きな質問を研究することで、研究者たちは、計算の難しさを証明する難しさは、一見無関係に見えるかもしれない基本的な質問と密接に結びついていることを学びました。 一見ランダムなデータの中に隠されたパターンを見つけるのはどのくらい難しいでしょうか? そして、本当に難しい問題が存在する場合、それはどれくらいの頻度で難しいのでしょうか?

「メタ複雑性が物事の核心に近いことが明らかになりました」と彼は言いました。 スコットAaronson、テキサス大学オースティン校の複雑性理論家。

これは、研究者を P 対 NP 問題からメタ複雑性に導く長く曲がりくねった道の物語です。 これは簡単な旅ではありませんでした。道には誤った方向転換や障害物が点在し、何度もループして戻ります。 しかし、メタ複雑性の研究者にとって、未知の世界への旅はそれ自体が報酬なのです。 一見単純な質問をし始めます、と言いました バレンタイン・カバネッツ、カナダのサイモン・フレイザー大学の複雑性理論家、そして「どこに行くのか全く分かりません。」

既知の未知数

P 対 NP 問題のパッとしない名前は、計算問題を大まかな「」に分類する複雑性理論家の習慣に由来しています。複雑さのクラス」ナスダックのティッカーシンボルを思わせるラベルが付いています。 計算問題とは、原理的にはアルゴリズム、つまり正確に指定された命令のリストによって解決できる問題です。 しかし、すべてのアルゴリズムが同じように役立つわけではなく、アルゴリズム間の差異は、異なるクラスの問題間の根本的な違いを示唆しています。 複雑さの理論家にとっての課題は、これらのヒントを複雑さのクラス間の関係に関する厳密な定理に変えることです。

これらの関係は、特定のテクノロジーをはるかに超えた、計算に関する不変の真実を反映しています。 「これは宇宙の法則を発見するようなものです」とカバネッツ氏は語った。

「P」と「NP」は、あるグループの最も有名な XNUMX 人のメンバーです。 成長する動物園 何百もの複雑さのクラスからなる。 大まかに言えば、P はリストをアルファベット順に並べるなど、簡単に解決できる問題のクラスです。 NP は、数独パズルのように、簡単に解決策を確認できる問題のクラスです。 簡単に解ける問題はすべてチェックも簡単なので、P の問題は NP にもあります。 しかし、一部の NP 問題は解決するのが難しいように見えます。最初に多くの可能性を試してみなければ、数独パズルの解決策をすぐに直感的に理解することはできません。 もしかしたら、この見かけの難しさは単なる幻想であり、簡単に確認できるすべての問題を解決するための XNUMX つの簡単なトリックがあるということなのでしょうか?

そうであれば、P = NP: XNUMX つのクラスは同等です。 もしそうなら、膨大な数独パズルを解き、世界規模の輸送ルートを最適化し、最先端の暗号を解読し、数学の定理の証明を自動化することを簡単にする何らかのアルゴリズムが存在するはずです。 P ≠ NP の場合、原理的に解決できる多くの計算問題は、実際には永遠に私たちの理解を超えたままになります。

研究者たちは、P 対 NP の問題が初めて明確になるずっと前、実際、現代のコンピューター サイエンスが始まるずっと前から、形式的な数学的推論の限界について懸念していました。 1921 年、数学者のデヴィッド ヒルベルトは、ほぼ XNUMX 世紀後にカルモジーノの注意を引くことになる同じ疑問に悩んで、数学を絶対的な確実性で基礎付けるための研究プログラムを提案しました。 彼は、公理と呼ばれるいくつかの単純な仮定から出発して、XNUMX つの重要な基準を満たす統一された数学理論を導き出すことを望んでいました。

ヒルベルトの最初の条件である一貫性は、数学に矛盾がないという必須の要件でした。同じ公理から出発して 1930 つの矛盾する命題が証明できた場合、理論全体は修復不可能になります。 しかし、理論に矛盾がなくても、その範囲は依然として限られている可能性があります。 それがヒルベルトの XNUMX 番目の条件、完全性、つまりすべての数学的記述が証明可能に真であるか、証明可能に偽であるという要件の動機でした。 彼の XNUMX 番目の基準である決定可能性は、数学的記述が真か偽かを決定するための明確な機械的手順を要求しました。 XNUMX年の会議で演説したヒルベルトは、「我々のスローガンは『我々は知らなければならない、我々は知るだろう』である」と宣言した。

わずかXNUMX年後、ゲーデルはヒルベルトの夢に最初の一撃を与えた。 彼 証明 「このステートメントは証明不可能である」のような自滅的なステートメントは、適切な一連の公理から導き出すことができるということです。 そのようなステートメントが本当に証明できない場合、理論は不完全ですが、証明できる場合、理論は矛盾しており、さらに悪い結果になります。 同じ論文の中で、ゲーデルはまた、いかなる数学理論もそれ自体の一貫性を証明することはできないことを証明しました。

研究者らは、将来の数学理論は、必ずしも不完全なものではあるが、それでも決定可能であることが証明されるかもしれないという希望を抱いていた。 おそらく、ゲーデルのような厄介な命題を避けながら、証明可能なすべての命題を特定する手順を開発できるかもしれない。 問題は、これらの仮説的な手順を推論する方法を誰も知らなかったことです。

そして 1936 年に、アラン チューリングという名前の 23 歳の大学院生が、ヒルベルトの決定可能性の条件を当時馴染みのなかった計算言語で言い換え、致命的な打撃を与えました。 チューリングは数学モデルを定式化しました。現在では、 チューリングマシン — これは考えられるすべてのアルゴリズムを表すことができ、ヒルベルトの手順が存在する場合、それがこのモデルに適合することを示しました。 その後、彼はゲーデルのような自己言及的な方法を使用して、 証拠 決定不可能なステートメントの存在、または同様に、どのアルゴリズムも解決できない計算不可能な問題の存在。

ヒルベルトのプログラムは廃墟となっていました。何を証明できるか、何を計算できるかについては、根本的な制限が永久に存在することになります。 しかし、コンピューターが理論的な抽象概念から実際の機械に進化するにつれて、研究者たちは、チューリングによる解決可能な問題と解決不可能な問題の単純な区別では多くの疑問が未解決のままであることに気づきました。

1960 年代までに、コンピュータ科学者はいくつかの問題を解決するための高速アルゴリズムを開発しましたが、他の問題については、既知のアルゴリズムしか知られておらず、耐え難いほど遅かったです。 問題が解決可能かどうかだけではなく、解決がどれほど難しいかが問題だったらどうでしょうか?

「豊富な理論が浮かび上がってきましたが、もはや答えはわかりません」とカルモシーノ氏は言う。

分岐経路

硬度に関する質問がいかに複雑であるかを説明するために、グラフを含む密接に関連した XNUMX つの問題を考えてみましょう。 これらは、ノードと呼ばれる点のネットワークであり、エッジと呼ばれる線で接続されています。 コンピューター科学者はこれらを使用して、あらゆるものをモデル化します。 量子計算 トラフィックの流れ.

グラフが与えられ、ハミルトニアン パスと呼ばれるもの、つまりすべてのノードを XNUMX 回だけ通過するルートを見つけるように求められたとします。 この問題は原理的には明らかに解決可能です。考えられるパスの数は有限であるため、他のすべてが失敗した場合は、それぞれをチェックするだけで済みます。 ノードが数個しかない場合は問題ありませんが、グラフがわずかに大きい場合でも可能性の数は制御不能になり、この単純なアルゴリズムはすぐに役に立たなくなります。

より優れた戦いを繰り広げる、より洗練されたハミルトニアン パス アルゴリズムがありますが、アルゴリズムが問題を解決するのに必要な時間は、グラフのサイズに応じて常に指数関数的に増加します。 グラフがそれほど大きくなくても、研究者が発見した最高のアルゴリズムでも「妥当な時間内に」パスを見つけることができないと同氏は述べた。 ラッセルインパリアッツォ、カリフォルニア大学サンディエゴ校の複雑性理論家。 「そして、『妥当な時間』とは、『宇宙が終わる前』を意味します。」

ハミルトン経路問題には、別の興味深い特性があります。 誰かが特定のグラフ上でハミルトニアン パスを見つけたと主張した場合、グラフが非常に大きい場合でも、解が有効かどうかをすぐに確認できます。 必要なのは、パスに従ってノードを XNUMX つずつチェックし、どのノードも XNUMX 回チェックしていないことを確認することだけです。 最後に欠落しているノードがない場合、パスはハミルトニアンです。

このソリューション チェック アルゴリズムの実行に必要な時間は、グラフのサイズに比例します。 これは、多項式アルゴリズムのより広いカテゴリに分類され、グラフ サイズの多項式関数に応じて実行時間が増加します。 多項式の増加は指数関数的な増加に比べて穏やかであるため、多項式アルゴリズムは大きなグラフでも引き続き実行可能です。 「劇的に効率が向上しました」とカルモシーノ氏は言う。

ハミルトニアン パス問題には明らかな非対称性があります。高速な多項式アルゴリズムを使用して正しい解を検証できますが、解を見つけるには低速な指数アルゴリズムが必要になります。 この非対称性は驚くべきことではないように思えるかもしれません。芸術的傑作を創作するよりもそれを認識するほうが簡単で、新しい定理を証明するよりも数学的証明をチェックするほうが簡単です。ただし、すべての計算問題がこの非対称性を持っているわけではありません。 実際、ハミルトニアン経路を見つけることによく似た問題は、まったく異なる動作をします。

再びグラフが与えられ、すべてのエッジを XNUMX 回正確に横切る「オイラー パス」を見つけるように求められたとします。 繰り返しますが、考えられる解決策をチェックするための多項式アルゴリズムがありますが、今回は問題を解決するための多項式アルゴリズムもあります。 ここには非対称性はありません。 複雑さの理論では、一部のパスは他のパスよりも見つけやすいように見えます。

ハミルトニアン経路問題とオイラー経路問題は両方とも複雑度クラス NP に属し、多項式アルゴリズムによって解をチェックできるすべての問題を含むように定義されています。 オイラー経路問題も多項式アルゴリズムで解決できるためクラス P に分類されますが、どう見てもハミルトニアン経路問題には当てはまりません。 表面的には非常に似ているこれら XNUMX つのグラフ問題が、なぜこれほど劇的に異なるのでしょうか? それが P 対 NP 問題の本質です。

普遍的に難しい

当初、複雑さのクラスは、類似しているが直接関連していない問題を分類するための便利なカテゴリのように見えました。ハミルトン経路の発見が他の難しい計算問題と何らかの関係があるとは誰も疑っていませんでした。

そして1971年、米国での在職権を拒否されトロント大学に移ってからXNUMX年も経たないうちに、複雑性理論家の彼は スティーブンクック 公表 驚くべき結果。 彼は、奇妙な特徴を持つ特定の NP 問題を特定しました。その問題を解決できる多項式アルゴリズムがあれば、NP の他のすべての問題も解決できます。 クックの「普遍的な」問題は、明らかに難しい問題のクラスを支え、以下の簡単な問題から分離する一本の柱であるように見えました。 その XNUMX つの問題を解決すれば、残りの NP は崩壊します。

クック氏は、彼の普遍的な問題に対して高速なアルゴリズムは存在しないのではないかと疑っており、論文の途中で同じことを述べ、「この予想を証明するためにかなりの努力を費やす価値があると感じている」と付け加えた。 「かなりの努力」という言葉は控えめな表現だろう。

同じ頃、ソ連の大学院生が、 しし座レビン を証明した 同様の結果ただし、彼がいくつかの異なる普遍的な問題を特定したことを除いて。 さらに、アメリカの複雑性理論家は、 リチャード・カープ 証明 クック（そしてレビン、ただしカープとクックは数年後までレビンの研究を知りませんでした）によって特定された普遍性の性質は、それ自体ほぼ普遍的でした。 既知の多項式アルゴリズムのないほぼすべての NP 問題、つまり、難しそうに見える簡単にチェックできる問題のほぼすべてが同じ特性を持っており、これは NP 完全性として知られるようになりました。

これは、ハミルトニアン経路問題、数独、および 数千 他人の — 正確な意味では同等です。 「さまざまな自然なタスクがすべてありますが、それらはすべて魔法のように同じタスクであることがわかります」とイランゴ氏は言いました。 「そして、同じことが可能かどうかはまだわかりません。」

NP 完全問題の難易度を解決するだけで、P 対 NP の問題を解決できます。 P ≠ NP の場合、簡単な問題と難しい問題の区別は、すべて同じ強度の何千もの列によって保持されます。 P = NP の場合、建物全体が崩壊の危機に瀕しており、ただ XNUMX つの破片が落下するのを待っていることになります。

クック、レビン、カープは、多くの無関係に見える問題を統合しました。 さて、複雑性理論家がしなければならないのは、P = NP かどうかという XNUMX つの問題を解決することだけでした。

XNUMX年経った今でも、この疑問は答えられていない。 カバネットは、計算の限界について推論することを、全体像をまったく理解せずに広大な領域を調査することに例えました。 無限の計算能力を持つ存在は、山頂から見下ろし、風景全体を一度に取り込むことができますが、単なる定命の者にはそのような利点を当てにすることはできません。 「山のふもとにいる私たちは、より良い景色を求めて飛び跳ねてみてもいいかもしれません」と彼は言いました。

P = NP であると仮定します。 それを証明するには、研究者は NP 完全問題の高速アルゴリズムを見つける必要がありますが、そのアルゴリズムは広大な風景の目立たない隅に隠れている可能性があります。 彼らがそれをすぐに見つけられるという保証はありません: 複雑性理論家は時々 発見 一見難しい (NP 完全ではないが) 問題に対して、数十年の研究を経て初めて解決される独創的なアルゴリズム。

ここで、P ≠ NP と仮定します。 それを証明するのはさらに難しいようです。 複雑性理論の専門家は、将来のすべての研究者の最善の努力を効果的に予測し、妨害する高速アルゴリズムは存在し得ないことを確立する必要があります。

どこから始めればよいかわからないことが問題の一部です。 しかし、研究者たちが試していないわけではない。 何十年にもわたって、彼らはさまざまな角度からこの問題に取り組み、あらゆる場面で道が塞がれていることに気づきました。 「これは、理論的なコンピューターサイエンスにおける最も明白な真実の XNUMX つです」とカルモシーノ氏は言います。 「これほど永続的な現象が発生すると、何らかの説明が必要になります。」

カルモシーノは大学の最終年までに、好奇心がゲーデルから複雑性理論の大学院コースに進みました。 彼は、自分が情熱を注いでいたプロジェクト、つまりおとぎ話の物語構造を学習して新しいものを生成するコンピュータ プログラムよりも宿題に多くの時間を費やしていることに気づき、驚きました。

「『わあ、これは真剣に受け止めなければいけない』と思いました」とカルモシーノさんは振り返る。 やがて、彼はこのテーマに夢中になり、指導教員が卒業後の計画を再考するよう優しく勧めました。

「彼はこう言いました。『もしこれを続けたいなら、理論的なコンピューターサイエンスと複雑さの理論を続けたいなら、できるよ。それは大学院と呼ばれるものだよ』」とカルモシーノ氏は語った。 修士号を取得した後、2012 年にサンディエゴに移り、インパリアッツォの監督下で博士号取得を目指しました。

カルモシーノの最初の主な目標は、 画期的な紙 XNUMX年前に彼の想像力を掻き立てたものでした。 複雑性理論家によるその論文 アレクサンダー・ラズボロフ および スティーブン・ルディッチは、P ≠ NP を証明するための特定の「自然な」戦略は、ほぼ確実に失敗することを示しました。成功には、研​​究者が非常に可能性が低いと考えていた暗号の完全な破壊という莫大なコストがかかるからです。 研究者らは、ラズボロフとルーディッチの結果が、P ≠ NP を証明するこの一般的なアプローチに対する障壁であると解釈しました。

この「自然証明の障壁」は、複雑性理論における未解決の問題を解決するための多くの既知の障壁の XNUMX つにすぎません。 それぞれが障害物のように機能し、一見有望な道が実は行き止まりであることを警告します。 これらの障壁を総合すると、P 対 NP の問題を解決する証明は、過去に使用されたものとは根本的に異なるものでなければならないことを示しています。 ほとんどの研究者が、解決策はまだ遠いと信じているのはこのためです。 しかし、少なくとも障壁は、見てはいけない場所を彼らに教えてくれます。

「複雑性理論は呪われていると同時に、非常に多くの障壁に恵まれています」とイランゴ氏は言う。

カルモシーノが自然の証拠の障壁に遭遇したときまでに、それは 20 年近く経過していました。 しかし、彼はそれが研究者にとってさらに多くの教訓をもたらすのではないかと考えた。 その気持ちは、ある日、彼と XNUMX 人の同僚がメタ複雑性の観点から自然証明の障壁を調べることによって驚くべき結果を証明したときに証明されるでしょう。 彼らの証明は、メタ複雑性への新たな関心を引き起こし、過去数年間の飛躍的な進歩につながった数少ない主要な成果の XNUMX つでした。

しかし、自然証明の障壁からメタ複雑性までの軌跡をたどるには、研究者が最初に P 対 NP 問題に取り組み始めた 1970 年代に研究者たちが出発した場所に戻る必要があります。 問題を証明することがこれほど難しいのはなぜでしょうか?

回り道

最初、研究者たちは、チューリングがいくつかの問題がいかなるアルゴリズムによっても解けないことを証明するために使用した手法のバリエーションを使用して、P ≠ NP を証明しようとしました。つまり、一部の NP 問題は、どのような多項式アルゴリズムによっても解けないことを証明しようとしました。 。 しかし、彼らはすぐに 発見 これらの方法が機能しないという証拠は、P 対 NP の問題を解決するための最初の大きな障壁です。 そこで彼らは別のアプローチを探し始め、すぐにチューリングの同時代の作品の中にそのアプローチを見つけました。 クロード・シャノン.

ミシガン州北部の小さな町で育ったシャ​​ノンさんは、情報化時代の到来を告げる人物とは思えなかった。 しかし、彼は、電気工学と数理論理学にも同様に親しみを感じ、コンピュータ サイエンスという新興分​​野の学際的な性質を体現しました。 彼の中で 修士論文、シャノンは、電気機械スイッチで作られた回路が、ブール変数、つまり 1 つの値のみ (true か false、または 0 と XNUMX など) を取ることができる量を含む論理式をどのように表現できるかを示しました。

これらの式では、ブール変数は「論理ゲート」AND、OR、NOT によって相互にリンクされます。 たとえば、基本式 A AND B は、A と B の両方が true の場合は true、それ以外の場合は false になります。 一方、A OR B は、XNUMX つの変数のうち少なくとも XNUMX つが true の場合に true になります。 NOT ゲートはさらに単純です。単一の変数の値を反転します。 これらの基本的な構成要素が十分にあれば、あらゆる計算を実行できます。

「一日の終わりにコンピューターを見るとき、それは何をしているのでしょうか? サーキットを走っているんです」とイランゴ氏は語った。

シャノンの研究は、問題の回路が単なる数学的抽象概念であるにもかかわらず、理論家が「回路の複雑さ」と呼ばれる計算問題の難しさを考えるための新しい方法を提案しました。 しばらくの間、研究者らはこのアプローチが P 対 NP を解決する方法である可能性があると考えましたが、最終的にはその道が自然の証明の壁にぶつかりました。

回路の複雑さのフレームワークでは、チューリングの計算モデルの最も基本的な概念を再考する必要があります。 ここでは、計算問題とそれを解決するアルゴリズムの代わりに、研究者はブール関数とそれを計算する回路を検討します。 ブール関数は、ブール変数 (true と false、1 と 0) を取り込み、true または false、1 または 0 を出力します。また、アルゴリズムと同様に、回路は、任意の入力が与えられた場合に出力を生成する手順を記述します。

「人々が回路の複雑さに取り組み始めたのは、チューリングマシンが複雑すぎると判断したからだと私は理解しています」と氏は述べた。 ライアン·ウィリアムズ、MITの複雑性理論家。 「回路をゲートごとに研究できます。」

特定の計算問題を解決するためのアルゴリズムが多数存在し、そのいくつかが他のものよりも高速であるのと同様に、多くの異なる回路が特定のブール関数を計算でき、その中には他の回路よりもゲート数が少ないものもあります。 研究者は、関数の回路の複雑さを、それを計算する最小の回路内のゲートの総数として定義します。 入力変数の数が固定された関数の場合、回路の複雑さも固定数であり、一部の関数では他の関数よりも高くなります。

しかし、多くの場合、より大きなグラフを考慮することでハミルトニアン パス問題を難しくできるのと同様に、入力変数の数を増やすことで同じ関数のより複雑なバージョンを検討できます。 次に研究者は、アルゴリズムの実行時間を研究するときに抱くのと同じ質問を検討します。ブール関数の計算に必要な最小ゲート数は、入力変数の数が増加するにつれて多項式または指数関数的に増加しますか? 研究者は、これら XNUMX つのカテゴリの関数をそれぞれ「計算が簡単」および「計算が難しい」と呼んでいます。

計算が簡単なブール関数は、クラス P の計算問題に似ており、多項式時間で実行されるアルゴリズムによって解決できます。 しかし、ハード NP 問題に類似した関数もあります。研究者が発見した、段階的に大きくなるバージョンを計算する最良の方法では、指数関数的に増加するゲート数が必要ですが、答えは簡単に確認できます。 もし複雑性理論の専門家が、このような関数を計算するのにこれより良い方法はないことを証明できれば、それは P ≠ NP を意味するでしょう。

これは、1980 年代にほとんどの複雑性理論家が追求した戦略でした。 そして勝算は彼らに味方した。 シャノンは持っていた 証明 1949 年には、ほぼすべてのブール真理値表 (固定サイズのブール関数のすべての可能な入出力の長いリスト) は、実質的に可能な限り高い回路の複雑さを持っていることがわかりました。 彼は驚くほど単純な議論を使用しました。つまり、少数のゲートを組み合わせる方法は、多数のゲートを組み合わせる方法よりもはるかに少ないのです。

「周回するのに十分な小さなサーキットがありません」とアーロンソンは言いました。

そのため、複雑性理論家たちは奇妙な状況に陥っていることに気づきました。 ほぼすべての真理値表の回路の複雑さが高い場合、ほぼすべてのブール関数の計算が困難になるはずです。 研究者は、クラス NP に含まれることが知られているそのような関数を XNUMX つ特定するだけで済みました。 それはどれほど難しいでしょうか？

クリプトブラザーズ

最初は進歩が早かったです。 1981年、シプサーとXNUMX人の協力者 証明 ゲートの配置方法に特定の制限がある回路を使用した場合、特定のブール関数の計算は間違いなく困難であることがわかりました。

「これらの制限されたモデルについて何かを証明し、学んだことを基にして、より少ない制限で動作できるようになるという空想がありました」とシプサー氏は語った。

1985 年、ラズボロフは次の大きな一歩を踏み出しました。 彼はモスクワの大学院に入学したばかりで、数学の別の分野の問題に取り組んでいたときに偶然この取り組みに参加しました。そこで、P 対 NP 問題を解決することが前提条件であることが判明しました。

「この問題がどれほど難しいかを知らなかったのが本当に幸運でした」とラズボロフ氏は語った。 「もしそうでなかったら、私は始めさえしなかったかもしれません。」

ラズボロフは、AND ゲートと OR ゲートのみを含む回路を分析しました。 証明 ゲートがどのように配置されていても、そのような回路を使用して特定の関数を計算するのは困難です。さらに、その関数は NP 完全であることが知られていました。 P 対 NP を解決するために研究者がしなければならなかったのは、ラズボロフの技術を NOT ゲートを備えた回路に拡張することだけでした。

「あと一歩、あと一撃、そうすれば勝てるという、ある種の普遍的な感覚があった」とラズボロフは語った。 しかし、それは起こりませんでした。 ラズボロフ自身は、NOT ゲートがミックスに追加されれば彼の手法は失敗し、誰も別の方法を見つけることができないことを証明しました。 年が経つにつれ、彼はなぜ道が途絶えてしまったのか疑問に思うようになった。

米国でも、ルーディッチは同じ疑問を考えていました。 彼とインパリアッツォは大学の同級生で、一緒に大学院に進学した。 彼らの友情は、ゲーデルとチューリングの自己参照証明と、それらが数学とコンピューター サイエンスの基礎に与える影響に対する共通の関心によって引き起こされました。

「私たちの冗談は、『自己言及』と書かれたボタンを手に入れるつもりだったということです」とインパリアッツォ氏は語った。

大学院生として、ルーディッチとインパリアッツォは両方とも、P ≠ NP を証明しようとする際におそらく最も実践的な動機となる暗号の複雑性理論の基礎に取り組みました。 暗号学者は、秘密のメッセージを「疑似ランダム性」で覆い隠します。この方法で暗号化されたメッセージは、盗聴者にとってはランダムな数字の寄せ集めのように見えますが、それでも、意図した受信者によって解読される可能性があります。 しかし、盗聴者が暗号を解読するのが非常に難しいとどうやって確信できるでしょうか?

ここで複雑性理論が登場します。現在最も広く使用されている暗号化方法はすべて、一見難しい NP 問題に基づいています。攻撃者がメッセージを復号するには、問題を解決するためのまだ発見されていない高速アルゴリズムが必要です。 これらのメソッドが本当に安全であることを証明するには、P ≠ NP を証明する必要があります。 証拠がなければ、できることは「秘密を守ろうとしている相手が自分より優れた数学者ではないことを祈ることだけ」だとシプサー氏は言う。

暗号はそれ自体魅力的ではありますが、最初にルーディッチとインパリアッツォをこの分野に引き込んだ自己言及的な議論からは遠く離れているように見えました。 しかし、回路の複雑さへのアプローチが行き詰まった理由を理解するのに苦労するうちに、結局のところ、この XNUMX つの主題はそれほど遠く離れていないことに気づき始めました。 P ≠ NP を証明する試みで研究者が採用した戦略には、ゲーデルの有名な命題「この命題は証明できない」を彷彿とさせる自滅的な性格があり、暗号化はその理由を説明するのに役立つ可能性があります。 ロシアでも、ラズボロフは同時期に同様の関連性を発見した。 それが自然の証結界の種だった。

自然証明の障壁の中心にある緊張は、複雑性の高い関数と複雑性の低い関数を区別するタスクが、メッセージの暗号化に使用される擬似ランダム性から真のランダム性を区別するタスクに似ているということです。 P ≠ NP を証明するために、高複雑度の関数は低複雑度の関数とは決定的に異なることを示したいと思います。 しかし、私たちはまた、擬似ランダム性がランダム性と区別できないようにし、暗号化のセキュリティに自信を持てるようにしたいと考えています。 もしかしたら、両方の方法を取り入れることはできないかもしれません。

残酷なジョーク

1994 年、ラズボロフとルーディッチは、似たような洞察を思いついたことに気づき、その結果を組み合わせるために協力し始めました。 彼らはまず、回路の複雑さを利用して P ≠ NP を証明するこれまでのすべての試みが、同じ一般的な戦略を採用していたことに気づきました。つまり、NP 完全ブール関数の特殊な特性を特定し、その特性を共有できる計算が容易な関数が存在しないことを証明するというものです。 これは、選択された NP 完全関数の計算が本当に困難であることを示し、P ≠ NP を証明します。

シプサー、ラズボロフらは、これと同じ戦略を使用して、より限定的な結果を証明することに成功しており、いずれの場合も、研究者が特定した特別な特性は、ほとんどのブール関数で共有されていました。 ラズボロフとルディッチは、単に既知の代替手段がなかったため、財産が広く共有されたこのケースを指すために「自然証拠」という用語を作りました。 もし「不自然な」証明が可能であれば、それは非常に直観に反するものであり、その名に値するものでなければなりません。

次に、ラズボロフとルーディッチは主な結果を証明しました。P ≠ NP の自然な証明には、計算しやすい関数と計算しにくい関数がどのように異なるのかについての非常に包括的な理解が必要であり、その知識はまた、簡単な関数を見つけるための高速アルゴリズムを促進する可能性があります。 -表面的に複雑であっても関数を計算します。 もし複雑性理論家が P ≠ NP の自然な証明に成功していれば、任意の真理値表を一目見て、対応する関数の回路複雑性が高いか低いかを判断する、ほぼ確実な方法を発見したでしょう。これは、以前よりもはるかに強力で一般的な結果です。彼らは証明しようとしていたのです。

「交渉した以上のものを手に入れずにはいられないのです」とカルモシーノ氏は言う。

それはあたかも特定の発言を事実確認しようとしたが、すべての試みが汎用の嘘発見器の青写真になってしまったようなもので、真実であるにはあまりにも出来すぎているように思えます。 複雑さの理論家にとっても、自然証明の驚くべき力により、成功の可能性は低くなったように思えました。 しかし、そのような証明が成功した場合、回路の複雑さと擬似乱数の間には関係があるため、予期せぬ結果が暗号学にとって悪いニュースとなるでしょう。

この関係を理解するには、多くの入力変数を持つブール関数の真理値表の出力列を見て、すべての「true」を 1 に置き換え、すべての「false」を 0 に置き換えることを想像してください。

ブール関数の回路の複雑さが高い場合、その長い出力リストは原則として、真にランダムな 0 と 1 の文字列 (たとえば、コインを繰り返し投げることによって得られる文字列) と区別がつきません。 ただし、関数の回路の複雑さが低い場合は、文字列が複雑に見えても、単純で簡潔な説明が必要です。 そのため、暗号化で使用される擬似ランダム文字列に非常に似ています。その簡潔な説明は、見かけのランダム性に埋め込まれた秘密メッセージです。

したがって、ラズボロフとルーディッチの結果は、P ≠ NP の自然な証明によって、隠されたメッセージを含む擬似ランダム文字列と真にランダムな文字列を区別できる高速アルゴリズムも生成されることを示しました。 安全な暗号化は不可能です。研究者が P ≠ NP を証明することで確立したいと考えていたこととはまったく逆です。

一方、安全な暗号化が可能であれば、安全な暗号化の前提条件である P ≠ NP を証明するための自然証明は実行可能な戦略ではありません。 一言で言えば、それが自然の証明の障壁です。 あたかも複雑性理論家が残酷なジョークにさらされているかのように見えました。

「硬度を信じるなら、硬度を証明するのは難しいと信じるべきです」とカバネッツ氏は言う。

メタバースへ

P ≠ NP 予想の意味とそれを証明する難しさの間の関係は興味深いものでしたが、特定するのは困難でした。 まず、自然証明の障壁は、P ≠ NP を証明する XNUMX つのアプローチをブロックしただけです。 もう XNUMX つは、P ≠ NP を証明することの難しさを、P ≠ NP 自体ではなく、安全な暗号の存在と結び付けました。これは密接に関連していますが、完全に同等ではない問題です。 この関係を真に理解するには、研究者はメタ複雑さに慣れる必要があります。

「『ああ、P ≠ NP なので、P ≠ NP を証明するのは難しい』という直感があります」とウィリアムズ氏は言う。 「しかし、この直感を理解するには、P ≠ NP のようなものを計算問題として証明するというタスクについて考え始める必要があります。」

それがカバネッツが大学院生としてやったことだ。 彼はウクライナで育ち、ソ連崩壊の XNUMX 年後にコンピュータ サイエンスの学部を卒業しました。 その後の混乱の中で、彼は最も興味のある理論的テーマを追求する機会がほとんどありませんでした。

「もっと学術的なことがやりたかった」とカバネッツさんは振り返る。 「そして、世界を見ることにも興味がありました。」 彼は大学院進学のためにカナダに移り、そこで自然証明バリアについて学びました。 カルモシーノと同様、カバネッツもこの結果に衝撃を受けた。 「あなたがこのようなつながりを持っていることは非常に深いように思えました」と彼は言いました。

2000 年、大学院時代の終わりに近づいた頃、彼は人との会話の中で自然証明の壁が常に話題になることに気づきました。 カイ・ジンイー、当時サバティカルでトロントを訪れていた複雑理論者。 彼らは、この障壁を障害ではなく招待状、つまり問題を証明することがどれほど難しいかを正確に調査する機会であると考えるようになりました。 の 紙 彼らがこの新しい視点を提示したこの作品は、メタ複雑性の初期の分野において最も影響力のある初期の作品の XNUMX つとなるでしょう。

Kabanets と Cai の論文は、Razborov と Rudich による自然証明障壁の定式化に暗黙的に含まれる計算上の問題を強調しました。つまり、ブール関数の真理値表が与えられた場合、回路の複雑さが高いか低いかを判断します。 彼らはこれを最小回路サイズ問題 (MCSP) と呼びました。

MCSP は典型的なメタ複雑性問題です。つまり、グラフ理論や別の外部トピックではなく、複雑性理論自体を主題とする計算問題です。 実際、これは、1980 年代に回路複雑性アプローチを使用して複雑性理論家が P 対 NP に取り組むように駆り立てた質問の定量版のようなものです。どのブール関数が計算するのが難しく、どれが簡単ですか?

「私たちが MCSP アルゴリズムを思いついたとしたら、それは複雑性理論で行っていることを自動化する方法のようなものになるでしょう」と Impagliazzo 氏は言います。 「少なくとも、私たちの仕事をより良くする方法について、大きな洞察が得られるはずです。」

複雑性理論家は、この魔法のようなアルゴリズムによって仕事がなくなることを心配していません。彼らは、そのようなアルゴリズムが存在するとはまったく思っていません。というのも、ラズボロフとルーディッチは、複雑性の高い真理値表と複雑性の低い真理値表を区別するためのそのようなアルゴリズムが暗号化を可能にすることを示したからです。不可能。 つまり、MCSP は難しい計算問題である可能性が高いということです。 しかし、それはどれほど難しいでしょうか？ それは、ハミルトニアン経路問題や 1960 年代に研究者が苦労した他のほぼすべての問題と同様に、NP 完全なのでしょうか?

NPの問題は「どのくらい難しいですか？」 通常は簡単に答えることができますが、MCSP は奇妙な外れ値のように思えました。 「たとえ難しそうに見えても、この NP 完全問題に関連していない『浮遊』問題はほとんどありません」と Kabanets 氏は言いました。

カバネッツは、自分とカイがMCSPと名付けたこの問題を最初に検討したわけではないことを知っていた。 ソ連の数学者は、さまざまな計算問題の本質的な難しさを理解する初期の試みとして、1950 年代から非常によく似た問題を研究していました。 レオニード・レビンは、1960 年代後半に NP 完全性の理論となる理論を開発する際にこの問題に取り組んでいましたが、NP 完全性を証明できず、独創的な論文をそれなしで発表しました。

その後、カバネッツ氏とカイ氏が自然証明障壁との関係に注目するまで、この問題は 30 年間ほとんど注目されませんでした。 Kabanets は、自分自身でこの問題を解決することを期待していませんでした。代わりに、計算の難易度に関するこの一見難しい問題が実際には難しいことを証明することがなぜそれほど難しいのかを探りたかったのです。

「それはある意味、メタメタ複雑さです」と彼は言った。 ラフル・サンタナム、オックスフォード大学の複雑性理論家。

しかし、それはずっと硬度が低かったのでしょうか、それとも研究者がなぜMCSPがNP完全であることを証明することに成功しなかったのかを理解する少なくとも何らかの方法はあったのでしょうか? Kabanets は、はい、理由があることを発見しました。回路の複雑さを理解することの難しさは、MCSP の NP 完全性を証明するための既知の戦略にとって障壁のように機能します。この問題自体が、回路の複雑さを理解することの難しさに関するものです。 自然の証明の壁によるねじれた自滅的な論理は避けられないように見えました。

MCSP が NP 完全ではない可能性もありますが、それも可能性は低いようです。問題のより単純な変種は NP 完全であることがすでに知られています。

「私たちが研究している他のすべての問題に直接関連する、それを置くのに適した場所がありません」とインパリアッツォ氏は語った。

カバネッツは MCSP の奇妙な行動を解明しましたが、彼はさらに進歩する方法を知りませんでした。 メタ複雑性の研究は徐々に遅くなりました。 16 年後、研究者らが別の基本的な質問との驚くべき関連性を発見したとき、この問題は再び栄えました。それは、ほとんどの場合正しい答えを得る事だけを気にしている場合、問題を解決するのはどれほど難しいでしょうか?

宇宙戦争

日常的な問題については、ほとんどの場合に役立つ答えで十分であることがよくあります。 私たちは、最悪のシナリオではなく、典型的な交通パターンに合わせて通勤計画を立てます。

ほとんどの複雑性理論家は満足することが困難です。彼らは、考えられるすべての入力に対して正しい答えを得る高速なアルゴリズムを見つけることができれば、問題が簡単であると宣言するだけで満足します。 その標準的なアプローチでは、研究者が「最悪の場合」と呼ぶ複雑さに従って問題を分類します。 しかし、「平均的な場合」の複雑さの理論もあり、ほとんどの入力に対して正しい答えを得る高速なアルゴリズムが存在する場合、問題は簡単であると考えられます。

この区別は暗号学者にとって重要です。 最適なアルゴリズムが失敗するいくつかの頑固なケースを除いて、ほぼすべての入力に対して簡単に解決できる計算問題を想像してください。 最悪の場合の複雑さの理論では、これは難しい問題であると考えられていますが、暗号化にとっては役に立ちません。メッセージの一部だけが解読できない場合、何の意味があるのでしょうか?

実際、NP 完全性に関する彼の先駆的な研究の 1972 年後、平均ケースの複雑さの厳密な研究を開始したのはレビンでした。 それまでの数年間、彼はソ連当局と衝突していた。彼は不遜なトラブルメーカーであり、時折所属する共産党青年グループの愛国的活動を損なうこともあった。 XNUMX年、彼は明らかに政治的な理由で博士号を取得しなかった。

「若い研究者としてソ連で成功するには、あまり自分の意見を主張することはできないし、レオニードが自分の意見を持たないなんて想像するのも難しい」とインパリアッツォ氏は語った。

レビンは 1978 年に米国に移住し、1980 年代半ばに平均的な症例の複雑さに注目しました。 彼は理論をさらに発展させるために、当時大学院生だったインパリアッツォを含む他の人々と協力し始めました。 しかし、研究が進んでいるにもかかわらず、インパリアッツォ氏は研究者たちが互いにすれ違うことがよくあることに気づきました。 彼は全員に同じ認識を持ってもらいたかったが、レビンの論文が簡潔であることで有名だったことが役に立たなかった。 フィールドを始めた 平均的なケースの複雑さは XNUMX ページ未満でした。

「レオニードの作品を​​、より親しみやすい専門用語に翻訳するつもりでした」とインパリアッツォ氏は語った。 彼は、数学に入る前に、全体像を短く遊び心のある概要から始めることにしました。 「そのようなことが新聞を席巻しましたが、とにかく誰もが覚えている唯一の部分です。」

　 紙1995年に出版され、すぐに古典になりました。 インパリアッツォは風変わりな名前を付けました XNUMXつの世界 計算の難易度の違いと暗号化機能の違いによって区別されます。 私たちはこれらの世界のいずれかに住んでいますが、どれであるかはわかりません。

インパリアッツォの論文が発表されて以来、研究者たちは彼のミニチュア多元世界の一部を削除すること、つまり一部の世界が結局は不可能であることを証明することで可能性の空間を狭めることを夢見てきた。 XNUMX つの世界は特に魅力的なターゲットです。それは、P ≠ NP であっても暗号化が不可能な世界です。

これらの世界の XNUMX つである Heuristica では、すべての NP 完全問題はほとんどの入力で簡単に解決できますが、高速アルゴリズムは時折間違いを犯すため、これらの問題は最悪の場合の複雑さの理論の基準では依然として難しいと考えられています。 ここは、ほとんどすべての暗号が簡単に解読されてしまうため、暗号化が不可能な世界です。 ペシランドと呼ばれる別の世界では、別の理由で暗号化は不可能です。平均的な意味ですべての問題は困難ですが、メッセージを暗号化すると、意図した受信者にとっても判読できなくなります。

これら XNUMX つの世界は、メタ複雑性の問題と密接に関係していることが判明しました。特に、Heuristica の運命は、MCSP が NP 完全であるかどうかという長年の問題と関連しています。 昔、カバネたちを魅了し、レビンを悩ませたこの疑問は、単なる好奇心ではありません。世界全体が危機に瀕しているのです。

ヒューリスティカを除外するには、研究者は、最悪の場合の複雑さと平均的な場合の複雑さの区別を崩壊させる必要があります。つまり、ほとんどの入力で NP 完全問題を正しく解決する仮説アルゴリズムが実際にそれを解決できることを証明する必要があります。すべての場合において。 最悪ケースから平均ケースへの削減と呼ばれるこの種の関係は、特定の問題に対して存在することが知られていますが、それらはどれも NP 完全ではないため、これらの結果はより一般的なものを示唆するものではありません。 Heuristica を廃止すると、暗号学者は P ≠ NP という XNUMX つの仮定に基づいた安全な暗号化の夢を実現するのに半分かかることになります。

しかし、世界を破壊するのは簡単なことではない。 2003 年、XNUMX 人の複雑性理論家が 示されました 既知のNP完全問題に対する最悪ケースから平均ケースへの低減を証明する既存のアプローチは突飛な結果を暗示しており、そのような証明はおそらく不可能であることを示唆しています。

研究者は別のアプローチを見つける必要がありますが、現在では MCSP がまさに必要な問題であるかもしれないと考えています。 しかし、それはXNUMX年以上明らかになることはなかった。 そのつながりを最初に垣間見たのは、マルコ カルモシーノの自然の証明バリアに対する執拗な魅了から現れました。

カルモシーノが初めてメタ複雑性研究に出会ったのは、大学院生のときでした。 2013紙 Kabanets と他の XNUMX 人の研究者によるこの研究は、Kabanet が XNUMX 年以上前に開拓した自然証明バリアへのアプローチをさらに発展させました。 それは、ラズボロフとルーディッチの古典的な論文から学ぶべきことがまだあるという彼の確信を強めただけだった。

「当時、私はその論文に夢中でした」とカルモシーノ氏は語った。 "何も変わっていません。"

その執念は、カリフォルニア大学バークレー校での半年間にわたるワークショップを訪れた際についに実を結び、そこで彼はインパリアッツォ、カバネッツ、そして彼と話すことにほとんどの時間を費やした。 アントニナ・コロコロワ、ニューファンドランド記念大学の複雑性理論家で、2013 年の論文で Kabanets と共同研究しました。 カルモシーノは以前に一度この XNUMX 人と仕事をしたことがあり、その成功したコラボレーションにより、カルモシーノは最も興味を惹かれたテーマについて自信を持って質問を投げかけることができました。

「彼は良い意味で人々を盗んでいました」とカバネッツは回想した。

当初、カルモシーノは、自然証明障壁に関するラズボロフとルーディッチの論文に登場した MCSP のバージョンの NP 完全性を証明するための新しいアイデアを持っていました。 しかし、それらのアイデアは実現しませんでした。 その代わりに、インパリアッツォの突然の発言により、XNUMX 人の研究者は、自然証明の障壁が誰も認識していたよりも強力なアルゴリズムを生み出す可能性があることに気づきました。つまり、障壁には秘密の地図が刻まれていたのです。

で 2016紙XNUMX 人の研究者は、ある種の平均的な MCSP アルゴリズムを使用して、ランダムに見える数字の文字列に隠されたパターンを識別する最悪の場合のアルゴリズムを構築できることを証明しました。これは、コンピューター科学者が「学習」と呼ぶタスクです。 直観的に学習することは、MCSP アルゴリズムによって実行されるバイナリ分類タスク (高複雑性または低複雑性) よりも難しいように見えるため、これは驚くべき結果です。 そして驚くべきことに、あるタスクの最悪の場合の複雑さと、もう一方のタスクの平均的な複雑さが関連付けられました。

「そのようなつながりが存在することはまったく明らかではありませんでした」とインパリアッツォは語った。

MCSP の高速アルゴリズムは、一般的なブール回路に対する純粋な仮説です。反対の証拠がすべてあったにもかかわらず、MCSP が簡単な計算問題であることが判明しない限り、このアルゴリズムは存在できません。つまり、XNUMX 人の研究者の論文が示唆する学習アルゴリズムは次のとおりです。同様に仮説です。

しかし、MCSP の一部の単純なバージョン (回路に特定の制限がある場合に複雑度の高い真理値表と複雑度の低い真理値表を区別する) については、高速アルゴリズムが長年知られています。 Carmosino、Impagliazzo、Kabanets、Kolokolova の論文は、これらのアルゴリズムを、同様に制限されているものの、これまで研究者がこれほど厳密な理論レベルで理解したアルゴリズムよりも強力な学習アルゴリズムに変換できることを示しました。

「どういうわけか、彼らの自己言及的なフレーバーにより、より標準的な問題ではできないように見えることができるようになるのです」とイランゴ氏は言う。

この結果は、他のトピックに取り組んでいる複雑性理論家の注目を集めました。 それはまた、今後数年間に現れるであろうメタ複雑さと平均的なケースの複雑さとの間のさらなるつながりのプレビューでもありました。

何よりも、これは、研究者が、一見進歩を妨げているようにしか見えない障壁について簡単な質問をすることで、どこまで到達できるかを証明するものでした。

「この種の二重性は、少なくとも過去 30 ～ 40 年の複雑さ全体のテーマです」とインパリアッツォ氏は語った。 「障害はしばしばチャンスになる。」

部分クレジット

カルモシーノと彼の同僚が論文を発表して以来、進歩は加速するばかりです。

「新しいことが起こっています」とコロコロワ氏は語った。 「本当に本当に優秀な若手研究者がたくさんいます。」

Ilango はこうした若い研究者の XNUMX 人です。大学院での最初の XNUMX 年間、彼は XNUMX つの戦略を使用して、MCSP の NP 完全性を証明するという未解決の気の遠くなる問題に取り組みました。 簡単な バージョン 回路複雑性の研究者が 1980 年代に P 対 NP を攻撃したときに行ったように、MCSP の NP 完全性も証明しました。 より複雑なバージョン、直感的には難しく見えるため、おそらく難しいことを証明するのが簡単です。

イランゴはメタ複雑性への関心を次のように考えています。 エリック・アレンダー、ラトガース大学の複雑性理論家であり、2000 年代から 2010 年代初頭にかけてメタ複雑性の研究を続けた数少ない研究者の XNUMX 人です。 「彼の熱意は伝わりました」とイランゴ氏は語った。

アレンダーに影響を受けたもう一人の若い研究者は、 平原修一、現在は東京の国立情報学研究所の教授です。 2018年にまだ大学院生だった平原氏は、カルモシーノ氏とその共著者らが発見したメタ複雑性と平均ケース複雑性との関係の真の範囲を明らかにした。 これら XNUMX 人の研究者は、ある問題 (MCSP) の平均的な場合の複雑さと、別の問題 (ブール学習) の最悪の場合の複雑さとの間に関連性を発見しました。 平原氏はさらに技術を発展させ、 派生する MCSP の最悪ケースから平均ケースへの削減。 彼の結果は、カルモシーノ氏らが検討したような仮想的な平均ケースの MCSP アルゴリズムが、実際にはわずかに異なるバージョンの MCSP を間違いなく解くのに十分強力であることを示唆しています。

平原氏の結果は刺激的である。なぜなら、最悪ケースから平均ケースへの低減が知られている他のすべての問題とは異なり、MCSP は NP 完全であると多くの研究者が疑っているからである。 彼らが平原の結果をすべての平均的なケースのアルゴリズムをカバーするように拡張し、MCSP が NP 完全であることを証明できれば、それは私たちがヒューリスティカに住んでいないことを証明するでしょう。

「それはまさに天地を揺るがす結果となるだろう」とサンタナム氏は語った。

MCSP が NP 完全であることを証明するのは難しい課題のように思えるかもしれません。結局のところ、この問題は 50 年以上にわたって未解決のままなのです。 しかし、その後 画期的な 昨年平原氏が発表したところによると、研究者たちは今、数年前に誰もが予想していたよりもはるかに近づいています。

平原氏は、各真理値表の特定のエントリを無視する、部分 MCSP と呼ばれる問題の変形について NP 完全性を証明しました。 彼の証明は、Ilango によって開発された手法に基づいて構築され、部分的な MCSP が、秘密共有と呼ばれる暗号化技術が関与する一見無関係な問題と同等であることを示しました。 これは、暗号化されたメッセージを多くの人に分割して、そのうちの特定の部分が協力した場合にのみメッセージを解読できるようにする方法です。

暗号化の実際のアプリケーションでは、事前にその割合を知りたいと思うでしょうが、追加の暗号トリックの助けを借りて、何人の協力が必要かを把握するだけでも困難なイライラするシナリオを構築できます。 平原氏は、この人為的な暗号問題が NP 完全であることを証明する方法を発見し、その証明が部分 MCSP の NP 完全性も暗示していることを示しました。

この結果は、平原の以前の研究よりもさらにメタ複雑性の研究者たちにエネルギーを与え、他の研究者も注目した。複雑性理論家でブロガーのランス・フォートナウは、それを「メタ複雑性」と名付けた。 今年の結果。 それは、計算問題のそのような「部分関数」バージョンへの取り組みが、他の NP 完全性証明における重要な中間ステップであるためです。

「素晴らしい仕事だ」とウィリアムズ氏は語った。 「これらの部分的な問題は、全体的な問題とほぼ同じ難易度だと誰もが思っていました。」

MCSP の完全バージョンの NP 完全性を証明するには障害が残っています。 しかし、まったく新しいツールキットが必要であることを示唆するような障壁はありません。既知の技術を組み合わせる適切な方法を見つけるだけの問題かもしれません。 証明ができれば、複雑性理論が存在する限り分類に抵抗してきた数少ない問題の XNUMX つが最終的に解決されることになるでしょう。 レビンは電子メールで次のように書いた。「それを見ることができなかった自分が愚かだったことを示すのは謙虚な気持ちになります:-)」

欠けている部分

大きな進歩をもたらしたメタ複雑性の問題は MCSP だけではありません。 2020 年、コーネル大学の暗号学者 ラファエルパス と彼の大学院生 ヤンイー・リウ つながりを発見した 異なるメタ複雑性の問題と、ヒューリスティカとペシランドの間の境界を定義する基本的な暗号プロトコルとの間で、インパリアッツォの世界の最悪の世界（NP完全問題は平均的な場合の意味で困難ですが、暗号化はまだ不可能です）。 そのため、彼らが研究した問題はペシランド攻撃の最有力候補となり、 もっと最近の仕事 Heuristica に対しても機能する可能性があることを示しています。

「パズルのさまざまなピースが欠けています」とパス氏は語った。 「私にとって、これらの分野がこれほど密接に結びついているのはまさに魔法のようです。」

平原氏は、インパリアッツォが30年前に想起させた世界を淘汰しようとする研究者たちには、依然として困難が待ち受けていると警告する。 同氏は「ある時点でヒューリスティカとペシランドは排除されるだろうと言いたいが、どれだけ近づいているかは分からない」と述べた。

多くの研究者は、最大の困難は、平均ケース複雑さの XNUMX つの異なるモデル間の一見無害なギャップを埋めることであると予想しています。 暗号学者は通常、両方向で間違いを犯す平均的なアルゴリズムを研究し、ランダムな文字列を擬似ランダムと誤ってラベル付けしたり、その逆を行ったりすることがあります。 一方、平原氏の最悪ケースから平均ケースへの削減は、最初の種類のエラーのみを発生させる平均ケースのアルゴリズムに対して機能します。 このような微妙な区別は、複雑性理論に大きな違いをもたらす可能性があります。 しかし、この障害やその他多くの障害にもかかわらず、アレンダー氏は慎重な楽観主義の声を響かせずにはいられません。

「何も効果がなかったという実績は十分に確立されているので、私は自分自身をあまり信じないようにしてます」と彼は言いました。 「しかし、私たちは本当にエキサイティングな開発、つまり障壁のように見えたものを克服する方法をたくさん見ています。」

P か NP かという質問に答えるための苦闘から研究者が学んだ教訓が XNUMX つあるとすれば、あるいはそれを理解するだけでもいいのですが、それは複雑性理論自体が複雑であるということです。 しかし、その挑戦こそが、この探求を非常にやりがいのあるものにしているのです。

「これほど難しいのは、実際のところ、ある意味素晴らしいことだ」とカルモシーノ氏は語った。 「決して退屈することはありません。」

編集者注: スコット・アーロンソンは、 クォンタマガジンさん 諮問機関.