2026年10月，OpenAI宣布其AI模型证伪了“指数时间假设”（ETH），一个统治理论计算机科学近30年的基础性猜想。这个消息之所以震动学界，是因为ETH并非一个孤立的猜想，它是在我们熟悉的P vs NP问题之下，支撑着整个“细粒度复杂度”领域大厦的地基性假设。

ETH的动摇，不意味着P=NP，但它意味着我们过去对“NPC问题到底有多难”的定量认知，可能需要大规模重写。要理解这件事的分量，我们需要从最经典的复杂度地图开始，一步步走到这张地图之下更精细的“地下结构”

P, NP, NPC与NP-hard

理论计算机科学用集合来刻画问题的计算难度。最核心的几个集合，构成了我们理解计算极限的第一张地图。

1. 四个核心集合的定义

• P（多项式时间） ：可以理解为“ 能实际算出来 ”的问题。存在一个算法，其运行时间随输入规模 \(n\) 的增长，不会快于某个多项式（如 \(n^2, n^3\)）。这类问题被认为是 可行（feasible） 的。
• NP（非确定性多项式时间） ：可以理解为“ 答案容易验证 ”的问题。给定一个候选答案，我们能在多项式时间内检查它是否正确。显然，P 是 NP 的子集，因为能算出来的自然也能验证。
• NP-hard（NP-难） ：这是“ 至少和NP中所有问题一样难 ”的问题集合。形式化地说，所有NP问题都能通过多项式时间 规约 （转换）到它。关键在于，NP-hard问题 自身不一定属于NP 。它可以比NP中的任何问题都难，甚至可以是不可判定的（如著名的停机问题）。
• NPC（NP-完全） ：这是NP中最“核心”的一类难问题。定义为 NPC = NP ∩ NP-hard 。一个NPC问题必须满足两个条件：它 本身是NP问题 ，同时它 又是NP-hard的 。SAT（布尔可满足性问题）是历史上第一个被证明的NPC问题，其他经典例子还包括哈密顿回路、子集和问题等。

2. 集合关系

它们的关系可以用集合包含来精确表达： \[ P \subseteq NP \] \[ NPC = NP \cap NP\text{-}hard \] \[ NPC \subseteq NP, \quad NPC \subseteq NP\text{-}hard \]

需要特别注意的是，NP-hard 并不包含 NP。NP-hard 与 NP 的交集才是 NPC，而 NP-hard 在 NP 之外的部分，包含了比 NP 更难的“怪物”。

3. 旅行商问题（TSP）到底是什么？

过于出名，以至于我们专门讨论下。

这是一个经常让人混淆的例子。我们口语中说“旅行商问题是NPC”，其实省略了“决策版”三个字。

• TSP优化版 ：给定一系列城市和距离，求访问每个城市恰好一次并回到起点的 最短 路线。这是一个求最优解的 函数问题/优化问题 。它极其困难，是 NP-hard 的，但它本身不属于 NP（因为 NP 是判定问题的集合，答案只能是“是”或“否”）。
• TSP决策版 ：给定城市、距离和一个整数 \(K\)，问是否存在一条总长度 不超过 \(K\) 的巡回路线？这就变成了一个判定问题，答案是“是”或“否”。这个版本不仅是 NP 问题，而且是 NP-hard 的，因此 它是 NPC 问题 。

另外一个重要的点是NP中间问题。拉格纳（Ladner）定理证明：如果 \(P \ne NP\)，那么在 P 和 NPC 之间，必定存在无穷多个既不属于 P 也不属于 NPC 的问题。比如整数分解的判定版（问 \(N\) 是否有不超过 \(k\) 的因子），它大概率是一个典型的 NP 中间问题。

我们还能讨论一些其他的比较著名的问题例子：

区域	例子
P	2-SAT、欧拉回路判定、最短路判定
NP 中非 NPC	上面的 P 问题；若 \( P\ne NP \) ，还有 NP 中间问题，如整数分解判定、图同构等候选
NPC	SAT、3-SAT、哈密顿回路、子集和、TSP 决策版
NP-hard 但不在 NP	停机问题；NEXPTIME 完全问题等
不属于判定问题集合	TSP 优化版是优化问题，严格说不在 NP/NPC 里；通常称它是 NP-hard 优化问题

4. 为什么解决一个 NPC 就能带来连锁反应？

这是一个极其深刻的逻辑链条：如果任何一个 NPC 问题（哪怕只有一个）被证明属于 P，那么 P 将等于 NP。

