OpenAI 宣称证伪指数时间假说，3SAT 可亚指数求解

fortnow · x · 2026-10-27

OpenAI 宣布了一项震撼复杂度理论的结果：声称指数时间假说（ETH）不成立——3SAT 问题（甚至包括解的计数）可以在 2^{o(n)} 时间内解决，并给出了 proof 的 Lean 形式化。若成立，这将是理论计算机科学几十年来最重大的突破之一，意味着一大批假定需要指数时间的 NP 问题实际上存在亚指数算法。理论计算机科学家 fortnow（Gasarch）转发了官方公告与论文链接，并强调这一宣称的分量——注意目前只是 OpenAI 单方面宣称，尚待独立验证。