从 2 到 3 的算力鸿沟：OpenAI 亚指数算法与被撼动的指数时间假说

每条规则里塞两个变量的逻辑题，普通的笔记本电脑一眨眼就能解开。 如果每条规则只多加一个变量，变成三个呢？ 过去半个世纪的标准答案是：全宇宙的计算机加起来，算到世界末日都算不完。 就差这么一个变量。 这就是理论计算机领域最有名的台阶，从 2-SAT 跨到 3-SAT。 当年在大学课堂上听过这道题的人，很多一辈子都忘不了那种冷冰冰的绝望感。

这两天，这个立了二十多年的硬天花板，突然被人从底下撬开了一条缝。 在微软领导过前沿研究、后来加入 OpenAI 的计算机科学家塞巴斯蒂安·布贝克发了一条推文。 他说这是他关注理论计算机二十年来，见过的最大意外。 因为有人宣称，3-SAT 问题被成功跑进了亚指数时间。 拿出这套算法并附带完整机器代码证明的，正是 OpenAI。

这到底是怎么回事？ 我们先看为什么 2 和 3 会差出这么一个银河系。 所谓 2-SAT，可以理解成一堆连环开关： 如果甲是关着的，乙就必须打开；如果乙打开了，丙就必须关上。 每个条件只捆绑两个人。 既然只有两个人，只要定了一个人的状态，另一个人的选择就被瞬间锁死了。 计算机可以顺着箭头画一张因果图，一路往前走，碰壁就换路，几毫秒就能排查完毕。

但只要每条规则变成三个人呢？ 「甲打开，或者乙打开，或者丙打开」。 这时候只要甲是关着的，乙和丙到底谁开谁关？ 因果链在这里分叉了。 计算机没法直接推导，只能先猜一个，两边都去试。 如果一道题里有成百上千个这样的分叉，试错路线就会像雪崩一样翻倍。 这就是经典的指数爆炸。 变量每多几个，运算量直接翻倍，算力很快就会彻底瘫痪。 1971 年史蒂芬·库克证明了 3-SAT 是 NP 完全问题，从那以后，它就成了人类衡量计算难度的一把标尺。

既然彻底解开太难，那能不能退一步，找个稍微快一点的算盘？ 1999 年，两位理论计算机科学家罗素·因帕利亚佐和拉马莫汉·帕图里，提出了著名的「指数时间假说」。 他们给这堵墙焊上了一把重锁。 两位学者的断言很干脆： 别抱幻想了，解 3-SAT 的时间，绝对不可能摆脱指数级别的底色。 无论你怎么优化算法，运算步数最少也得是 2 的常数分之一次方，比如 2 的 0.1n 次方。 只要变量数量上去了，宇宙毁灭前你依然算不完。

这二十多年里，这个假说成了整个计算复杂性理论的承重墙。 计算机科学家们翻不过这堵墙，就干脆把它当成公理。 大家顺着它，证明了几百个经典算法问题不可能更快。 图论、基因测序、动态规划，整座大厦的设计图纸，都默认这堵高墙坚不可摧。

现在，这面承重墙被撞出了一道裂纹。 OpenAI 拿出来的这套确定性算法，把运算时间的指数硬生生削去了一块。 它的时间复杂度，被压到了 2 的 n 除以以 2 为底对数项的平方根次方。 分母上多出来的这个对数，会随着变量规模变大而不断膨胀。 这就意味着，指数上的增长速度变慢了，它不再是严格的线性比例。 在理论计算机里，这就叫亚指数时间。 那把焊了二十多年的指数时间假说铁锁，在理论上被砸开了。

大家最关心的问题来了： 这等于证明了 P 等于 NP 吗？ 千禧年大奖那一百万美金，是不是被拿走了？ 并没有。 不仅没拿走，连边都没沾上。 多项式时间就像平地散步，问题变大，步数慢慢增加； 传统的指数时间就像垂直发射火箭，几步就冲进太空失控了。 这个亚指数算法，只是让火箭的仰角稍微往下压了一点点。 它比纯指数慢一点点，但依然远远快于多项式散步。 真正遇到大规模的实际工业算力需求，它依然算不动。 P 与 NP 的世纪大决战，依然停在原地。 但它的冲击力在于： 那座基于指数时间假说建立起来的研究大厦，突然发现自己的地基可能踩空了。 那些原本被判定为不可能更快的算法，理论上限可能都要重写。

更硬核的是验证过程。 写出一篇惊世骇俗的理论论文是一回事，数学界承不承认是另一回事。 以往这种震动学界的宣称，往往要经历几年的争吵，最后发现某个引理存在逻辑漏洞。 但这一次，OpenAI 掏出了一套用 Lean 编写的形式化代码。 Lean 是一种机器证明工具，它不相信任何人类的直觉，只对每一行逻辑做最冷酷的符号推导。 机器跑通了，意味着内部每一步推理在形式上没有跳步。 为了彻底消除疑虑，这篇论文甚至直接交给了当年提出假说的因帕利亚佐和帕图里本人，再加上麻省理工学院的理论顶尖学者瑞安·威廉姆斯，由学术界组织公开审议。 能不能经得起人类同行的显微镜检查，很快就会见分晓。

布贝克在推文里回忆，自己 25 年前在课堂上第一次看到 2 和 3 的差别时，那种震撼久久不散。 当时谁也不会想到，25 年后这堵坚不可摧的铁墙，会被 AI 钻出一个小孔。 这场关于算力极限的学术大考，才刚刚交卷。