OpenAIのAIが計算機科学の「常識」を覆した？ 25年間信じられてきた指数時間仮説に反証を提示

この記事のポイント

何が起きた: OpenAIが、社内モデルによる「指数時間仮説（ETH）の反駁」を主張するプレプリントとLeanの形式証明をGitHubで公開した。MITのRyan Williams氏らが独立した検証を進める。
なぜ重要か: ETHは、何百本もの論文で計算の難しさを示す前提となってきた予想だ。ただし、今回の主張はP対NP問題の解決や、実用暗号の解読を意味しない。
次に見るべき点: Leanで検証された命題が、本来のETHを反駁する内容になっているかが焦点となる。論文と形式証明の対応、アルゴリズムの正しさ、計算量の評価を専門家が精査する。

（以下略、続きはソースでご確認ください）

xenospectrum　2026年10月27日
https://xenospectrum.com/openai-exponential-time-hypothesis-false-claim/