困扰计算机科学界近30年的一条「铁律」，被AI在一天之内推翻了。OpenAI一口气公布三项内部AI独立完成的研究结果，其中计算机科学这一项，直接指向统治学界近30年的「指数时间假设」（ETH）。

打开网易新闻 查看精彩图片

先说清楚ETH是什么。所有程序员都绕不开可满足性问题（SAT）：给一堆逻辑条件，问有没有一组取值能让它们同时成立。它是NP完全问题的祖师爷，和「P与NP」这个千禧年难题血脉相连。

上世纪90年代末，Russell Impagliazzo和Ramamohan Paturi提出「指数时间假设」：3-SAT这类问题，不可能在「亚指数时间」内被解决，最快也得是2的cn次方量级。这个假设没人证明过，但几乎所有人都相信它。

于是过去近30年里，研究者不断把别的问题和它联系起来。图论、数据库、计算几何、计算生物学中，数百篇论文借助ETH划定算法能有多快的边界。AI这次给出的结论是：这一切错了。

OpenAI公开的计算机论文，标题只有一个毫不含糊的结论——《指数时间假设是错的》。这份67页手稿提出的算法，甚至要精确数出一个3-SAT公式有多少组满足条件的赋值。只要这个数量大于零，公式有没有解，也就一起回答了。

可以把3-SAT理解成一大堆互相牵制的开关规则：每条规则涉及三个取值为真或假的变量，任务是找到一种赋值，让所有规则同时成立。难处在于，变量一多，可能的组合就会爆炸。ETH认为，在最坏情况下，求解时间绕不开随变量数增长的指数级代价。

论文主张把增长速度降到次指数级，距离多项式时间仍有差距，所以反驳ETH不等于证明P=NP，也不能直接翻译成所有难题明天就能秒算。OpenAI同样明确，要把理论变成实际提速，还需要大量后续研究。

验证环节的分量同样不轻。提出ETH的祖师爷本人被请出山——Impagliazzo和Paturi，以及MIT著名复杂度理论学者Ryan Williams亲自挂帅。今早，Williams已公开给出论文链接和其中的时间复杂度主张。他们花了近30年研究的一条计算极限，如今迎来AI递来的反证。

速度是另一个让人倒吸一口凉气的点。OpenAI内部AI仅用一天完成证明：10月16日得到自然语言反驳，17日完成Lean形式化。这里的一天，是两种证明形态之间的转换间隔；决定结果能否站住的公开审查，现在正由这群专家接手。

现OpenAI理论计算机与数学家Sebastien Bubeck惊叹，亚指数时间内的3SAT，是自己关注理论计算机科学20年来见过的最大惊喜。他至今还记得25年前看到3和2在复杂度上能带来多大天壤之别时的那种震撼。网友Peter Gostev则调侃：行吧，那现在P与NP问题的胜率赔率是多少。

另外两项发现落在纯数学与理论物理。数学方向，OpenAI的模型把「局部平滑猜想」推到了所有维度。这个猜想由Sogge在1991年提出，它想象不同方向的波在一个时刻聚到一起，局部强度突然冲得很高；猜想要抓住的规律是，这种最极端的聚焦持续不了太久。OpenAI称，模型用一种新的辅助偏微分方程，给出了所有空间维度n≥2的证明。它是一座「母猜想」，一旦成立，挂谷猜想和Stein限制猜想会像多米诺骨牌一样全部倒下。从10月18日拿到自然语言证明，到第二天完成Lean形式化验证，AI只用了一天。

理论物理工作组由诺奖得主David Gross领衔。1973年，他参与发现了渐近自由，这一发现帮助确立量子色动力学，也让他与另外两位科学家分享了2004年诺贝尔物理学奖。OpenAI称，这次模型沿着构造性量子场论中Balaban的方法，给出了某些四维规范场与费米子理论的存在性证明，范围包括QCD，以及一种包含标准模型规范场和费米子的大统一补全。其中，纯杨–米尔斯理论的存在性，正好触及千禧年大奖难题的一部分。Clay要求的完整答案还包括正质量间隙，本次公告没有宣布解决这一部分。模型9月9日给出杨–米尔斯存在性证明，9月18日给出QCD证明。

与Gross一起入组的，还有Michael Douglas、Arthur Jaffe、Igor Klebanov和Nikita Nekrasov。Jaffe当年与Edward Witten共同写下了这道千禧年问题的正式题述。有人奠定过相关物理理论，有人亲手定义了悬赏问题，现在他们共同面对机器提出的新论证。

OpenAI把这三份手稿定位为「原始科研数据」，并首次试验三种外部学界协作模式：数学结果公开AI手稿与Lean代码；计算机科学结果公开手稿与Lean代码并组建专家组；物理天团决定暂不公开AI原始产物，由五位大师先闭门研读并亲自撰写阐述论文。

协作原则写得清楚：不要求签署任何保密协议；OpenAI不为内部模型产出的原始发现寻求学术署名；工作组因发展出的科学理解、撰写的阐释论文以及准确追溯前人思想而获得学术认可；学者自愿且无偿参与，完全独立得出结论。OpenAI向Simons Foundation出资500万美元，Simons基金会联合OpenAI、Anthropic共投入1500万美元资金与算力资源，资助研讨会、会议与专项计划。

目前openai/math仓库已收录由OpenAI未公开内部模型产出的721篇手稿，归为373个结果族。模型在约4000个开放研究问题上进行评测，平均每个结果消耗约3小时ChatGPT Pro级别的深度思考算力，目前约42%的顶层结论已完成Lean形式化。

OpenAI研究员苏炜杰在X上晒出自己3年前的演讲PPT。第4页写着，完全信息工作最易受AI冲击，除了程序员、会计，还特别点名「也许还有理论计算机科学家、理论物理学家和（纯）数学家」。他感慨，当时在现场听他演讲的人里，几乎没人相信他的话。

回过头看，「取代」这个词用得并不完全准确。AI不会取代任何学科，它将会从根本上重塑、而且已经在重塑各个学科。OpenAI总裁Greg Brockman在官宣里写道，AI已经开始帮助我们加深对宇宙的理解。一旦成果通过验证，人类科研将进入「AI率先发现、人类验证理解」的新阶段。