撑了27年的计算理论地基被抽走：OpenAI算法与它推翻的指数时间假说

如果一个猜想你提出来27年，全世界都把它当成公理在用，突然有一天别人发来一段代码，证明你当年猜错了，你会怎么做？

加州大学圣迭戈分校的计算机教授因帕利亚佐，现在就坐在这么一个位置上。

给他寄来算法的甚至不是同行学者，直接来自 OpenAI 的内部模型。

更绝的是，对方把论文手稿和证明代码往网上一挂，还掏出 500 万美元设立专项基金，指名请因帕利亚佐这位假说的提出者亲自牵头，来核验这段代码算得对不对。

很多人这几天刷到这条新闻，只觉得又是人工智能在刷存在感。

但只要在理论计算机领域待过的人，看到这个消息，后背全是凉的。

这次被动了刀子的，叫指数时间假说，学术界习惯简称它为 ETH。

我们都知道计算机科学里有一个至今没人能解开的终极难题，叫 P 与 NP 问题。

通俗点说，面对那些极其复杂的难题，人类到底能不能找到像查乘法口诀表一样飞快的多项式算法？

这个大门至今谁也推不开。

既然不知道到底能不能极快地解决，1999 年，因帕利亚佐和帕图里这两位学者就退了一步。

他们提出了一个非常朴素、但看起来极其坚固的假说：

面对最经典的逻辑判定难题，比如 3-SAT 问题，无论你怎么优化算法，都不可能比盲目穷举快到天上去。

算法消耗的时间，必须老老实实维持在指数级别。

就是这么一个看起来合情合理的假设，在随后的 27 年里，成了整整一代计算机学者的隐形地基。

图论、复杂网络、计算生物学、密码学……成百上千篇顶尖论文，只要想证明某个问题在现实中极其难算，推导不出绝对边界时，就会在论文里写上一句：

假设 ETH 成立，那么该问题绝不可能在亚指数时间内解决。

大家都把这句话当成了默认公理。

既然底层假设没人能推翻，上面盖起来的几千座理论大厦就坚不可摧。

结果，OpenAI 这次扔出来的算法，硬生生把 3-SAT 的计算时间压进了亚指数。

那根撑了 27 年的承重柱，突然被一段代码抽掉了。

更让学者们觉得不可思议的，是这个模型推翻假说的方式。

它没有走常规路线去判断这组逻辑到底有没有解。

它给出的确定性算法，是在极小的多项式内存空间里，精确数出一共有多少个满足条件的解。

做过计算复杂性的人都知道，在算法世界里，数出所有解的难度，比碰巧撞上一个解要高出几个维度。

这就像在大海里捞针。

碰运气摸出一根针已经很难了，要求你在一滴水不漏的前提下，把海底藏着的一千零二十三根针一颗不差全数清楚，算力消耗根本无法想象。

这个模型直接把更难的数解问题做到了亚指数。

那个原本卡了人类几十年的判定版假说，反倒成了一个顺带被碾过去的副产品。

消息一出来，网上很多人开始喊：是不是 P 与 NP 问题被解决了？

并没有。

亚指数时间确实比指数穷举快了一大截，但它依然不是多项式时间。

P 与 NP 的终极大门依然紧闭着，现代密码学的大厦也没有塌。

但过去 27 年里，所有写着某某问题不可能快速解决的论文，结论全部得重新打上一个大大的问号。

理论的边界突然被撕开了一个口子。

让人吃惊的是，推翻 ETH 还只是这次公布的其中一项。

在它旁边，还有另外两个同样卡了人类几十年的硬骨头。

一个是纯数学里的挂谷猜想。

这个问题最早源于一个非常生活化的几何脑筋急转弯：一根长为 1 的针在桌面上原地调个头，转过的最小面积是多少？

后来它演变成调和分析里极其抽象的波聚焦与偏微分方程问题。

包括陶哲轩在内的一大批顶尖数学家，过去几十年只能在低维度上极其艰难地往前推。

这次模型构造出了一个人类以前没见过的辅助偏微分方程，证明了索格在 1991 年提出的全维度局部平滑猜想，顺带着把所有维度的挂谷猜想和斯坦因限制猜想一起给结了。

另一个则是物理学里描述强核力的杨-米尔斯场论。

模型给出了一套严格的数学推导，证明了四维空间中带费米子的量子色动力学在数学上确实存在，直接切入了千禧年大奖难题之一的核心腹地。

以往学术界如果收到谁宣称推翻了重大猜想，第一反应往往是扔进垃圾桶，因为人类手写的几百页证明里总是塞满了笔误和逻辑漏洞。

但这次不一样。

推导过程不再写在草稿纸上，全部直接变成了 Lean 语言的机器形式化代码。

在 Lean 这种交互式定理证明器里，没有任何一步可以靠显然成立糊弄过去。

代码能通过编译，就意味着每一环逻辑都被数学内核强行校验过。

OpenAI 也没有急着给自己挂上第一作者的名头去领奖。

他们把代码完整公开在 GitHub 上，把物理学的推导交给了 2004 年诺贝尔物理学奖得主戴维·格罗斯牵头的学者团队，把算法的推导直接交给了当年提出假说的因帕利亚佐和帕图里。

因帕利亚佐在公开信里写得很谨慎：参与核验绝不代表立刻背书，这种级别的结论需要极其漫长和严密的独立审查。

这当然需要时间，谁也不知道在浩瀚的代码细节里会不会藏着未被发现的边界条件。

但当白发苍苍的理论宗师必须打开电脑，逐行核对一段机器代码怎样推翻自己 27 年前写下的假说时，有些事情确实已经悄悄改变了。