
据多方报道,2026 年 10 月 16 日,OpenAI 的 AI 系统找到了指数时间假设(Exponential Time Hypothesis,ETH)——复杂度理论的基石之一——的一个否定证明,并在大约十天之内由 Lean 证明验证器完成了机器检验。数天后,Anthropic 也披露其模型独立推翻了 ETH,同样给出了次指数时间的算法构造。Wired 引述一位研究人员的说法:AI"直接摧毁了许许多多人正在进行的研究项目"(Wired、TechCrunch)。
这正是 "AI impacts theoretical computer science" 从课堂术语一跃成为本季上升最快的 AI 搜索词的原因。本文讲清楚:到底发生了什么、理论的哪些领域被动摇、哪些毫发无损、对学生/研究者/工程师分别意味着什么——以及同一波前沿模型能力正在如何重塑 AI 图像生成 这类创作工具。
核心要点
- 指数时间假设(ETH)据报已被推翻:OpenAI 与 Anthropic 先后独立完成,OpenAI 的证明在约十天内通过 Lean 机器检验。
- 数千条条件性结果失去地基:参数化复杂度、细粒度复杂度、近似难度中所有以 ETH(或更强的 SETH)为前提的下界,如今悬在半空。
- P vs NP 仍然悬而未决:次指数算法不等于多项式算法——这个领域最深的难题没有被解答。
- AI 为此铺垫了四年:AlphaTensor、AlphaDev、FunSearch、AlphaEvolve、AlphaProof——从微观算法到研究级定理的持续攀登。
- 领域在重组,而非消亡:验证、选题与品味(判断哪个问题值得证明)正在成为理论工作中属于人的核心。
什么是理论计算机科学?
理论计算机科学(TCS)研究的是计算能与不能做什么——不是如何上线一个应用,而是任何机器在给定时间内原则上能证明、排序、分解或搜索什么。主要支柱包括:
- 算法与数据结构——一个问题原则上能解多快?
- 复杂度理论——P、NP、EXP 等难度类之间的关系;哪些问题可证是难的?
- 可计算性与逻辑——从图灵的停机问题到现代证明助手,什么是可判定的?
- 密码学与信息论——哪些安全性保证建立在数学困难性之上?
- 组合数学与图论——网络、优化与计数之下的数学基座。
几十年来,这里的进展以人类数学的速度推进:十年出几条里程碑定理,职业生涯建立在为单个问题削减指数上。今年被打破的,正是这个速度假设。
刚发生了什么:ETH 突破
指数时间假设由 Impagliazzo 与 Paturi 于 1999 年提出,猜想 3-SAT——规范的 NP 完全可满足性问题——无法在次指数时间内求解,即快于 2^o(n)(n 为变量数)。它是比"P ≠ NP"更强的命题,支撑起一整座"条件性结果"大厦:形如"若 ETH 成立,则问题 X 不可能快于 Y"的定理。
根据目前报道:
- OpenAI 的模型于 2026 年 10 月 16 日找到否定证明,论证在约十天内于 Lean 中完成形式化与机器检验(The Next Web)。
- Anthropic 随后独立报告了反驳,同样通过对 ETH 本应守护的问题给出次指数时间构造(TechCrunch)。
- Wired 的报道捕捉了社区的复杂情绪:一边是哀叹("摧毁了许多人正在进行的研究项目"),一边是电流般的兴奋——有研究人员自比"过度兴奋的兔子",盯着全新的研究纲领(Wired)。
两句诚实的 caveat。其一,这些结果只有数天历史;Lean 检验让核心论证极难被质疑,但社区仍在消化细节。其二,"次指数"不等于实用——一个 2^(n/√log n) 的算法足以摧毁 ETH,却对真实 SAT 实例毫无用处。这次震荡是结构性的,不会立刻体现在工程层面。
AI 影响理论计算机科学的五个层面
ETH 是最响亮的一章,但更深的叙事是:AI 系统用四年时间沿理论的阶梯逐级而上。全景如下。
1. AI 发现新算法
- **AlphaTensor(2022)**找到 GF(2) 上 4×4 矩阵乘法的更快算法——五十多年来该情形的首次改进,发表于 Nature(DeepMind)。
- **AlphaDev(2023)**发现短序列排序快至多约 70% 的例程,并被合并进 LLVM 的 libc++——数百万程序在用的标准库(DeepMind)。
- **FunSearch(2023)**给出 8 维空间迄今最大的 cap set——首个由大语言模型完成的真正数学发现,同样见诸 Nature(DeepMind)。
- **AlphaEvolve(2025)**打破一项保持了 56 年的纪录:用 48 次标量乘法完成 48×48 复矩阵乘法,优于 Strassen 递归方案;并通过优化数据中心调度为 Google 收回了约 0.7% 的整个集群算力(DeepMind)。
模式很清晰:AI 不再只是执行算法——它在可能算法的天文数字空间里搜索,找到人类错过的结构。
2. AI 证明定理
形式化证明是下一级台阶。AlphaProof 与 AlphaGeometry 2 在 2024 年国际数学奥林匹克达到银牌水平;2025 年,Gemini 搭配 Aristotle 推理引擎达到金牌水平。OpenAI 2026 年 8 月的文章《数学与理论计算机科学的十项进展》记录了 AI 在几何、密码学与复杂度理论中的成果(OpenAI)。ETH 的否定延续着这条轨迹——而且由于经过 Lean 检验,它带有人类口头报告永远无法提供的保证:机器检验的正确性。
3. 复杂度理论本身在被改写
由于 SETH(强指数时间假设)蕴含 ETH,ETH 倒下便拖垮一切以两者为前提的下界:
- 参数化复杂度——Vertex Cover、Dominating Set 等问题的 FPT 运行时间下界(ETH 下不存在 2^o(k)·poly(n) 算法),以及数十条核化界。
- 细粒度复杂度——以 SAT 困难性为锚的归约,含 APSP 与 3SUM 类条件界。
- 近似难度——建立在 ETH 型 gap 归约之上的不可近似性结果。
花了十年证明 ETH 条件下界的研究者们,眼看着前提在两周内坍塌。这就是 Wired 笔下的"毁灭"——不是结果错了,而是结果突然无处着力。
4. 密码学重新审视地基
现代密码学刻意建立在困难性猜想而非 ETH 之上。但此事件 sharpen 了一个不舒服的问题:如果 AI 能推翻一个被数千篇论文倚靠了 27 年的结构性猜想,下一个是哪个?格假设、分解启发式、后量子候选,如今都多了一个星号:假定对 AI 辅助攻击也是难的。可以预期一波正式建模"可运行数月自动证明搜索的对手"的论文,以及带 Lean 可验证安全性证明的假设的溢价。
5. 理论的研究方式与教学方式都在变
Scott Aaronson 的博客近期刊出广为流传的客座文章《Theory Beyond Theorems and Proofs》,主张"AI 陨石"已经落地,STOC/FOCS 时代的理论文化必须演进(Shtetl-Optimized)。当下的争论是:当机器能搜索证明空间,什么仍然是人所独有的? emerging 的共识有三条腿:
- 选题与品味——在一万条可证明的陈述里决定哪条值得证。
- 验证与形式化——把 AI 论证送过 Lean,这是真正的技术劳动(ETH 的检验花了约十天)。
- 意义建构——把机器找到的构造转化为领域能理解、能讲授、能继续建造的思想。
与此同时,计算机系——2025 年调查中 68% 的项目已围绕 AI 工具重组课程——在思考:当学生可以向模型要一份证明思路时,理论课该教什么?给学生的实际答案是:定义与归约依然重要,因为它们正是你指挥、检验与解读 AI 输出所需的全部。
通往 2026 年 10 月之路:时间线
| 年份 | 事件 | 意义 |
|---|---|---|
| 2022 | AlphaTensor(Nature) | 强化学习首次改进尘封 50 年的矩阵乘法纪录 |
| 2023 | AlphaDev 进入 LLVM libc++ | AI 写的代码进入标准库 |
| 2023 | FunSearch(Nature) | 首个由 LLM 完成的数学发现(cap set) |
| 2024 | AlphaProof:IMO 银牌 | 研究级形式化证明达到奥赛银牌水准 |
| 2025 | AlphaEvolve | 打破 Strassen 1969 方案;收回 Google 0.7% 算力 |
| 2025 | Gemini + Aristotle:IMO 金牌 | 形式化推理达金牌水准 |
| 2026.08 | OpenAI《十项进展》 | AI 成果横跨几何、密码学、复杂度(OpenAI) |
| 2026.09 | 《Theory Beyond Theorems and Proofs》 | TCS 社区公开反思其会议与价值观(Shtetl-Optimized) |
| 2026.10 | ETH 被推翻(OpenAI,Lean 检验;Anthropic 独立) | 一块基石猜想倒在 AI 搜索之下(Wired) |
怀疑者怎么说
突破是真的,但社区并未照单全收:
- 验证的人工成本是真实的。 十天的 Lean 形式化是专家劳动。"AI 证明了"目前往往意味着"AI 提出、人类检验"。
- 低质论文洪峰将至。 若模型能规模化生成貌似可信的证明,期刊与 arXiv 将需要 Lean 式验证作为默认过滤器,否则会被淹没。
- 否定 ≠ 构造。 知道 ETH 不成立,不等于得到一个干净、可讲授的次指数算法。领域仍需要机器构造里面的思想。
- 署名与激励。 机器找到的定理该署名谁——模型、操作者还是实验室?STOC/FOCS 还在写这些规则。
对你意味着什么
如果你是计算机系学生:基础刚刚变得更值钱,而不是更不值钱。归约、不变量、复杂度类正是你用来监督 AI 推理的语言。课程上向逻辑、形式化方法与证明助手倾斜。
如果你是研究者:以 ETH 为前提的条件下界纲领需要重想。增长点在:形式化、证明验证、"下一个倒下的是哪个猜想"的结构性工作,以及关于 AI 辅助数学本身的元问题。
如果你是工程师:本季度敲键盘的方式几乎不变——SAT 求解器不会突然变快。变的是天花板:推翻 ETH 的同一族模型,同样在发现调度、编译与基础设施优化(AlphaEvolve 的 0.7% 集群回收正来源于此)。
从定理到像素:同一波浪,不同的岸
把这条线索与我们在 GrokImage.ai 做的事连起来:驱动研究突破与驱动创作生成的,是同一种前沿模型能力——在天文数字解空间中的深度搜索、自我验证与迭代。 能在证明空间里猎出次指数算法的模型,与能凭一句话渲染照片级场景、能真正理解图像内容再动手编辑的模型(我们在 Grok 4.6 发布分析中详细讲过这一视觉跃迁),是近亲。
实际的区别在于可得性。你还没法与前沿实验室合证一条复杂度定理,但你今天就能把这波浪的生成侧用起来:
如果你更偏创作者而非理论家,从我们的 AI 图像提示词完全指南开始——提示词工程,往小了说,就是一种在可能性空间上的应用搜索。
常见问题
AI 解决 P vs NP 了吗?
没有。推翻 ETH 只说明 SAT 存在次指数算法——比任何 2^εn 都快,但仍超多项式。P vs NP 依然悬而未决,十月的结果对两个方向都没有定论。
用大白话解释:指数时间假设是什么?
它是 Impagliazzo 与 Paturi 1999 年提出的猜想:不存在次指数时间求解 3-SAT 的算法——实例本质上需要 2^εn 量级的时间。它是数千条"假设 SAT 难,则问题 X 也难"定理的承重墙。
AI 会取代理论计算机科学家吗?
证据指向重组而非取代。机器搜索证明空间;人类定义问题、在 Lean 中验证、提炼可迁移的思想。职位描述变了——品味、形式化能力与判断力成为稀缺资产。
Lean 是什么?验证为什么重要?
Lean 是交互式定理证明器:证明的每一步都被机器对照逻辑规则检验,因此 Lean 验证过的论证不可能藏着隐蔽漏洞。这正是 AI 找到的证明一旦形式化进 Lean 就被认真对待的原因。
这对日常 AI 工具有什么影响?
今天看,直接影响很小;拉长看,影响巨大。同一套推理与搜索的进步驱动着两者:在 GrokImage.ai 上编辑你照片、生成图像的模型,与发现算法的系统,训练在同一条扩展曲线上。同一波浪,很多岸。
来源:Wired · TechCrunch · The Next Web · OpenAI · Shtetl-Optimized(Scott Aaronson) · DeepMind