OpenAI 和 Anthropic 各自发表了证明，认为指数时间假设为假。
ETH 是理论计算机科学中已有 27 年历史的一个假设，认为某些问题不可能比穷举法快太多。如今，顶尖 AI 实验室表示事实并非如此。
如果这些证明经得起检验，它们将成为迄今由 AI 生成的计算机科学领域最重要的成果。同时，这也迫使人们重新审视数以百计以 ETH 为前提的研究论文。
本文将解释指数时间假设究竟意味着什么，以及与之相关的 P 对 NP 问题。我们还将看看两家实验室具体声称了什么、证明如何被核验、以及对密码学有哪些改变（以及哪些不变）。
用通俗语言解释 P 对 NP
P 对 NP 询问：是否每个“答案容易核验”的问题也都“容易求解”。它是七大千禧年难题之一，即便在这条新闻之后仍未解决。
数独是经典示例。核验一个已填好的棋盘只需几秒：检查每行、每列和每个宫是否有重复。而从一个接近空白的棋盘找出解答可能要长得多，且随着棋盘规模增长，这一差距会迅速扩大。
- P 是计算机能在多项式时间内求解的问题类，意味着随着输入规模 n 增长，工作量按 n2、n3 等多项式增长。
- NP 是计算机能在多项式时间内核验备选解的问题类。
P 中的每个问题也都属于 NP。未解的问题在于反过来是否成立。大多数计算机科学家相信 P ≠ NP，即有些问题在本质上“求解”比“核验”更难。现代密码学基于这一信念：加密很容易，但没有密钥要解密应当很难。
什么是指数时间假设？
ETH 更为尖锐：它声称 NP 中一个特定问题——3-SAT——无论算法多么聪明，都需要指数时间。加州大学圣迭戈分校的 Russell Impagliazzo 与 Ramamohan Paturi 在 20 世纪 90 年代末提出了这一假设，Francis Zane 对奠基性工作亦有贡献。
3-SAT 问题
在 3-SAT 中，您得到一个由 n 个真/假的变量和一组子句构成的公式。每个子句用“或”连接三个条件，例如“x₁ 为真或 x₄ 为假或 x₇ 为真”。任务是找到一种变量赋值，使所有子句同时满足。
穷举法会尝试全部 2ⁿ 种赋值，因此每增加一个变量，工作量就翻倍。可以想见，当变量数接近 100 时几乎无望。
ETH 的表述
ETH 断言存在常数 c > 1，使得没有算法能以快于 cⁿ 的时间解 3-SAT。巧妙的算法可以把底数从 2 降低，但永远降不到次指数级。形式化地：存在 δ > 0，使得 3-SAT 不能在 O(2δn) 时间内解出。
数十年来，进展与这幅图景相符。研究人员不断把底数往下砍，但它始终远大于 1。由于 3-SAT 可被转换为许多其他问题，ETH 成为一个工作马式的假设。研究者用它来论证诸如 Clique、Vertex Cover、Independent Set 等问题也不能快太多。
新结果的对比
| 方法 | 3-SAT 的运行时间 | 是否指数增长？ |
|---|
| 穷举法 | 2ⁿ | 是 |
| 2026 年 10 月前最佳（确定性） | 约 1.328ⁿ | 是 |
| 2026 年 10 月前最佳（随机化） | 约 1.308ⁿ | 是 |
| OpenAI 与 Anthropic（2026 年 10 月） | 2^O(n log log n / √log n) | 否：次指数级 |
新的上界可简写为 2o(n)。随着 n 增长，每增加一个变量的代价趋向于 1，而这正是 ETH 认为不可能的。
OpenAI 和 Anthropic 公布了什么
两家实验室各自独立地得到本质相同的次指数上界，并都用 Lean 形式化证明助理给论文提供了机助核验。
| | OpenAI | Anthropic |
|---|
| 论文 | "The Exponential Time Hypothesis Is False"（67 页） | "A 2o(n) Time Algorithm for 3-SAT"（49 页） |
| 模型 | 未命名的内部模型 | 内部 Claude 研究模型，署名为作者 |
| 核心思路发现时间 | 2026 年 10 月 16 日 | 2026 年 10 月 16 日 |
| 公开时间 | 2026 年 10 月 26 日 | 2026 年 10 月 26–27 日 |
| 核验 | Lean 证明了一个稍弱但仍足以推翻 ETH 的上界 | 在 Mathlib 上用 Lean 4 证明，并由第二个内核复核 |
| 额外主张 | 提速不适用于整个 NP | 亦推翻强 ETH（SETH）；给出新的电路下界 |
Anthropic 表示，Claude 在无人工输入的情况下产出了约 1400 万个 token 后找到了核心算法。其方法使用张量网络与秩论证。随后研究人员协助完成终稿。
为何两家同日发现？
两家实验室都未解释具体原因。Anthropic 的论文称两项结果彼此独立且并发，两篇文章也沿着不同的数学路径达成了本质相同的上界。
一些背景使得这种重合并不如乍看那样意外。两家实验室一直在让各自的模型攻克大量未解问题，且仅 OpenAI 就在 10 月上旬发布了数百篇 AI 生成的数学手稿。ETH 是该领域最知名的靶标之一，而两者都学习了同样已发表的研究。独立且同时的发现在科学史上也是常见模式，如牛顿与莱布尼茨在微积分，或达尔文与华莱士在自然选择。
这些证明有多扎实？
Lean 能确认形式化陈述可由其公理逻辑推导。但它无法确认该形式化陈述与论文中的口头表述完全一致。Anthropic 指出，没有机器会核查这两者的对应关系；OpenAI 也表示其 Lean 文件证明的是一个较标题略弱的上界。
目前，最初提出该问题的研究者 Impagliazzo 与 Paturi，以及 MIT 的 Ryan Williams，正组织研讨会评估这些形式化陈述是否真正刻画了 ETH。他们的公开信强调，参与评审不等于背书。截至本文写作时，尚无人公开发现漏洞。
Williams 表示，OpenAI 证明中的部分内容看起来较为常规，而“另有两三处像外星人写的部分”仍需仔细审视。ETH 的作者之一 Impagliazzo 将这一结果形容为“深感意外”。
哪些会改变，哪些不会
在实践中，几乎没有任何即时改变（呼）：新算法只会在远超任何计算机所能容纳的超大输入上优于穷举法。
不会带来更快的 SAT 求解器
Anthropic 的论文称，其方法只会在天文规模的输入上战胜穷举。对典型的“每个变量约五个子句”的公式，交叉点是一个大约有 1 万位数字的数；在最一般情形下，这个交叉点大约有 1 亿位数字。
作者还表示，他们的方法不太可能对低于约 1000 万个变量的情形有帮助。用于芯片验证、调度与规划的 SAT 求解器不会因这一结果而变快。
密码学未被攻破
该结果并未触及 P 对 NP。没有人声称这一点。OpenAI 表示其已经检查过该算法是否会攻破现实中的密码系统，并且相当有信心它不会。
理论将被重写
更大的影响在于研究。建立在 ETH 或 SETH 之上的困难性结果如今需要新的依托，一些研究者表示自己多年的工作可能需要重审。当然并非一切都坍塌。Anthropic 指出，该结果并未推翻正交向量问题，而后者支撑着许多细粒度复杂性结果。
这对 AI 有何意义
标题的重点不在 3-SAT 本身，而在于“是谁找到答案”：两个 AI 系统彼此独立地推翻了一个人类专家一代人都信奉的猜想。
AI 作为研究合作者
研究人员如今形容，每一两周就会有新的 AI 结果落地，打断正在进行的项目。像 Lean 这样的形式化工具正变得核心，因为它们让人类无需重推每一行，也能信任一篇冗长的机器撰写证明。
隐藏的捷径与自我改进
ETH 代表着一种信念：某些搜索问题不存在巧妙捷径。如果这信念是错的，其他看似显然很难的问题也许同样隐藏着捷径。
我在思考算法发现这一方向，在递归式自我改进方面可能意义重大——即 AI 系统帮助设计更好的 AI。用 AI 寻找更快的算法是迈向这一目标的具体路径之一，尽管眼下该结果本身并未直接做到这一点。
这对数据从业者意味着什么
对以数据为业的人来说，有三点启示：
- 复杂性理论并非只是学术：知道一个问题为何是 NP 困难，可以指导您何时考虑启发式、近似或求解器，而不是精确搜索。
- 核验是一项技能：随着 AI 生成更多代码与分析，核查其输出（通过测试、证明或可复现流程）与产出本身同等重要。
- 渐近分析可能误导：理论上“更快”的算法在真实规模下可能毫无用处。
结论
如果这些证明能通过专家评审，指数时间假设将加入“广为相信却被证明为假”的短名单（如欧拉幂和猜想）。但 P 对 NP 仍未解决，密码学目前依旧安全。
接下来值得关注的里程碑包括：由 ETH 原作者牵头的评审研讨会、算法的独立复现实现、以及是否有人能进一步收紧上界。
若想打好理解此类故事的基础，欢迎学习我们的课程：数据结构与算法、Python 编程与机器学习。它们涵盖使此类结果可读的大 O 思维。
OpenAI 和 Anthropic 各自发表了证明，认为指数时间假设为假。
ETH 是理论计算机科学中已有 27 年历史的一个假设，认为某些问题不可能比穷举法快太多。如今，顶尖 AI 实验室表示事实并非如此。
如果这些证明经得起检验，它们将成为迄今由 AI 生成的计算机科学领域最重要的成果。同时，这也迫使人们重新审视数以百计以 ETH 为前提的研究论文。
本文将解释指数时间假设究竟意味着什么，以及与之相关的 P 对 NP 问题。我们还将看看两家实验室具体声称了什么、证明如何被核验、以及对密码学有哪些改变（以及哪些不变）。
用通俗语言解释 P 对 NP
P 对 NP 询问：是否每个“答案容易核验”的问题也都“容易求解”。它是七大千禧年难题之一，即便在这条新闻之后仍未解决。
数独是经典示例。核验一个已填好的棋盘只需几秒：检查每行、每列和每个宫是否有重复。而从一个接近空白的棋盘找出解答可能要长得多，且随着棋盘规模增长，这一差距会迅速扩大。
P 中的每个问题也都属于 NP。未解的问题在于反过来是否成立。大多数计算机科学家相信 P ≠ NP，即有些问题在本质上“求解”比“核验”更难。现代密码学基于这一信念：加密很容易，但没有密钥要解密应当很难。
什么是指数时间假设？
ETH 更为尖锐：它声称 NP 中一个特定问题——3-SAT——无论算法多么聪明，都需要指数时间。加州大学圣迭戈分校的 Russell Impagliazzo 与 Ramamohan Paturi 在 20 世纪 90 年代末提出了这一假设，Francis Zane 对奠基性工作亦有贡献。
3-SAT 问题
在 3-SAT 中，您得到一个由 n 个真/假的变量和一组子句构成的公式。每个子句用“或”连接三个条件，例如“x₁ 为真或 x₄ 为假或 x₇ 为真”。任务是找到一种变量赋值，使所有子句同时满足。
穷举法会尝试全部 2ⁿ 种赋值，因此每增加一个变量，工作量就翻倍。可以想见，当变量数接近 100 时几乎无望。
ETH 的表述
ETH 断言存在常数 c > 1，使得没有算法能以快于 cⁿ 的时间解 3-SAT。巧妙的算法可以把底数从 2 降低，但永远降不到次指数级。形式化地：存在 δ > 0，使得 3-SAT 不能在 O(2δn) 时间内解出。
数十年来，进展与这幅图景相符。研究人员不断把底数往下砍，但它始终远大于 1。由于 3-SAT 可被转换为许多其他问题，ETH 成为一个工作马式的假设。研究者用它来论证诸如 Clique、Vertex Cover、Independent Set 等问题也不能快太多。
新结果的对比
新的上界可简写为 2o(n)。随着 n 增长，每增加一个变量的代价趋向于 1，而这正是 ETH 认为不可能的。
OpenAI 和 Anthropic 公布了什么
两家实验室各自独立地得到本质相同的次指数上界，并都用 Lean 形式化证明助理给论文提供了机助核验。
Anthropic 表示，Claude 在无人工输入的情况下产出了约 1400 万个 token 后找到了核心算法。其方法使用张量网络与秩论证。随后研究人员协助完成终稿。
为何两家同日发现？
两家实验室都未解释具体原因。Anthropic 的论文称两项结果彼此独立且并发，两篇文章也沿着不同的数学路径达成了本质相同的上界。
一些背景使得这种重合并不如乍看那样意外。两家实验室一直在让各自的模型攻克大量未解问题，且仅 OpenAI 就在 10 月上旬发布了数百篇 AI 生成的数学手稿。ETH 是该领域最知名的靶标之一，而两者都学习了同样已发表的研究。独立且同时的发现在科学史上也是常见模式，如牛顿与莱布尼茨在微积分，或达尔文与华莱士在自然选择。
这些证明有多扎实？
Lean 能确认形式化陈述可由其公理逻辑推导。但它无法确认该形式化陈述与论文中的口头表述完全一致。Anthropic 指出，没有机器会核查这两者的对应关系；OpenAI 也表示其 Lean 文件证明的是一个较标题略弱的上界。
目前，最初提出该问题的研究者 Impagliazzo 与 Paturi，以及 MIT 的 Ryan Williams，正组织研讨会评估这些形式化陈述是否真正刻画了 ETH。他们的公开信强调，参与评审不等于背书。截至本文写作时，尚无人公开发现漏洞。
Williams 表示，OpenAI 证明中的部分内容看起来较为常规，而“另有两三处像外星人写的部分”仍需仔细审视。ETH 的作者之一 Impagliazzo 将这一结果形容为“深感意外”。
哪些会改变，哪些不会
在实践中，几乎没有任何即时改变（呼）：新算法只会在远超任何计算机所能容纳的超大输入上优于穷举法。
不会带来更快的 SAT 求解器
Anthropic 的论文称，其方法只会在天文规模的输入上战胜穷举。对典型的“每个变量约五个子句”的公式，交叉点是一个大约有 1 万位数字的数；在最一般情形下，这个交叉点大约有 1 亿位数字。
作者还表示，他们的方法不太可能对低于约 1000 万个变量的情形有帮助。用于芯片验证、调度与规划的 SAT 求解器不会因这一结果而变快。
密码学未被攻破
该结果并未触及 P 对 NP。没有人声称这一点。OpenAI 表示其已经检查过该算法是否会攻破现实中的密码系统，并且相当有信心它不会。
理论将被重写
更大的影响在于研究。建立在 ETH 或 SETH 之上的困难性结果如今需要新的依托，一些研究者表示自己多年的工作可能需要重审。当然并非一切都坍塌。Anthropic 指出，该结果并未推翻正交向量问题，而后者支撑着许多细粒度复杂性结果。
这对 AI 有何意义
标题的重点不在 3-SAT 本身，而在于“是谁找到答案”：两个 AI 系统彼此独立地推翻了一个人类专家一代人都信奉的猜想。
AI 作为研究合作者
研究人员如今形容，每一两周就会有新的 AI 结果落地，打断正在进行的项目。像 Lean 这样的形式化工具正变得核心，因为它们让人类无需重推每一行，也能信任一篇冗长的机器撰写证明。
隐藏的捷径与自我改进
ETH 代表着一种信念：某些搜索问题不存在巧妙捷径。如果这信念是错的，其他看似显然很难的问题也许同样隐藏着捷径。
我在思考算法发现这一方向，在递归式自我改进方面可能意义重大——即 AI 系统帮助设计更好的 AI。用 AI 寻找更快的算法是迈向这一目标的具体路径之一，尽管眼下该结果本身并未直接做到这一点。
这对数据从业者意味着什么
对以数据为业的人来说，有三点启示：
结论
如果这些证明能通过专家评审，指数时间假设将加入“广为相信却被证明为假”的短名单（如欧拉幂和猜想）。但 P 对 NP 仍未解决，密码学目前依旧安全。
接下来值得关注的里程碑包括：由 ETH 原作者牵头的评审研讨会、算法的独立复现实现、以及是否有人能进一步收紧上界。
若想打好理解此类故事的基础，欢迎学习我们的课程：数据结构与算法、Python 编程与机器学习。它们涵盖使此类结果可读的大 O 思维。