10月29日、WIREDが「An AI Breakthrough Has Made Decades of Computer Science Research 'Irrelevant'」と題した記事を公開した。OpenAIとAnthropicがAIを用いて理論計算機科学の根幹を支える27年来の仮説「指数時間仮説（ETH）」を反証したとするもので、研究者コミュニティに動揺が広がっている。

研究者への衝撃：「50本の論文が無意味になるかもしれない」

UCサンタバーバラのDaniel Lokshtanov教授は、この結果が確認された場合、自分は「銀河規模で間違っていた」ことになり、自身の発表済み論文約50本が「無意味になるか、見直しが必要になる」と述べている。

「フィールドの真ん中に巨大な爆弾を落とされたようだ。本当にクールで、同時にひどいことでもある」

リンシェーピング大学のPeter Jonsson教授は、2週間後にIEEE Symposium on Foundations of Computer Science（IEEE FoCS）※で自身の研究を発表する予定だったが、ETHを前提とした研究が「死んだ」と表現した。カンファレンスでは「ETHは偽だ、自分の論文の半分は成立しない」という発言が相次ぐだろうと予測している。

※IEEE FoCSは理論計算機科学における最権威カンファレンスのひとつ。アルゴリズムや計算複雑性理論の基礎研究が多数発表される場として知られる。

「27年間の前提」がAIによって崩れた

指数時間仮説（ETH: Exponential Time Hypothesis）とは、ある種の問題（特にSAT問題などのNP困難問題）を解くのに要する計算時間は問題のサイズに対して指数関数的に増大する、という命題だ。1997年頃に提唱されたこの仮説は、計算複雑性理論やアルゴリズム設計の広大な研究領域の「土台」として機能してきた。ETHはP≠NP問題とも深く関わる未解決問題群の体系において、多くの下界証明（「これ以上速いアルゴリズムは存在しない」という証明）の根拠として広く援用されてきた。

今回、OpenAIとAnthropicはそれぞれ独立に、このETHが偽であることを示す証明を公開した。証明は自然言語と機械検証可能な**Lean形式**※の両方でGitHubに公開されており、OpenAIの論文は約60ページに及ぶ。

※Lean形式とは、数学的証明をコンピュータが検証可能な形式で記述するための証明支援系（Proof Assistant）の一種。人間の記述ミスや論理的飛躍を機械的にチェックできるため、証明の信頼性を高める手段として数学・理論計算機科学の分野で近年注目が高まっている。

証明の検証はこれから

現時点で、研究者コミュニティはAIが生成したこの証明を独立に検証できていない。 OpenAIはETHを最初に提唱したUCサンタバーバラの研究者と、ETHの反例を研究してきたMITの研究者に呼びかけ、証明を解読するコミュニティの取り組みを立ち上げている。具体的にはボランティアと意見を募るGoogleフォームの設置と、OpenAIによるカンファレンス開催の資金提供が約束されている。

コペンハーゲンIT大学のアルゴリズム研究グループ長Thore Husfeldt氏は、ETHのある版を最初に定式化した人物のひとりでもある。今年の大半を一つの問題に費やしていたが、それが「すべて無関係になった」と語りつつも、悲観とは異なるトーンでこう述べた。

「完全に暗い部屋を手探りで歩き回っているようなものだった。誰かがサブフィールド全体を投光器で照らしてくれた。今は興奮した兎のように走り回って、突然探索できるようになった隅々を見ている。超エキサイティングな時代だ」

反証の独立検証が完了していない現段階では、この結果を既成事実として扱うことには慎重であるべきだ。ただし、Lean形式での記述はその検証プロセスを大幅に加速しうる点で、従来の数学的証明とは異なる信頼性担保の経路を持っている点は注目に値する。

暗号技術への影響は「直接ではないが、設計者は注目すべき」

現代のWebセキュリティを支える暗号技術は、「特定の数学的問題を解くには現実的でない時間がかかる」という前提に依存している。今回の結果はそこに直接影響するものではないが、Lokshtanov氏は「一部の暗号システム設計者を確実に怖がらせるはずだ」と述べている。

Husfeldt氏も「現代のデジタルインフラの多くが計算に関する仮定の上に成り立っている。オープンな科学的プロセスが計算に関する誤解を特定することが重要だ」と強調する。

研究者に漂う「心理的疲弊」

Husfeldt氏は、コミュニティ全体の空気感についても率直に語った。

「ここ数ヶ月は本当につらかった。毎週あるいは隔週でAIが発表する結果が、多くの人の進行中の研究プロジェクトを壊滅させる。心理的に重くのしかかっている」

同氏の所属機関では、産業カウンセラー（職業心理士）の採用まで検討しているという。「本当に落ち込んで悲しんでいる人がいる」と述べた。

また、OpenAIは今月初めに400問題に関する722本の原稿をGitHubに一括投下し、研究者から批判を受けた経緯もある。誤りを含む文書が複数あり、「IPO前の実績作りのためのお粗末なロールアウト」と受け取る数学者もいた。今回のETH論文は、それに比べると質が高いと研究者たちはWIREDに語っている。

ETHの反証が独立検証を経て本物と確認されれば、研究者たちは「ETHが正しい」と仮定して諦めていた問題群に立ち返ることができる。それはアルゴリズム研究の地図を根本から描き直す作業を意味する。Jonsson氏はこう語った。

「人間が書いた証明でも、AIが書いた証明でも、宇宙人が送ってきた証明でも構わない。それが真であれば、これからはそれを使うだけだ」

詳細はAn AI Breakthrough Has Made Decades of Computer Science Research 'Irrelevant'を参照していただきたい。