OpenAI用 AI 证伪了指数时间假设（ETH）？

发布日期：2026/10/28 9:39:07      浏览量：

OpenAI 刚刚挑战了计算机科学界 25 年的一个基本信念。

这可能是 AI 科研史上最重要的突破之一。

2026 年 10 月 17 日，OpenAI 发布了一篇论文，标题只有一句话：

《The Exponential Time Hypothesis Is False》

翻译过来就是：

「指数时间假说是错的。」

你可能不知道这意味着什么。

但如果这篇论文最终被证实，它可能会改变我们对计算机能力极限的理解。

我用 16 岁高中生也能听懂的方式解释一下。

先想象一个游戏

你面前有 30 个开关。

每个开关只有两种状态：开或关。

你需要找到一组开关组合，同时满足几百条规则。

问题是：

30 个开关，总共有多少种组合？

答案是：

2³⁰ = 10.7 亿种。

如果有 100 个开关呢？

组合数量就变成一个天文数字。

这就是计算机科学中的经典难题：SAT（布尔可满足性问题）。

过去几十年，科学家普遍相信一个假说：

对于某些 SAT 问题，不管你的算法多聪明，最坏情况下，计算时间都无法避免指数级增长。

这个假说叫 ETH，指数时间假说。

它是计算复杂性理论的重要基础。

然后，OpenAI 的 AI 做了一件惊人的事

它提出了一种全新的算法。

不仅能够判断这些开关有没有满足规则的组合。

还能精确计算到底有多少种合法组合。

更重要的是：

理论上，它的运行时间增长速度突破了 ETH 所假设的指数级下界。

数学家称之为「亚指数时间」。

简单理解：

以前大家以为，你不可能绕开的一堵墙，现在 AI 声称找到了一条路。

而且 OpenAI 还发布了使用 Lean 数学证明系统进行形式化验证的代码。

这是不是意味着所有难题都能秒解？

不是。

这里有两个非常重要的区别：

第一，亚指数时间不等于几秒钟解决问题。面对足够大的问题，算法仍然可能非常慢。

第二，这也不意味着著名的 P vs NP 难题已经解决。

真正的突破不是电脑突然快了 100 万倍，而是我们对计算难度的理论认知可能需要被重新审视。

目前，OpenAI 已公布论文和形式化证明，独立专家仍在审查这一结果。

我觉得最震撼的，其实不是算法本身。

而是一个更大的变化：

过去，我们把 AI 当成回答问题的工具。

后来，它开始帮助人类写代码、做实验、寻找规律。

现在，它开始提出可能改变计算机科学基础理论的证明。

AI 正在从使用人类已知知识，走向帮助人类发现未知知识。

当然，这次研究能否完全经受住学术界的检验，还需要时间。

但一个值得所有年轻人思考的问题已经出现：

如果 AI 不仅能回答考试题，还能挑战写在教科书里的理论，那么未来 10 年，我们应该学会什么？

我认为，答案可能不再只是「学会解决问题」。

而是：

学会提出真正值得解决的问题。

-------------------------------------

很多人看到 OpenAI 刚刚用 AI 证伪了指数时间假设（ETH）

所以，OpenAI要毁灭人类现有的社会秩序了吗？未来是不是 Token 够多，我们就能解决任何问题了？

今天这篇炒的很热的 @OpenAI 的ETH解法论文，普遍大众认知似乎是

1 - PNP问题解决了，所以AI 解决一切万物的时代到来了
2 - 大加速时代来了，万物的解决方案都可以被计算了

仔细花了一个小时细读研究，发现其实并没有大家想的那么夸张。这里简单解释下几个关键概念：

----------------------------------

首先，到底什么是 P vs NP 问题？

我在 16 岁左右刚开始学习算法工程时，曾对 P vs NP 特别痴迷。因为如果它被解决，就说明宇宙万物只要使用足够的算力，就能瞬间获取答案。

简单来说，它的核心是：“可以在多项式时间内【验证】有解决方案的问题，是否等于可以在多项式时间内【获得】解决方案？”

即，可以在多项式时间内证明有解决方案的问题，是否等于可以在多项式时间内获得解决方案。

什么是多项式时间？

简而言之，任何算法都可以边简化为 o(n)，o(n^2) 等等多项式方程，n 是数据的规模，o 则可以通过 n 计算出所需要的计算时间。

换言之，如果 P = NP，则一切事物都可以被计算，相当于人类拿到了宇宙的“作弊码”。

从今往后，只要token够多：

• 我们可以瞬间反向推导，研发出治愈任何绝症的特效药。

•  研发火箭，AI 能在几秒钟内穷尽无数可能，抓出那一个完美的发射方案。

• 物流优化、AI 训练、天气预测……全部可以通过砸Token在几秒内解决

----------------------------------

但是，如果正如主流科学界认为，P ≠ NP，那么很多问题就没法在多项式时间内，而是在指数时间内完成。

什么是指数时间？

指数时间就是说 order of complexity 不是o(n^c)，而是 o(2^n)一类的形式。变量 n 每增加 1，计算量就会直接翻倍。

而存在这类指数时间，且无法转化为多项式时间的问题，就意味着有些问题就算你一直烧Token，也不知道什么时候才能获得解法。

现实中，新药研发的蛋白质折叠、保护你网银安全的 RSA 加密算法，全都是顶级的指数时间难题。就算你把全地球的算力烧干，计算机算到太阳系毁灭也拿不到答案。

一旦 P = NP 成立，指数时间问题可以通过算法工程转化为多项式时间问题，人类可以靠AI创造一切，也可以毁灭并破解一切。

----------------------------------

那么，这次的ETH问题和PNP问题的联系在哪里呢？

大家都在提的点，就是ETH问题证明了3SAT这个指数时间问题有更好的解决方案，所以似乎解决了PNP。

但实际上并不是如此。即便3SAT这个指数时间案例被证伪，PNP仍然没有解决。

为什么？因为这次的ETH问题，本质上是将 o(2^n) 指数时间，转化为了 2^{O(n/\sqrt{\log n})} 这个次指数时间，而这仍然不是多项式时间。

随着n的数量增大，order of complexity的结果仍然会爆炸式增加，只是它不是指数性，而是“次指数性”的。本质上，AI 只是把时间从“几百亿年”缩短到了（比如）“几亿年”。

当然，这也不是说这件事情本身不值得警惕。因为 AI 已经提出了一种人类未曾想到的减少指数时间的方案。

那么，随着 AI 进一步发展，很多原本被判了死刑、认为 “不可能算得更快” 的经典难题，全部重新变成了未解之谜。

也就是说，“指数时间无法成为多项式时间” 这一假设，仍然有被推翻的可能，不过，并不是现在。

就像另外一个 “ETH” 的V神 @VitalikButerin 前段时间针对 ECDSA 算法存在被 AI 攻破的可能性这件事情发表的那句话一样：

在任何数学结构上，比起“刚好只有 3 种解决方案”，“存在隐藏的第 4 种”更有可能。