AIモデルが指数時間仮説を覆した？教科書の書き換えはまだ早い

TechCrunchが2026年10月28日に報じたところによると、最前線のAIラボが、自社モデルが計算複雑性理論における指数時間仮説（Exponential Time Hypothesis、ETH）を反証したと主張している。報道の要旨によれば、TechCrunchはMITの計算機科学者にインタビューを行い、OpenAIによるこの最新かつ難解な発見を外部に説明する役割を担っているという。この報道が衝撃を与えた理由は、ETHが単なる通常の予想ではなく、精細複雑性理論の中核的な柱の一つだからだ。もしETHが本当に覆されれば、影響を受けるのは数学界だけでなく、アルゴリズム設計、暗号学のパラメータ設定、そしてAI支援による科学研究の信頼性にまで及ぶ。

ETHとは何か、なぜ重要なのか？

ETHはImpagliazzoとPaturiによって1999年前後に体系的に提唱されたもので、その核心的な主張は「3SATなどの古典的なNP完全問題には亜指数時間アルゴリズムが存在しない」というものだ。言い換えれば、変数数が増加するにつれて、最悪ケースの求解時間はexp(o(n))以下には下げられないということである。これはP≠NPよりも強力かつ具体的な主張であり、多くの細粒度の下界結果の基盤となっている。研究者はしばしばETHを仮定として用い、編集距離、グラフアルゴリズム、あるいは特定のパラメータ化問題などについて「これ以上高速化することは不可能」であることを証明する。もしETHが反証されれば、3SATに亜指数時間アルゴリズムが存在することを意味し、膨大な数の下界証明が書き直しを迫られ、アルゴリズム競技と理論計算機科学の地図が塗り替えられることになる。

「最前線のAIラボが、自社モデルが指数時間仮説を反証したと主張している。」——TechCrunchの報道タイトルが述べる核心的な主張

AIはどのようにして仮説を「反証」するのか？

報道の情報から見ると、最もあり得るシナリオは、モデルがETHを覆すと主張する証明、アルゴリズム、または反例を生成したというものだ。しかし、数学的な主張と数学的真理の間には検証という壁がある。AIモデルは定義を混同したり、未証明の補題を引用したり、循環論証を行ったり、あるいは自然言語による証明の中に重要なステップを隠したりする可能性がある。したがって、MIT科学者の役割はモデルを保証することではなく、この発見が実際に何を意味するのか、どの部分が検証可能なのかを一般に理解させることにある。現代の数学界にはLeanやCoqといった形式化検証ツールがすでに存在するが、複雑な証明を完全に形式化することは依然として膨大な作業を要する。形式化検証と独立した再現がなければ、いわゆる「反証」は検証待ちの強い主張として扱うほかない。

もし成立した場合、衝撃はどれほど大きいのか？

まず、アルゴリズム分野にパラダイムシフトが生じる。亜指数時間の3SATアルゴリズムは多数のNP問題の高速化を牽引し、最適化・計画・検証・自動推論に影響を与える。次に、暗号学はセキュリティパラメータの再評価を迫られるが、SATにより高速なアルゴリズムが存在するからといって、すべての暗号がただちに破られるわけではない点に注意が必要であり、実際の影響は具体的な帰着とアルゴリズムの定数に依存する。さらに、複雑性理論は再構築の時期に入り、ETHを条件としていた多くの下界結果がその前提を失い、研究者は新たな仮定を探し求めることになる。最後に、AI業界にとっては、もしモデルが本当に検証可能な数学的ブレークスルーを提示できるなら、AI for mathは推測の補助から発見エンジンへと進化することになる。逆にそうでなければ、AI科学研究の誇大宣伝に対する警告となる。

編集者注：まず三つの検証関門を通過せよ

「AIがETHを覆した」というような見出しに直面したとき、理性的な態度は声の大きさではなく証拠を見ることだ。第一の関門は形式化：証明が証明支援システムによって検査できるかどうか。第二の関門は独立した再現：外部の専門家が同一の設定のもとで同じ結論に到達できるかどうか。第三の関門はコミュニティによる査読：結論が長期的な同業者レビューに耐えられるかどうか。最前線の実験室もまた、衝撃的なサマリーだけを公表するのではなく、モデルの出力・プロンプト・検証スクリプト・失敗事例を公開すべきである。科学コミュニケーションの難しさは、AIが生成した「発見」が驚異的であればあるほど、より監査可能な証拠の連鎖が求められるという点にある。

現時点でTechCrunchが開示した情報はまだ限られており、MIT科学者の説明が「モデルが言ったこと」と「数学が証明したこと」を区別する助けになるかもしれない。さらなる詳細が公表されるまで、最も堅実な判断は次の通りだ：これは追跡する価値のある重大な手がかりであるが、教科書を書き換えるべき時ではまだない。

本記事はTechCrunchより編訳