マスアポカリプス

Shtetl-Optimized Scott Aaronsonのブログ このブログから一つだけ持ち帰るとすれば、それは「量子コンピュータは並列処理で全ての解を試すことによって、難しい問題を瞬時に解決するわけではない」ということです。 UTオースティンでの私の新しいコース：AIアライメント理論 マスアポカリプス 昨夜、私の9歳の息子が、複雑性理論家の妻であるDana Moshkovitzに次のようにからかっていました。「ママ、クックされたって聞いたよ！ママがキャリア全体をかけて取り組んできた数学の問題をロボットが解いたんだって！ひどい！」 息子は生意気でしたが、間違ってもいませんでした。あなたがそれに興奮していても、落ち込んでいても、怒っていても、あるいは他のどんな感情を抱いていても、昨日は間違いなく数学の歴史における最も大きな日の一つでした。そして、OpenAIが発表した372件の画期的な成果のうち、Timothy Gowers、Edward Wittenなどの著名な数学者からなる諮問委員会の推薦により、私が妻を知って以来、彼女が証明に向けて取り組んできたSubhash Khotのユニークゲーム予想（UGC）の証明が含まれていました。（UGCは、半正定値計画法の緩和（我々の主要なツールの1つ）から得られるものよりもわずかに良い近似値しか望めないとしても、多くの最適化問題が実際にNP困難であることを意味します。） 少なくとも、我々はそれが証明であるとかなり確信しています！他の372件のブレークスルー成果（すべてではない）のいくつかに見られるように、Leanの証明書があります。しかし、これらの証明のほとんどを人間はまだ全く理解していないようです。その理解への競争は始まったばかりです。 その競争がどのようなものになるかの現場感覚を得たいなら、Danaが昨夜私に送ってきたメッセージの一部を紹介します。 サイケデリック状態の誰かが書いたような感じ。多くのことが不明瞭で、意味をなさない。不可能の結果にもかかわらず、なぜそれが使用できるのかを議論せずに、過去の仕事の名前がたくさん挙げられている。基本的に、論文はAIの助けなしには読めないほどひどく書かれている。ノイズガジェットの合理的な完全性および健全性に関する主張についてAstraに尋ねたところ、それは論文の至る所からの主張を組み合わせてそれらを提供した。また、UGCの主要な応用（Max CutとすべてのCSP）に対する直接的な最適なNP困難性近似証明もあり、これらはUGCを迂回する。UGCの証明は、完全に新しい奇妙なコードとノイズテストを発明する。それはいくらかのクレイジーな再帰的構成だ。それはロングコードでもショートコードでもない――エイリアンのクレイジーさだ。私はまだ、ハーフスペースコード（自然なもの）を使用する証明があるかもしれないと考えている。引用はしばしば無関係で混乱を招く。 考えられる未来は、ビジョン/創造的なアイデアがあればAIがチェックと実装を助けてくれる、天国のような数学の世界だ。そしてもちろん、エイリアンから学ぶことはたくさんある。 Danaがどのような感情を抱いているか疑問に思っているなら――おそらくすべてだろう！ロボットにキャリアの中心的な目標が奪われたとしても、彼女には少なくとも2つの軽減要因がある。第一に、多くの同僚が疑っていたにもかかわらず、彼女が決して疑わなかったUGCが結局真実であったことを証明できたと感じることができる！第二に、数学、理論計算機科学、数理物理学の私たち全員、少なくとも明確に定義された問題を解くことに興味があった人々は、今や同じ船に乗っている。 ユニークゲーム予想に加えて、私が今後数週間で最も注目するであろう、アラジンの洞窟からの宝物のほんの一部を紹介します。 L=BPL（つまり、確率的対数空間と決定論的対数空間は同じもの）これは、P=BPPを除く、偉大なランダム化解除予想の1つである。その真実には真剣な疑いはなかったが、それを証明することに専念したコミュニティ全体があった。 O(n log n)時間未満でのフーリエ変換と整数乗算。1960年代から続く障壁を破った。興味があれば、新しい実行時間は、O(n log0.9999999999999 n)程度である。 単位合成問題の正の解。これは、Greg Kuperbergと私が2007年に提起したものである。任意のn量子ビットユニタリ変換Uに対して、UをAへのアクセスで量子多項式時間で実装できるような古典的オラクルAが存在する。これはほとんどの人が予想していたことの逆であり、例えばブラックホールのホーキング放射の計算問題や量子計算複雑性理論の他の多くの問題（もしオラクルAを効率的に構築する方法があれば、この論文では与えられていない）に影響を与える可能性がある。 パリティはQAC0にない。これは1999年以来の量子計算複雑性理論の主要な問題の1つであり、多くの同僚がそれに迫っていた。 全ブール関数に対するランダム化クエリ複雑性と量子クエリ複雑性の間のほぼ4乗分離。1998年以来（！）のお気に入りの問題であり、その時、最適な分離指数が2から6の間にあることしか知られていなかった。過去数年間、それは3から4の間にあると知られていた。したがって、これはついにその話を締めくくる。 感度とブロック感度間の超二次分離。 2次元ギャップハミルトニアンの面積法則。ハミルトニアン複雑性における主要な未解決問題の1つ。 O(n9/4)時間での行列乗算――ついに有理数指数（！）となり、O(n2.373)などのためのものとは全く異なるアプローチによる。 永久行列式の行列式複雑性に対するΩ(n3)下界。以前の最良の下界（二次）を改善する。 一般グラフにおける完全マッチングの数を近似的に数えるためのランダム化多項式時間アルゴリズム、およびそのようなグラフにおける最大マッチングを見つけるためのランダム化ほぼ線形時間アルゴリズム。 有理数上の多項式方程式を解くことの計算不可能性――これは計算理論におけるおそらく最大の未解決問題であった（整数上の多項式方程式、すなわちディオファントス方程式を解くことの計算不可能性は1970年代に証明され、ヒルベルトの第10問題に否定的な答えを与えたことに注意）。 上記のいずれか一つでも、ある分野（そしてユニークゲームやL=BPLのような場合、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モデルは、そうではなかった。