OpenAI 宣称模型推翻指数时间假设 ETH，已用 Lean 验证

AIFlow_ML · x · 2026-10-27

10 月 27 日，MIT 复杂性理论家 Ryan Williams 发帖称 OpenAI 内部模型「宣称推翻了指数时间假设（ETH）」，他与 Russell Impagliazzo、Mohan Paturi 被邀请组织开放独立的审查。OpenAI 的 Dan Roberts 随后宣布「数学、计算机科学、物理学三领域的三项新发现」，其中 CS 领域的核心成果据 OpenAI 自述是「系统证明了 ETH 为假，并已在 Lean 中完成验证」。配套论文摘要称给出了精确计数 k-CNF 可满足赋值的确定性算法，时间复杂度 (n+m)^{O(k)}2^{n/(log n)^{1/3+o(1)}}。这是号称挑战复杂性理论支柱级猜想的重大且存疑的宣称，作者以工程师视角解读：SAT 求解器暂时还不会受影响。