10月30日、ibtimes.sgが「Half of My Paper Does Not Work': AI Just Hit Computer Science With a 27-Year Bombshell」と題した記事を公開した。OpenAIのAIが1999年から理論計算機科学の基盤として使われてきた「指数時間仮説（ETH）」を反証したと主張し、CS研究界に波紋が広がっていることを詳しく報じている。
27年間使われてきた仮説が崩れるかもしれない
2026年10月26日、OpenAIは「指数時間仮説（Exponential Time Hypothesis、以下ETH）が偽であることを証明した」と発表した。この主張はまだ独立した専門家による検証が完了していないが、影響範囲の大きさから研究コミュニティで大きな注目を集めている。
ETHは1999年にRussell Impagliazzo、Ramamohan Paturi、Francis Zaneの3名が提唱した仮説だ。核心は「3-SATという論理充足可能性問題は、指数時間より真に速いアルゴリズムでは解けない」というものである。
3-SAT（3-Satisfiability） とは、3つの変数からなる節を持つ論理式に対して、各変数に真または偽を割り当てて式全体を満たせるかを問う問題だ。NP完全問題の代表格であり、「この問題が難しければ、他の多くの問題も難しい」という証明の起点として広く活用されてきた。ETHはその3-SATの困難さを定量的に下限付けする仮説であり、原著論文（Impagliazzo・Paturi、2001年）はアルゴリズム理論の基礎文献として現在も広く参照されている。
OpenAIによれば、ETHはグラフ理論・計算生物学・データベースなど多岐にわたる分野の数百本の論文で前提として使われている。
OpenAIの主張：何を発見したのか
OpenAIの論文が主張するのは、ブール式の充足割り当てを数え上げる決定性アルゴリズムを、わずかに指数時間より速く（準指数時間で）動作するよう構築できたというものだ。改善幅は控えめだが、もし正しければETHが引く「理論的な境界線」を越えることになる。
ただし、これは現実の計算が劇的に速くなることを意味しない。理論的な計算量クラスの境界を越えることと、実用的なアプリケーションで体感できる高速化は別の話だ。
OpenAIは証明の検証にLeanを使用し、「ETHが偽であることを証明し、その結果はLeanで検証された」と述べている。Leanとは、数学的な証明をプログラムとして記述し、コンピュータ上で形式的に正しさを検証できる定理証明支援系の一種であり、公式サイトでその仕様と実装が公開されている。ただし、Leanによる検証は「形式的な記述が正しい」ことを確認するものであり、その形式的記述が数学的主張を完全に捉えているかどうかは、人間の専門家がさらに精査する必要がある。
現在、ETHの原著者であるImpagliazzoとPaturiら（カリフォルニア大学サンディエゴ校）、およびMITのRyan Williamsが内容を精査する予定とされているが、彼らは「関与することはOpenAIの主張を支持することを意味しない」と釘を刺している。
「論文の半分が動かなくなる」
影響の具体性を示すコメントとして、リンショーピング大学のPeter Jonsson氏のケースが報じられている。WIRED誌の報道を引用する形で、Jonsson氏の約50本の発表済み論文がETHに依存しているとされ、本人はETH反証が確定した場合の発表冒頭を次のように表現したという。
「ETHは偽だ。私の論文の半分が機能しない。」
もちろん、これは「50本すべてが無効になる」という意味ではない。ETHへの依存の仕方によっては、別の仮定や代替的な証明によって結論が生き残るケースもある。ただ、長年の前提が覆ると、直接的な研究者だけでなく広い範囲に波及することを示す例だ。
P≠NP問題との関係は？
誤解が広がりやすいポイントとして、記事は明確に否定している。ETHの反証はP=NP問題の解決ではない。
P=NP問題は「効率よく検証できる問題は効率よく解けるのか」という別の問いであり、今回の主張はそれに答えるものではない。暗号技術が脅かされるといった主張は、現時点で確立された事実を超えている。
なお、Anthropicも関連する結果を独自に発表したと報じられている。AnthropicはOpenAIと並ぶ大規模言語モデルの開発企業であり、近年は数学・形式的推論分野への研究投資を強化している。ただし、Anthropicの発表はOpenAIの主張を独立に検証するものではなく、別途評価が必要だとされている。
現時点での立ち位置
ETHは現在も理論計算機科学で広く使われている前提であり、OpenAIの主張は独立した数学的精査を待つ段階だ。専門家が正しいと確認すれば、どの既存研究が見直しを要するかの判断が始まる。確認されなければ、主張は棄却される。現段階では結論が出ていない。
詳細はHalf of My Paper Does Not Work': AI Just Hit Computer Science With a 27-Year Bombshellを参照していただきたい。