为什么？逻辑如下： 1. 假设你找到了某个 NPC 问题 \(B\) 的多项式时间算法。 2. 对于任意一个 NP 问题 \(A\)，根据 NPC 的定义，必然存在一个多项式时间的“规约”过程，把 \(A\) 的输入转化为 \(B\) 的输入。 3. 于是，解开 \(A\) 的算法就是：把 \(A\) 转化为 \(B\)（多项式时间），用你发现的超快算法解开 \(B\)（多项式时间），再把答案转回来（多项式时间）。整个流程依然是多项式时间。 4. 这意味着所有 NP 问题都能被有效解决。

所以：

“存在一个 NPC 可被 P 解决” 是 “任意 NP 可被 P 解决”的充分且必要条件（两者等价于 P=NP）。

但这里有一个极大的误区：解决一个 NPC 的“具体实例”（比如你解出了一个具体的 SAT 公式），并不等于解决了这个问题类，也无法推导出所有 NP 问题被解决。P=NP 要求的是给出一个处理所有可能输入的通用多项式算法。

为什么边界是多项式时间

你可能会问：为什么把“可行”的边界划在多项式时间？FGH（快速增长层级）里有那么多层级，为什么不选别的？

这源于一个被称为 Cobham-Edmonds 论题的基础约定：一个计算问题在实践上是可行的，当且仅当它属于 P 类。

选择多项式时间并不是随便选的，它具备其他任何增长率层级都不具备的结构稳健性： 1. 对组合封闭：如果你写一个程序，调用的子程序都是多项式时间的，且主程序逻辑也是多项式时间的，整体依然是多项式时间的。这意味着“可行”的算法可以像积木一样无限次安全嵌套。 2. 对机器模型不变：无论你用单带图灵机、多带图灵机还是现代计算机的 RAM 模型，它们互相模拟带来的时间开销最多是多项式级别的。因此，“一个问题是否在 P 中”是一个与具体设备无关的客观事实。如果选一个 FGH 中随意的增长率，你定义的复杂度类可能会随着机器模型的改变而崩塌。 3. 时间可构造性：多项式时间恰好落在“既足够精细以区分难度，又足够稳健以独立于模型”的甜点区。FGH 中的很多高阶函数甚至无法被图灵机用来作为计算时间界限。

细粒度复杂度与神秘的 \(n^{3-\varepsilon}\)

P vs NP 的二分法太粗糙了。一个 \(n^2\) 的算法和一个 \(n^{100}\) 的算法，在实际中是天壤之别。为了刻画 P 类内部的精细地形，细粒度复杂度（Fine-Grained Complexity） 诞生了。

在这个领域，科学家们不再满足于“多项式时间”这种模糊结论。他们要把指数“抠”到极致。为了严谨表达，他们引入了记号：\(n^{3-\varepsilon}\)。

• \(\varepsilon\)（Epsilon）是一个 任意小但固定的常数 。比如 \(\varepsilon = 0.001\)，就是 \(n^{2.999}\)。
• 说一个问题“ 不存在 \(O(n^{3-\varepsilon})\) 算法（对任意 \(\varepsilon>0\)） ”，严谨的量化含义是： 对于每一个正数 \(\varepsilon\)，无论它有多小，你都休想找到比 \(n^{3-\varepsilon}\) 更快的算法 。它等价于说该问题的下界是 \(n^{3-o(1)}\)。
• 指数 3 是一堵“硬墙”，你可以削掉低阶项，但绝不能在指数上打任何固定折扣。

在这个领域，有诸如 APSP（全源最短路径）猜想、3SUM猜想 等核心基石，它们断言了某些经典问题不存在诸如 \(n^{3-\varepsilon}\) 或 \(n^{2-\varepsilon}\) 的算法。

数学拆解：为什么那个奇怪的公式依然属于 \(n^3\) 家族？

现实中最著名的 APSP 算法，其当前最优复杂度长这样： \[ n^3 / 2^{\Omega(\sqrt{\log n})} \]

初学者常想：你除以了一个不断增长的东西，这不就比 \(n^3\) 快了吗？为什么还没打破 \(n^3\) 的硬墙？

这里需要拆解两个符号：

1. \(\Omega\)（大 Omega）表示下界 公式里的 \(2^{\Omega(\sqrt{\log n})}\) 意思是：分母的增长速度，至少是 \(2^{c\sqrt{\log n}}\)（\(c\) 为正数常数）。

2. 对数的魔法变换 利用恒等式 \(a^b = 2^{b \log_2 a}\)，我们把分母改写成多项式： \[ 2^{\sqrt{\log n}} = (2^{\log n})^{1/\sqrt{\log n}} = n^{1/\sqrt{\log n}} \] 代入公式： \[ \frac{n^3}{2^{\Omega(\sqrt{\log n})}} = \frac{n^3}{n^{\Omega(1/\sqrt{\log n})}} = n^{3 – \Omega(1/\sqrt{\log n})} \]

