11月4日、Dataconomyが「OpenAI and Anthropic claim AI disproved the exponential time hypothesis」と題した記事を公開した。27年間にわたり理論計算機科学の基礎とされてきた「指数時間仮説（ETH）」を、OpenAIとAnthropicのAIモデルがそれぞれ独立に反証するアルゴリズムを発見したと両社が主張している。確認されれば800本超の論文が無効になりうる可能性があり、研究者の中には混乱でうつ状態に陥っている人もいるという。

27年来の仮説が崩れた？

指数時間仮説（Exponential Time Hypothesis、ETH）とは、1999年にカリフォルニア大学サンディエゴ校のRussell ImpagliazzoとRamamohan Paturiが提唱した仮説だ。「3-SAT問題（3つの条件からなる節で構成されたブール変数の充足可能性判定問題）を解くには、変数の数に対して指数時間が必要である」という主張を核心とする。

ブルートフォース（全探索）では変数が1つ増えるたびに計算量が倍増する。2026年10月以前の最良のアルゴリズムでも、決定的アルゴリズムで底が1.328、乱択アルゴリズムで1.308まで削減するのが限界だった（Anthropicの論文より）。

今回、OpenAIとAnthropicはそれぞれ2^o(n)（2のo(n)乗）の実行時間で3-SATを解くアルゴリズムを発見したと主張している。この表記は「変数あたりの乗数が入力サイズの増大に伴って1に近づく」ことを意味し、ETHと真っ向から矛盾する。両社のモデルがコアアイデアを発見したのは同日（10月16日）だったという。

Claudeは1400万トークンを出力して発見した

特にAnthropicの開示内容は興味深い。Claudeは人間の介入なしに、1400万トークンの出力を生成した末にコアアルゴリズムを発見したとAnthropicは述べている。その後、Anthropicの研究者がClaudeと共同で論文をまとめ、著者欄には「Claude, Anthropic」と記載されている。

OpenAIは67ページの論文「The Exponential Time Hypothesis is False」を、Anthropicは49ページの論文を公開した。

証明の検証には、両社とも**Lean)**（定理証明支援システム。与えられた命題から証明が論理的に続くかを機械的に検証するソフトウェア）を使用した。Leanは与えられた命題から証明が論理的に続くかを機械的に確認するが、「その命題が論文の主張と一致するか」は人間のレビュアーが判断しなければならない点は重要だ。Anthropicも「LeanファイルがLeanが論文の内容を正しく記述しているかを機械チェックする仕組みはない」と明記している。OpenAIのLeanファイルは、論文の主見出し結果より若干遅いバウンドを証明しているが、それでもETHを反証するには十分だとしている。

査読は進行中、現時点で欠陥は未発見

レビューを担当するのはETHの提唱者であるImpagliazzoとPaturi、MITのRyan Williamsの3名だ。10月29日時点で、両論文に対して公的に欠陥は指摘されていない。

ただし査読チームのレターには「査読への参加は、主張の認定を意味しない」と明記されており、慎重な姿勢を崩していない。Williamsは「OpenAIの証明の一部は標準的に見えるが、"異質に見える2〜3の部分"は広範な研究コミュニティによる精査が必要だ」と述べている。

実用的な3-SAT求解への影響はない

重要な留意点がある。このアルゴリズムは、実用的な3-SAT問題の求解性能を向上させるものではない。

Anthropicは、節と変数の比率が5の3-SAT問題の場合、変数が10^10,000個を超えない限りブルートフォースに勝てないと記している。ちなみに観測可能な宇宙の原子数の推定値よりもはるかに大きい数だ。現実の問題では変数100個程度でブルートフォースはすでに非現実的であり、今回の結果が実計算に恩恵をもたらす規模は天文学的に遠い。

暗号への影響は「限定的だが注視が必要」

暗号分野への波及も話題になっている。Williamsは、OpenAIのサイエンスリードが「結果が暗号システムを破るかを確認し、破らないと合理的に確信している」と述べたことを明かした。カリフォルニア大学サンタバーバラ校のDaniel Lokshtanovは「直接的な影響はないが、一部の暗号設計者は怯えるべきだ」と述べた。

ルール大学ボーフムとマックスプランク・セキュリティ&プライバシー研究所の研究者らによる10月29日付けのプレプリントは、今回のアルゴリズムを楕円曲線に適用した攻撃を記述している。ただしその攻撃は「わずかに指数時間を下回る（わずかに準指数時間的）」なものであり、天文学的なサイズでのみ利益が生じ、現在デプロイされている楕円曲線への具体的攻撃は改善しないと著者らは述べている。

**P≠NP問題**（計算複雑性理論における最大の未解決問題）への影響については、Anthropicは「P=NPを直接示すものではない」、OpenAIは「NP問題一般への速度向上には拡張しない」としている。ただしWilliamsは「P=NPの妥当性にやや多くの重みを置くべきだ」とも述べており、見方が変わりつつある。

研究コミュニティへの衝撃

ETHを前提とした研究への影響は甚大だ。ClaudeによるETH文献サーベイでは、ETHのみに依存する結果を含む論文が800本以上見つかった。これらはETHの反証が確定した場合、結論の修正や無効化を迫られる可能性がある。

Lokshtanovは「確認されれば自分が"galactically wrong"（銀河規模で間違っていた）ことになり、自分の発表論文50本程度が無意味になるか修正が必要になる」と述べ、今回の主張を「フィールドの真ん中に投下された巨大な爆弾」と表現した。

コペンハーゲンIT大学のアルゴリズム研究グループ長Thore Husfeldtは「自分が取り組んでいた問題の研究が今や無意味になった」と明かした。またAIが生成した数学的成果が「毎週か2週間に1度」届くようになっており、研究者の進行中プロジェクトを次々と崩しているという。研究者の中には混乱でうつ状態に陥っている人もおり、所属学科では産業カウンセラーの採用を検討したと明かしている。

詳細はOpenAI and Anthropic claim AI disproved the exponential time hypothesisを参照していただきたい。