OpenAI模型反驳指数时间假设：为什么它没攻破密码学，却震动了整个理论计算机界？

如果全世界计算机科学家深信了 25 年的一个底线，忽然被 AI 掀翻了，会发生什么？ 理论计算机科学界这几天正在经历一场地震。 OpenAI 的内部模型扔出了一篇论文，声称推翻了计算复杂度领域著名的「指数时间假设」。 这个名字听起来有些生僻，但过去 25 年里，整个算法理论界的大半座高楼都盖在它上面。 很多人都听过千禧年七大数学难题之首的 P 对 NP 问题。 说白了，就是计算机面对那些超大规模的复杂问题，到底存不存在聪明的快速算法？ 半个多世纪过去了，全世界最顶尖的大脑都没能彻底证明它。 大家甚至连证明「某些难题绝对无法快速求解」都做不到。 到了 1999 年，拉塞尔·因帕利亚佐（Russell Impagliazzo）和拉莫汉·帕图里（Ramamohan Paturi）两位学者换了个思路。 他们做了一个更大胆、也更符合直觉的判断。 他们指出：别争什么快速算法了，像 3-SAT 这种经典的布尔可满足性难题，难度远超想象。 它不仅无法在多项式时间内被快速解出，而且耗时必须随变量数量呈严格的指数级暴涨。 不管你多聪明，都绝不可能写出一个耗时在所谓「亚指数时间」内的解法。 这就是著名的指数时间假设。 虽然没人能在数学上彻底证明这个假设，但所有人都觉得这太符合常识了。 于是在过去的 25 年里，整个理论界形成了一种默契： 既然一时证不出 P 不等于 NP，那我们就先把指数时间假设当成坚固的地基来用。 在这块石头上，学者们盖出了一整座叫作「细粒度复杂度」的庞大学术大厦。 图论、生物基因测序、数据库查询、离散优化，成百上千篇经典论文都在结尾立下了同一个论断： 在指数时间假设成立的前提下，这个算法的耗时已经逼近了数学极限，不可能再快了。 大家安心地在这个地基上耕耘了整整一代人的时间。 结果在 2026 年 10 月中旬，OpenAI 的内部模型直接把这块石头抽掉了。 它给出了一个确定性算法，声称解 3-SAT 的时间复杂度降到了大约 2 的 n 次方除以根号对数 n 的级别。 不用去死记这串数学符号。 关键在于：它的耗时被硬生生推进了理论界认为绝对不可能存在的「亚指数区间」。 那个守了 25 年的严格指数红线，被击穿了。 很多人看到消息的第一反应是：天哪，那 P 是不是等于 NP 了？ 各大银行的密码加密是不是全完了？比特币和网络通信是不是一夜之间全被破解了？ 完全没有。 亚指数时间虽然击穿了原有的红线，但随着问题规模扩大，它的耗时依然会迅速膨胀到天文数字。 它离多项式级的轻快秒解还隔着十万八千里。 现有的密码学协议依旧安全，世界并没有在今天塌下来。 那理论界的学者们到底在恐慌什么？ 他们震惊的是，那座学术大厦底下立了二十几年的警示牌，一下子全被拔掉了。 过去 25 年里成百上千篇被判定为「绝不可能跑得更快」的问题，边界全部失效了。 原先以为彻底焊死的铁门，忽然发现底下居然留着缝隙。 无数原本被认定已经走到头的基础算法，现在必须全部推倒重算。 更耐人寻味的是这次交卷的方式。 OpenAI 并没有只扔出一份容易让人扯皮的英文草稿。 他们把整套证明翻译成了形式化定理证明语言 Lean，将推导步骤逐行写成代码，直接通过了机器程序的逻辑编译核验。 更绝的是，他们把成果直接交给了当年提出这个假设的两位原作者：拉塞尔·因帕利亚佐与拉莫汉·帕图里，以及麻省理工学院的算法大师瑞安·威廉姆斯（Ryan Williams）。 27 年前亲手立下这根标杆的前辈，如今被邀请来审查一个推翻自己毕生假说的 AI 模型。 三位顶级学者迅速牵头组建了独立的学术审查小组，并公开发布了一封联名信。 他们在信中写道：组织审查绝不代表为结论背书。 哪怕代码在机器语言里显示通过，也可能存在定义偏离或者环境漏洞。 机器能确认代码推导不矛盾，但最底层的数学前提是否符合逻辑现实，依然需要人类学者一行一行去抠。 著名理论计算机科学家斯科特·阿伦森（Scott Aaronson）在博客中记录，当天学生直接冲进他的办公室大喊这个假设被攻破了。 菲尔兹奖得主陶哲轩此前也提醒过：理论科学正在跨入一个前所未有的阶段。 以往顶尖学者是举着火把在未知荒原上拓荒的探险家。 而现在面对 AI 喷涌而出的机器证明，顶尖学者们忽然变成了一群手忙脚乱的质检员与校对员。 这场由原作者领衔的同行评议预计还要持续几个月。 无论是最终查出了算法里某个隐蔽的前提缺陷，还是真的推翻了这个 25 年的历史猜想，时代都已经变了。 AI 不再只是在外面打打下手、写写业务脚本。 它已经坐在人类几十年前立下的数学棋局前，神情自若地推下了第一颗棋子。