AI 说"指数时间假说"是错的,然后人类发现自己也没讲清楚它怎么错的。ETH 曾是数百篇论文的地基,如今它的证明、验证、发布流程与署名之争,构成了 AI 科研最真实的一次全景实验
来源:TechCrunch(Tim Fernholz,2026年10月27日独家);OpenAI《Working with academic communities to build scientific understanding》(2026年10月27日);OpenAI《Sharing AI progress in mathematics》(2026年10月6日,10月15日更新);Anthropic GitHub anthropics/formal-math 仓库 eth/ 目录 README 与 MainResults.lean(2026年10月);OpenAI GitHub openai/math 仓库预印本与 Lean 形式化说明 lean/docs/378.md;Lean / Mathlib 官方文档;Palomar 登记册与 leanprover/comparator 项目说明
日期:2026年10月28日
在讲 AI 干了什么之前,先花五分钟把 ETH 讲明白——这是后面所有争论的地基。
3-SAT 是这样一道题:给你一堆逻辑子句(每条子句是三个文字的"或",比如 x1 ∨ ¬x2 ∨ x3),问你"这堆子句能不能同时为真?"——能的话有多少种满足赋值?
它是NP 完全问题里最有名的一个。NP 的意思是"解出来之后可以很快验证对错",P 的意思是"解出来本身也很快"。
P vs NP 是计算机科学最大的未解问题。用 Ryan Williams(MIT,最懂这件事的人之一,也是这次 OpenAI 请来当"牧羊人"的计算理论家之一)的说法:
"P = NP is saying that, not only can you verify Sudoku solutions when they exist, you can just generate them. P = NP is asserting that this is true for every single problem you can verify quickly — if you can verify it quickly, you can solve it quickly. So this just seems too good to be true."
(P = NP 说的是:不仅当数独解存在时你能很快验证它,你还能直接生成它。P = NP 断言的是:对你能快速验证的每一个问题,你都能快速求解。这看起来实在好得不像真的。)
绝大多数计算机科学家因此站在 P ≠ NP 一边。
而 ETH(Exponential Time Hypothesis,指数时间假说) 是 1999 年由 Impagliazzo、Paturi 与 Zane 提出的一个更具体的假设:即使 P ≠ NP,某些"难啃"的 SAT 类问题(3-SAT 及其近亲)也需要指数级时间才能求解——不是"可能需要",而是"确实需要"。
ETH 的厉害之处不在于它难,而在于它太好用了。过去二十年,无数论文把 ETH 当作"砖头":只要假设 ETH 成立,就能证明"这个算法在某种意义下是最优的""这个问题本质上很难""这个优化问题没有高效近似"。这些结论散落在图论、计算生物学、数据库、计算几何、密码学等一大片领域里。
用 Williams 的话说:
"The durability of ETH has lead to it being included in many scientific papers over the past decade that will need to be revisited if the AI labs claims that they've proven it wrong holds up."
(ETH 的持久生命力让它出现在过去十年大量论文里——如果 AI 实验室宣称它们证伪了它的说法站得住脚,这些论文都得回头重做。)
所以 ETH 被推翻,不是"多了一个更快的 SAT 求解器"这么轻描淡写。它是一整座用"ETH 成立"当脚手架搭起来的建筑,被抽掉了一根承重柱。
时间线(全部来自 OpenAI 与 Anthropic 官方材料):
| 时间 | 事件 |
|---|---|
| 2026年10月6日 | OpenAI 第一次大规模发布"内部前沿模型"做出的数学结果(local smoothing 猜想,进而解决 Kakeya 猜想与 Stein 限制猜想),论文与 Lean 形式化都放上 GitHub |
| 2026年10月9日 | Anthropic 对 OpenAI 这波"扔证明"的操作提出批评;MIT 的 Ryan Williams 称其为"对数学家的一次 DDoS 攻击" |
| 2026年10月15日 | OpenAI 追加 500 万美元,注资西蒙斯基金会(Simons Foundation)新设的"帮助数学家应对 AI 时代"专项,并承诺向受资助研究者开放模型与算力 |
| 2026年10月16日 | OpenAI 的系统在自然语言层面找到了 ETH 的反证 |
| 2026年10月17日 | OpenAI 把该反证形式化为 Lean 证明 |
| 2026年10月18日 | OpenAI 的模型产出 local smoothing 证明(次日形式化) |
| 2026年10月25日 | OpenAI 正式发布《Working with academic communities to build scientific understanding》,同时公布数学、计算机科学、物理学三组结果 |
| 2026年10月26日 | Anthropic 放出自己的 ETH 反证 + Lean 4 形式化(仓库 anthropics/formal-math) |
技术核心其实一句话就能说清——但这句话的分量要说清楚:
OpenAI 自己给的精确界(来自 openai/math 的 Lean 说明文件 lean/docs/378.md):
k ≥ 2,Lean 证明一台确定性机器能在 2^{O_k(n(log log n)²/√log n)} 时间内精确计数一个规范编码的 k-CNF 的满足赋值数(L 为编码比特长度,每步最多访问 (L+1)^{O_k(1)} 个纸带格)。(n+m)^{O_k(1)} · 2^{O_k(n log log n / √log n)};当 m ≤ Dn(子句数与变量数线性相关)时进一步改进为 2^{O_{k,D}(n/√log n)}。读法:log log n / √log n 这个因子趋于 0 但不趋于常数。也就是说时间复杂度是 2^{n·o(1)}——严格小于任何 2^{εn}(ε 为常数),但仍然是指数形式,只是指数上的系数被压到任意小。
而 ETH 说的正是:不存在这样的算法。所以 ETH 假。
Anthropic 那边的界长得不一样(anthropics/formal-math 仓库 README 表格):
一台确定性图灵机可以在
2^{O(min{k² n log log n / √log n, km/√log m})}步内,计数任意 k-CNF(m ≥ 2 个子句、n ≥ 4 个变量,且每个变量都出现)的满足赋值数,这证伪了指数时间假说。
论文标题很直白:《A 2^{o(n)} Time Algorithm for 3-SAT, by Claude (Anthropic)》。
一个必须泼的冷水,Anthropic 自己写在 README 顶部:
"The result is purely asymptotic and says nothing about solving formulas in practice."
(这个结果纯粹是渐近的,对实际求解公式没有任何意义。)
也就是说:没有任何一个 SAT 求解器会因此变快一个数量级。 你今天装的任何一个 SAT 求解器,明天还是那个速度。ETH 假说的是"渐近最优性的假设不成立",不是"你手上的代码明天就能跑得更快"。
这是全篇最值得学习者慢慢读的一段。因为它是"AI 做科研"里唯一真正硬的机制。
Lean 是一个带类型的小型编程语言,其中定理即程序、证明即程序运行。写出来的证明由 Lean 的内核(kernel)逐条检查,任何一处不成立就编译失败。所以"论文里的证明"和"机器验证过的证明"之间,差距是可执行的,不是靠人肉挑错。
OpenAI 的流程:10 月 16 日模型产出自然语言反证 → 10 月 17 日形式化为 Lean。Anthropic 的流程类似,形式化由 AI 模型写出。
两家的 Lean 证明都"只依赖三条标准公理"——propext、Classical.choice、Quot.sound。这意味着没有偷偷用任何未经证明的假设。Anthropic 的 README 直接把验证命令写给所有人:
lake exe cache get —— 拉取已编译好的 Mathliblake build —— 编译整个形式化工程lake env lean scripts/PrintAxioms.lean —— 打印定理依赖的公理清单并且明确警告:lake build 会有两个 sorry 警告,两者都来自 Challenge.lean——那是"把论文定理原样复述一遍但不给证明"的对拍文件,是流程设计的一部分,不是漏洞。
但最关键的一句在这里,同样出自 Anthropic README:
"Lean checks the proofs, but no machine checks that this file says what the paper says; the file is kept short so that a reader can check this."
(Lean 检查证明,但没有任何机器能检查这个文件说的是不是论文所说的内容;文件被刻意保持得很短,好让读者亲自核对。)
这句话是整件事的题眼。 形式化验证的是"这个数学陈述 + 这套证明";而"论文里写的陈述 == 形式化里的陈述"这一步,仍然靠人眼。所以 Anthropic 才做了两件事:
MainResults.lean 里用注释的形式写清"证明了什么",并附上论文附录 E,说明它与印刷版陈述的差异;PaperIndex.lean 建立论文编号陈述 ↔ Lean 对应项的逐条映射表。这不是形式化的,这是人类可审计的。两件事必须一起做,缺一不可。
更狠的是 CI 层:Anthropic 的仓库不是"我本地编译过了"就完事,而是按 Palomar 提交模板(Challenge.lean / Solution.lean / comparator.json / formalization.yaml)提交给 Palomar 登记册,登记册的验收检查会用 lean4export 导出的证明、被第二个独立编写的内核 nanoda 重新校验、再经 landrun 沙箱执行,打印 "Your solution is okay!" 才算通过。Lean 版本与 Mathlib 版本都被钉死(此处为 leanprover/lean4:v4.33.1 + Mathlib v4.33.1),构建规模也写明了:24 虚拟 CPU 约 8 分钟,最大进程约 7GB 内存。
顺带一提,Anthropic 这个仓库不是只有 ETH 一项,还有:
zeta23/:黎曼 ζ 函数零点——证明"超过三分之二的零点是单重且在临界线上"(Alpöge–Furman, arXiv:2608.13637);3sum-apsp/:3SUM 在 O(n^1.9992) 步、APSP 在 O(n^2.99942) 步内求解(Alman–Vassilevska Williams, arXiv:2610.06783)。一个实验室愿意把"机器检查过的形式化"做成公开仓库 + 公开验收流程 + 公开 CI,这件事本身,比那三个定理更有长期价值。
数学部分其实是相对平静的。吵起来的是"这个发现算谁的"。
TechCrunch 的报道里有一条关键时间差:
Anthropic 数学家 Levent Alpöge 在 X 上暗示,OpenAI 的解法是建立在已有工作之上的;几小时后,Anthropic 就放出了自己的 ETH 反证。
这个"几小时"非常值得玩味。可能的解释不止一种:
Anthropic 的 README 里有一个非常微妙的细节,直接对应第 2 种可能。它公开了一段"压缩描述",并声称 Claude Opus 5.5 在高 effort 下可以从这段描述重新推导出 ETH 的反证:
"Claude Opus 5.5 at high effort can rederive the refutation of ETH from the following condensed description: The exponential time hypothesis is false! ..."
这段描述里塞进了核心技术(张量网络收缩、singlet、SWAP 分解、行列合并与分组),并且坦白:
"What it rederives is only that 3-SAT can be decided in time O(2^{δn}) for every δ > 0, not the sharper bounds at the top of this page."
(它重新推导出的只是"3-SAT 对任意 δ > 0 都能在 O(2^{δn}) 时间内判定",而不是本页顶部那些更锐的界。)
这段话信息量极大:模型能从一段"已经知道答案"的描述里重建出核心论证,说明这段论证是"可以讲清楚、可以传授"的——而不是某种只有模型自己能摸到的神秘直觉。这既是好消息(知识可以形式化传授),也是坏消息(门槛被拉低了)。
而 Alpöge 的指控——"OpenAI 的解法建立在已有工作之上"——如果成立,意味着 AI 复现了人类已有的结果然后宣称是发现。OpenAI 自己的回应框架就写在官方博客里,标题是"Working with academic communities to build scientific understanding",四条原则:
Transparency(透明):不要求参与者签 NDA,可自由讨论、分享中间产物、发表结论。
No Academic Credit(不索取学术署名):不为自己内部模型做出的发现索取学术信用;邀请研究者做"牧羊人"也不意味着他们或他们的工作组做出了原始发现。
Recognition(认可):工作组应因他们产出的理解、写成的稿件与其他材料而获得认可,并确保工作恰当地引用它所借鉴的研究者、技术与想法。
Independence(独立):参与是自愿且无偿的,工作组成员独立参与,结论属于他们自己;他们不代表 OpenAI,OpenAI 也不代表他们。
这四条读起来很像一份成熟的"科研伦理协议",而且它是对着上一轮争议开出的药。上一轮 Williams 把它称为"对数学家的一次 DDoS 攻击"——仓库一开,几十份手稿同时砸下来,人类学者根本来不及读,谁先读到、谁先发论文、谁署名,都不清楚。
| 学科 | 结果类型 | 发布策略 | 谁来解释 |
|---|---|---|---|
| 数学 | local smoothing 猜想(全维度),进而解决 Kakeya 猜想与 Stein 限制猜想 | 公开 AI 原始输出(自然语言稿 + Lean),不组织工作组 | 研究者自由组织 |
| 计算机科学 | ETH 为假 | 公开 AI 原始输出 + 外部工作组(Impagliazzo、Paturi、Williams 领衔) | 工作组主导,OpenAI 出钱办会议 |
| 物理学 | QCD 及标准模型完备化的存在性证明(含纯 Yang–Mills 存在性) | 暂不公开 AI 产物,由工作组自己写 | David Gross 领衔的工作组 |
三个结果,三套完全不同的规则——这本身就是"发布流程仍在进化"的证据。OpenAI 自己也承认:
"We do not yet know which of these three approaches will be most useful, and we welcome feedback on what works and what we can improve."
(我们还不知道这三种方式中哪一种最有用,欢迎反馈。)
并且坦白了一个结构性问题:
"choosing initial shepherds necessarily shapes who gets involved first and creates asymmetry of information."
(挑选最初的"牧羊人"必然决定了谁先参与,并造成信息不对称。)
这话说得太诚实了:所谓"社区治理",第一轮就带着"谁被选中"的不平等。 谁被选中做牧羊人,谁就先拿到材料、先发文章、先拿到引用。这不是 bug,但至少应该被摊开说。
Williams 的原话,语气非常克制:
"Every computer scientist should probably put a little more weight on the plausibility of P = NP, but one's weight may vary. I do think that it kind of calls into question a lot of the intuitions that we thought we had about … how tractable [hard NP problems] are. I also think that this is probably not the final answer either. I don't think that OpenAI's algorithm could possibly be the best algorithm you can get."
(每一位计算机科学家大概都该给"P = NP 的可能性"多加一点权重,但加多少因人而异。我确实认为,它多少动摇了我们过去对困难 NP 问题可解性的一大堆直觉。但我也认为这大概不是最终答案。我不认为 OpenAI 的算法可能就是你能拿到的最好的算法。)
三个要点,逐个拆:
Williams 做的第一件事非常职业:
"So one of the first questions I asked OpenAI science lead Dan Roberts 'was if they had checked that this affects any crypto systems … is anything insecure now? And apparently, they checked, and they were reasonably confident that this didn't … imply any breaks.'"
(所以我向 OpenAI 科学负责人 Dan Roberts 提的第一个问题是:他们有没有检查这会不会影响任何密码系统?现在是不是有什么东西变得不安全了?结果他们检查了,并且相当有把握这不会导致任何破解。)
注意这里的关键区分,很多人会搞混:
log log n/√log n 这种因子在真实密钥长度下带来的实际收益,可能远远不足以对抗暴力破解;但 Williams 依然把它列为头号问题,这本身就是一种态度:安全领域不能靠"理论上应该没事"。回想 10 月 25 日那篇讲"把互联网关进笼子"的文章里那条主线——当能力边界突然被拉长时,责任方必须主动去检查自己负责的那一格,而不是等着别人来发现。
Williams 提到 ETH 的"持久生命力"意味着过去十年大量论文需要回头检查。这意味着:
这部分工作量巨大、回报模糊、且署名尴尬(因为不是你的成果,是你之前论文的地基塌了)。谁来做?这是接下来几年学术圈真实会疼的地方。
如果你学 AI、学算法、学数学,这篇文章真正能带走的不是"ETH 是假的"这个冷知识,而是三件事。
| 层次 | 具体是什么 | 当前状态 |
|---|---|---|
| 求解层 | 找到一条能证伪命题的路径 | 已可用,且强得超预期(16 天内产出 ETH 反证 + Lean 形式化) |
| 验证层 | 把证明翻译成机器可检查的形式 | 已可用且可靠(Lean 内核 + 独立第二内核 + 沙箱) |
| 策展层 | 决定谁参与、如何署名、如何在社区里被理解与接续 | 最落后,也最卡人 |
过去两年,公众的注意力几乎全在第一层,资本也在第一层。但第三层——"谁来解释、谁署名、谁把新结果接进自己的研究纲领"——才是这次 OpenAI 改发布策略、Anthropic 花力气建 Palomar 流程、Williams 宁可放下"DDOS 攻击"的旧账也要来当牧羊人的原因。
第三层没解决,第一层越强,社区越痛。 想想 10 月 6 日那次"扔证明":结果是真的、Lean 是过的,然后 20 多个数学家同时发现自己看不懂、也没人知道谁该来说明。那不是数学的失败,是知识分发的失败。
Anthropic README 里那句"没有机器能检查这个文件说的是不是论文所说的",是整篇文章里最该被抄进笔记本的一句。
Lean 保证的是:在陈述为真的前提下,证明成立。 它不保证:
一个反例类比:如果有人写了一份完美的 Lean 证明,证明"1+1=2 是错的"(在一个被明确定义的怪系统里),机器会给它盖绿灯。形式化验证是一条下限,不是上限。
Williams 描述他读 OpenAI 证明时的感受,恰恰说明人类验证还在做机器做不了的事:
"Some parts [of OpenAI's proof] are, maybe you could say routine, but then yes, there are two or three alien-looking parts, and it's exactly these parts that I saw that made me think, wow, this is something that the whole community needs to work on together."
(证明里有些部分可以说是例行的,但确实有两三处"看起来像外星文"的部分,而正是这些部分让我觉得:哇,这是整个社区需要一起面对的东西。)
"例行的部分"可以批量检查,"外星文的部分"需要人来重讲一遍。 这就是为什么这次的结果最终由人类理论家来"牧羊"——不是因为机器证明得不够严,而是因为理解必须由人接力。
Williams 说得很直接:
"AI is forcing people to be a little more ambitious about the kind of work that they do, and to think more deeply about, okay, if all the things I used to work on are now low-hanging fruit for AI, how can I raise the bar for the kind of scientific questions I want to ask?"
(AI 在迫使人们对自己的工作类型更有野心,并更深入地思考:如果我以前做的所有事情现在都是 AI 的低垂果实,那我要怎么把自己想研究的问题的标准抬得更高?)
这对学习者是很实在的信号:"解出 3-SAT 的亚指数算法"这条路已经不再是好目标了。 新的目标长这样:
最后一条尤其重要。 这次的三个结果里,计算机科学那一个是"AI 出面、人类接盘",而物理学那一个——QCD 与标准模型完备化的存在性证明——OpenAI 干脆没放出 AI 产物,让 David Gross 领衔的工作组自己从头写。为什么?大概因为这个结果太接近"人类的根基",翻译的成本太高、太不可省略。
二十年来,计算复杂性理论的一个基本信念是:难,是可以证明的。 ETH 就是这个信念最坚固的砖之一——它让"这个问题很难"从一句经验判断变成一条可引用的定理,让成千上万篇论文敢于写下"在 ETH 假设下,我们证明了……"。
现在这块砖被一块 AI 吐出来的东西砸出了裂缝。而且砸它的方式很值得玩味:模型不是给了一个更快的求解器,而是推翻了一条关于"什么是不可能的"的断言。前者只是工程改进,后者动的是知识的边界。
而整篇文章里最让人感慨的,恰恰是那些人类动作:Impagliazzo、Paturi、Williams 组成工作组;Alpöge 在 X 上发出质疑;OpenAI 掏出 500 万美元给西蒙斯基金会,说"我们不要学术署名,但要给你们认可和自由";Anthropic 建了一个公开仓库,把 Lean 版本钉死、把 CI 写进 README、把"哪些句子需要人核对"写得一清二楚。
ETH 是假的。但这门学科还活着,而且正需要人。
anthropics/formal-math —— 仓库 README、eth/ 目录 README、eth/MainResults.lean、eth/proof/PaperIndex.leanopenai/math —— 预印本《The Exponential Time Hypothesis is False (October 25, 2026)》、lean/docs/378.mdleanprover/comparator、Palomar Registry