AIがETH反証：計算量理論に激震
原題: Frontier AI labs say their models refuted the Exponential Time Hypothesis. What does that mean?
なぜ重要か
ETHは暗号理論や計算複雑性の基礎を担う仮説であり、その反証は情報セキュリティ設計や理論計算機科学全体に長期的影響を与える可能性がある。
OpenAIは2026年10月26日、計算科学の基礎仮説「指数時間仮説（ETH）」の反証を含む数学難問3件の解を公開した。数時間後にはAnthropicも独自のETH反証を発表。MIT教授Ryan Williamsら当初ETHを提唱した研究者が検証作業部会を組織し、コミュニティへ公開フィードバックを求める公開書簡を発出した。
OpenAIが公開した解のなかで最も衝撃的だったのが、ETHの反証だ。ETHは1999年にUC San DiegoのRussell ImpagliazzoとRamamohan Paturiが発表した仮説で、コンピュータ科学において「何が計算困難か」を定義する基盤の一つとして広く受け入れられてきた。
ETHは「P vs NP」問題という大きな枠組みの一部だ。P vs NPとは、解の検証が容易な問題（NP）が解を導き出すことも容易（P）かどうかを問うものだ。数独パズルを例に取ると、解が揃えば正否はすぐ分かるが、解を見つける作業は膨大な時間を要する。この非対称性は暗号システムの安全性を支えており、鍵があれば即座に復号できるが、鍵なしでの解読は現実的な時間内に不可能とされてきた。ETHの反証はこの前提を揺るがす可能性を示唆する。
Anthropicの数学者Levent AlpögeはOpenAIの解が既存研究に依拠していると指摘。Anthropicはその後、独自のETH反証を公開した。学術コミュニティの反応は「興奮と困惑の混在」と報じられている。
OpenAIは今回、分野ごとに公開方法を変えた。数学者向けにはGitHubに直接投稿。計算科学者は作業部会を結成してプルーフの公開とOpenAIによる討論会資金提供を要請。物理学者も作業部会を設置し、公開方法を慎重に検討中だ。
MIT教授のRyan Williamsはかつて、OpenAIの10月初頭の「プルーフ一括公開」を「数学者へのDDoS攻撃」と批判した人物だ。それでも今回は協力を決断し、TechCrunchに対してこう語った。「一部は平凡かもしれないが、2〜3か所は明らかに異質な部分があり、そこを見た瞬間にコミュニティ全体で取り組むべき内容だと確信した」。Williams、Impagliazzo、Paturiの3人が連名で公開書簡を発出し、科学者からのフィードバックとAIの学術貢献に関する規範の議論を呼びかけた。