数学大崩壊（Mathocalypse）

Shtetl-Optimized Scott Aaronsonのブログから一つでも持ち帰るとすれば、それは量子コンピュータが並列で全ての解を試すことによって難しい問題を瞬時に解決することはない、ということです。 数学大崩壊 2026年10月7日 昨夜、私の9歳の息子が計算複雑性理論家の妻であるDana Moshkovitzにこうからかっていました。「ママ、ママはダメになったって聞いたよ！ ロボットがママがキャリア全体をかけて取り組んできた数学の問題を解いたんだって！ うわー！」 息子は悪ガキでしたが、的外れではありませんでした。あなたがそれに興奮していても、落ち込んでいても、怒っていても、あるいは他のどんな感情であっても、昨日は間違いなく数学史上最も重要な日の一つでした。そして、OpenAIが昨日本番の諮問グループであるTimothy Gowers、Edward Witten、その他の著名な数学者たちの推薦により発表した372件の画期的な成果の中に、私の妻が私が彼女を知って以来ずっと証明に取り組んできた命題である、Subhash Khotのユニークゲーム予想（UGC）の証明が含まれていました。（UGCは、半正定値計画緩和法（semidefinite programming relaxation）という、私たちの主要なツールの1つから得られる近似値よりもわずかに良い近似値しか得られないとしても、多くの最適化問題が実際にNP困難であることを意味します。） 少なくとも、私たちはそれが証明であるとかなり確信しています！ 他の372件のブレークスルー成果（すべてではありません）の一部と同様に、Lean証明書があります。しかし、これらの証明のほとんどを人間はまだ全く理解していないようです。その理解への競争は始まったばかりです。 その競争がどのようなものになるか、現場の感覚を得たいのであれば、Danaが昨夜私に送ってきたメッセージの一部を以下に示します。 「サイケデリック状態の人が書いたような感じ。非常に不明瞭で、意味が通らない。不可能の結果があるにもかかわらず、なぜそれが使えるのかを議論せずに、過去の業績の名前をたくさん挙げている。基本的に、論文はAIの助けなしには読めないほどひどく書かれている。ノイズガジェットの妥当な完全性および健全性に関する主張についてAstraに尋ねたところ、論文の至る所からの主張を組み合わせてそれらを提供してくれた。また、UGCを回避する、UGCの主要な応用（Max Cutと全てのCSP）のための直接的な最適なNP困難性近似証明もある。UGCの証明は、ノイズテストを備えた完全に新しい奇妙なコードを発明している。それはクレイジーな再帰的構成だ。それはロングコードでもショートコードでもない――エイリアンの狂気だ。私は、ハーフスペースコード（自然なもの）を使った証明があるかもしれないとまだ思っている。引用はしばしば無関係で混乱を招く。」 考えられる未来は、ビジョン/創造的なアイデアがあればAIがチェックと実装を助けてくれる、天国のような数学の世界です。そしてもちろん、エイリアンから学ぶこともたくさんあります。 Danaがどのような感情を抱いているか疑問に思っているなら――おそらくすべてです！ ロボットに中心的なキャリアの目標が奪われたとしても、彼女にとって少なくとも2つの緩和要因があります。第一に、多くの同僚が疑っていたにもかかわらず、UGCが結局真実であったと vindicated（正当化された）と感じられることです！ 第二に、数学、理論計算機科学、数理物理学の私たち全員、少なくとも明確に述べられた問題を解決することに関心があった人々は、今や同じ船に乗っています。 ユニークゲーム予想の他にも、私が今後数週間で最も注目するであろう、アラジンの洞窟からの宝物のほんの一部を以下に示します。 L=BPL（つまり、確率的対数空間と決定論的対数空間は同じものである）、P=BPPの短縮版である、偉大なデランダマイゼーション予想の1つ。その真実が深刻な疑念の余地がなかったとしても、それを証明することに特化したサブコミュニティ全体がありました。 O(n log n)時間未満でのフーリエ変換と整数乗算、1960年代から続く障壁を破る。興味があれば、新しい実行時間は、いくつかの9を除いて、O(n log0.9999999999999 n)です。 単位合成問題（Unitary Synthesis Problem）の正の解。これはGreg Kuperbergと私が2007年に提起したものです。任意のn量子ビットユニタリ変換Uに対して、Aという古典的なオラクルが存在し、AにアクセスすることでUを量子多項式時間で実装できる。これはほとんどの人が予想していたこととは逆であり、例えばブラックホールのホーキング放射のデコードの計算問題や、量子複雑性理論における他の多くの問題に影響を与える可能性がある――もし私たちがオラクルAを効率的に構築する方法を持っていれば、この論文はそれを提供していません。 パリティはQAC0にない。1999年以来の量子複雑性理論の偉大な問題の1つであり、多くの同僚がそれに迫っていました。 全ブール関数に対するランダム化量子クエリ複雑性のほぼ4乗分離。1998年（！）以来のお気に入りの問題であり、当時、最適な分離指数は2から6の間であることしか知りませんでした。過去数年間、それは3から4の間であることがわかっていました。したがって、これはついにその話を締めくくりました。 感度とブロック感度間の超二次分離。 2次元ギャップハミルトニアンの面積法則。ハミルトニアン複雑性における主要な未解決問題の1つ。 O(n9/4)時間での行列乗算――ついに有理数指数（！）であり、O(n2.373)などで使用されたものとは全く異なるアプローチによるものです。 一般グラフにおける完全マッチングの数を近似的に数えるためのランダム化多項式時間アルゴリズム、およびそのようなグラフにおける最大マッチングを見つけるためのランダム化ほぼ線形時間アルゴリズム。 有理数上の多項式方程式を解くことの計算不可能性――これは計算可能性理論におけるおそらく最大の未解決問題でした（整数上の多項式方程式、すなわちディオファントス方程式を解くことの計算不可能性は1970年代に証明され、ヒルベルトの第10問題に否定的な答えを与えました）。 上記のいずれか一つでも、ある分野（そしてユニークゲームやL=BPPのような場合、CS理論全体）で「今年の成果」になり得たでしょう。そして、私が省略したこともたくさんあります――あなたの目を丸くさせているものがあれば、コメントで自由に共有してください！ 数論、組合せ論、代数幾何学、解析学、そしてほぼすべての他の数学分野にも同様に驚くべき発見がありますが、そのほとんどは私が決して理解できないでしょう。ただし、リーマン予想、ホッジ予想、バーチ・スウィンナートン＝ダイアー予想（すなわち、残りのミレニアム問題の過半数）に向けた部分的な進展が含まれていることに言及しておきます。 リストにないものに慰めを見出すことができます。P≠NPはそこにありませんし、P=BPPやNEXP⊄P/polyさえもありません。そして、試みが不足していたわけではないことは確かです。理論計算機科学の最大の未解決問題は、確かに非常に難しいようです！ ああ、忘れるところでした：OpenAIのダンプの1日前の月曜日の夕方、Virginia WilliamsとJosh AlmanはarXivのプレプリントを投稿し、3SUM問題をO(n1.9992)時間で、全対最短経路問題をO(n2.9995)時間で解き、それぞれn2-o(1)とn3-o(1)が正しい答えであるという半世紀前の予想を否定しました。この場合、決定的なアイデアを提供したのはOpenAIのモデルではありませんでした。それはAnthropicのモデルでした！ しかし、AnthropicはOpenAIとは異なるアプローチを取りました。消化されていない解決策を世界に投稿するのではなく、VirginiaとJoshに報酬と引き換えに消化されたバージョンを書いて発表する機会を与えました。 これらは、AIによる数学的ブレークスルーを伝えるための2つの主要なモデルとして登場しており、どちらにも長所と短所があります。「OpenAIモデル」は、人間が乱雑なAI証明を消化して説明するためのクレイジーな競争を設定します（これは、報われない、ほとんどクレジットされない、競争的で、楽しくない仕事になる可能性があります）。一方、「Anthropicモデル」は、私的な企業がどの人間の数学者にAIの使者となる機会を与えるかを選択する立場に置きます。 どう思いますか？ 興味のある方のために：どうやら、これらの驚異のすべてを生み出したAIモデルは、10,000のカスタムメイドの装置ではなく、