数学 · OpenAI 与 Anthropic 同日反驳 ETH

10 月 26 日 20:35 UTC，OpenAI 把三份材料挂上自己的数学仓库，其中一份的标题只有六个词：The Exponential Time Hypothesis is False。6.5 小时后，Anthropic 跟进，论文标题更直接：A 2^o(n) Time Algorithm for 3-SAT。两家公司用各自的大模型产出了同一项结论——1999 年提出的指数时间假设（ETH），被反驳了。

ETH 是什么，为什么值得两家电竞式的对轰

ETH 由加州大学圣地亚哥分校的 Impagliazzo 和 Paturi 在 1999 年提出，说的是一个具体的事：3-SAT 这类可满足性问题，不存在明显快于指数时间的通用算法。开关数量每加一个，组合数翻倍，几百个开关的组合数就超过可观测宇宙的原子总数。三十年来，ETH 支撑着「精细复杂度」这个领域的大半结论——无数「这个问题至少需要 n 的多少次方时间」的定理，地基都是它。

OpenAI 的论文给出一个确定性算法，对任意 k-SAT 公式枚举全部解的时间是 2^O(n log log n / √log n)。这个增长速度对每个固定的 δ 都慢于 2^(δn)，恰好是 ETH 排除掉的那类。两篇论文都顺带反驳了更强的 SETH。

验证链条：Lean 加工作组，以及「完全无法阅读」的第一版

两家都把机器可验证证明放进了发布物。OpenAI 用 Lean 验证后公开，Anthropic 的 GitHub 仓库里同样躺着一份 AI 写的 Lean 4 证明。Lean 是个证明助手，代码过得了内核检查，数学上就无可争议——争议只剩「Lean 形式化的对象是否忠实于原命题」这一层。

流程上的安排更值得记录。OpenAI 没有自行宣发，而是请 MIT 的 Ryan Williams 牵头外部审读，Williams 拉来了 ETH 的两位提出者本人。Impagliazzo 对媒体说，OpenAI 发来的第一版「完全无法阅读」，工作组先做了一份可读版本才公开。OpenAI 的口径也诚实：这些手稿「本质上更像一类原始研究数据」，而不是打磨好的论文。审读小组的三人说得很清楚，他们的角色不是背书；截至 10 月 29 日，没有人报告发现漏洞。

结论的边界，比结论本身重要

三项限定必须放在最前面。第一，算法只在变量数超过 10^108 的公式上跑赢暴力枚举——这个数字大到宇宙里的粒子总数在它面前约等于零。第二，OpenAI 告诉 TechCrunch，有相当把握不牵连任何现行加密方案。第三，ETH 被反驳离 P vs NP 还隔着千山万水，亚指数不等于多项式，千禧年奖金的支票还是开不出来。

数学共同体的反应同样值得称量。搜「AI impacts theoretical computer science」的美国检索量三天涨了 600%，但对应领域的扎实判断集中在一点：这是一个精致的、依赖巨大常数的理论结果，工程含义为零。它的重要之处在于纯理论的版图被移动了一块。

为什么这件事的真正主角是发布流程

过去两年，AI 参与数学的新闻以「证明了一个猜想」的形态出现，这次不一样的地方在两头：两头是两家公司 6.5 小时内先后发布同一结论的独立版本，尾巴是「原始研究数据」这个自我定位。模型产出数学结论的速度已经超过人类同行评审的消化速度，OpenAI 和 Anthropic 这次不约而同选择的路数是：Lean 保证内部一致性，外部工作组保证可读性，全程留档保证透明度。这套先机检后人读的流程，大概率会成为接下来几年 AI 数学成果发布的模板。

墙上的日历提醒我们，这个月还发生了 Axiom 团队用多智能体系统 24 天形式化有限单群分类定理、产出 4310 万行 Lean 代码的事。形式化验证的产能已经不是瓶颈，瓶颈移到了「人类要不要、以及如何理解这些证明」。ETH 这两份手稿，是这个新阶段的第一批标本。

参考资料

• OpenAI：The Exponential Time Hypothesis is False（数学仓库，2026-10-26）
• Anthropic：A 2^o(n) Time Algorithm for 3-SAT（GitHub + Lean 4，2026-10-27）
• 中国科学报：OpenAI 称推翻计算机科学一项核心原则（2026-10-30）
• Mean CEO：Exponential Time Hypothesis Refuted by AI?（2026-10-29 更新）
• 腾讯新闻：量子杂志简评 OpenAI 三项里程碑成果（2026-10-31）