这里出现了一个关键：减去的指数 \(\Omega(1/\sqrt{\log n})\) 是一个随着 \(n\) 变大而不断趋近于 0 的量。在数学上，这被称为 小 \(o\)（小 o），记作 \(o(1)\)。

所以，这个复杂度的真面目是：\(n^{3-o(1)}\)。

小 \(o\) 的定义是：分子除以分母的极限为 0。 它意味着，虽然这个算法确实比纯粹的 \(n^3\) 快，但它快的那一部分（\(o(1)\)）会随着 \(n\) 增大而无限缩小，最终趋近于无。

而之前提到的 \(\varepsilon\) 是一个固定常数。无论你的 \(\varepsilon\) 定得多小（比如 \(10^{-10}\)），随着 \(n\) 趋于无穷大，\(o(1)\) 最终一定会小于 \(\varepsilon\)。这就意味着，\(n^{3-o(1)}\) 永远比 \(n^{3-\varepsilon}\) 慢。它依然没有打破 \(n^3\) 的硬墙，只是把墙皮稍微蹭掉了一点点。

ETH是什么？OpenAI又干了什么？

ETH（指数时间假设） 是细粒度复杂度的第一块地基。它由 Impagliazzo 和 Paturi 在 1999 年提出，断言：

3-SAT 问题不存在亚指数时间的通用解法。

严格地说，ETH 断言 3-SAT 不存在 \(O(2^{\varepsilon n})\) 算法（对任意 \(\varepsilon>0\)，其中 \(n\) 为变量数）。这比 P ≠ NP 强得多：P ≠ NP 只说它没有多项式算法；ETH 则说它连“比指数稍好一点点”（如 \(2^{\sqrt{n}}\)）的算法都没有。

过去二十多年，大量论文以 ETH 为基石，推导出各种问题“不存在比某个指数更快的算法”的条件性下界。

OpenAI的证伪意味着什么？

OpenAI 声明其模型构造了一个确定性算法，能在 \(2^{O(n/\sqrt{\log n})}\) 时间内解决（甚至精确计数）3-SAT 的受限版本。

这个时间依然是亚指数的，但它远远快于纯粹的 \(2^n\)。这推翻了“3-SAT必须花费本质指数时间”的信念，意味着 ETH 不成立。

这会带来 P=NP 吗？

绝对不会。 \(2^{n/\sqrt{\log n}}\) 对于足够大的输入，依然会爆炸式增长，它仍然远远大于任何多项式时间。3-SAT 依然不被认为属于 P。P vs NP 的边界没有移动。 （注意：这里的时间 \(2^{n/\sqrt{\log n}}\) 与前面的 \(n^3 / 2^{\Omega(\sqrt{\log n})}\) 在数学结构上有奇妙的相似性，都涉及了 \(\sqrt{\log n}\) 这个在亚指数和亚多项式区间的神秘幽灵）。

那么它的真正冲击是？

ETH 被证伪的真正冲击，集中在细粒度复杂度领域。它相当于在这堵“指数墙”上打开了一个缺口。我们并没有走到墙外的多项式世界，但我们发现墙的另一边并非遥不可及。

ETH 这个地基一旦松动，过去二十年建立的成千上万个基于它的“条件性下界”结论，便需要被重新审视，整个领域的知识结构面临大规模修订。

重绘复杂度地图

回到最初的集合框架：ETH 的证伪，并没有改变 P、NP、NPC 这些集合之间的包含关系。

它改变的是我们对 NPC 集合内部问题“硬度刻度” 的认知。以前我们认为所有的 NPC 问题在“指数难度”的区间里是分布极其陡峭的；现在我们发现，有些问题的解法比我们想象的更靠近“可行”的边缘。

在计算复杂度这座宏伟的建筑中，经典的地图（P vs NP）画出了海岸线的轮廓，但水面之下，那层更精细、也更脆弱的“细粒度”结构，正等待着被重新绘制。

意义

1. 一屁股的数学命题得重新审视了，因为很多论文默认ETH是正确的，然后基于此得到了一些界限。现在ETH寄了，这些论文给出的极限都可能可以进一步拓宽了。（相当于之前我们认为秦岭里面有活火山，因此不能修隧道，所有的铁路线都得绕着走，西安到成都至少8h起步，不管你怎么修路架桥。结果一天突然有人证明秦岭是可以打隧道的！那成西高铁修起来就一下子能让旅客节省不少时间了，至少可以低于8h）
2. P≠NP仍然固若金汤！虽然是一个极大进步，但是亚指数复杂度还是不能算作多项式复杂度。

如果说ETH相当于证明了秦岭能打隧道，那P≠NP的难度可能最好情况也是个地心地核隧道，西安直通巴西的那种难度的级别。

最差情况是研发出来空间跃迁科技的难度。