行业资讯

科学家相信了30年的假说，发过数百篇论文，可能被OpenAI证伪了

时间：2026-11-01 17:54 所属分类：行业资讯 点击次数：

高中时，拉塞尔·因帕利亚佐（Russell Impagliazzo）上过一门编程课。若想让程序运行，他需要先把代码转到纸带上，再送进一台老旧的计算机。偏偏机器很

高中时期，拉塞尔·因帕利亚佐（Russell Impagliazzo）曾修过一门编程课。想要运行程序，他得先把代码转录到纸带上，再送入一台老旧计算机。这台机器故障频发，甚至常会把纸带扯断。多年后，他在接受《量子杂志》（Quanta Magazine）采访时回忆，那时的他只觉得计算机科学“无聊透顶”，一心打算转向逻辑学研究。

可他深入钻研逻辑之后，反倒对计算本身生出了浓厚兴趣：该怎样判定一条数学命题的真假？一道难题的难点究竟在何处？各类问题最快能以多高的效率完成计算？计算是否存在一道无法逾越的边界？1998年，因帕利亚佐与两位合作者共同提出指数时间假说（Exponential Time Hypothesis，ETH）。该假说认为，对于一部分计算难题，无论算法设计得多么精巧，都无法摆脱随问题规模呈指数增长的运算耗时。

在此之后近三十年里，理论计算机学界以ETH为基础前提，不断推导各类问题的计算时间下界，衡量现有算法的优化上限，围绕这一假说产出了数百篇学术论文。

而当地时间10月26日，OpenAI发布一篇论文，宣称其人工智能系统找到了全新算法，可以在亚指数时间内求解ETH所针对的计算问题，对这一假说构成证伪。OpenAI同步公开了配套证明，邀请学界开展独立核验，受邀牵头审查的研究者中，就包括ETH的提出者因帕利亚佐与拉马莫汉·帕图里（Ramamohan Paturi）。截至目前，这项结论还没有通过完整的同行独立评审。

计算究竟能有多快？

上世纪90年代，寻找更高效的算法是计算机科学家的核心工作之一。面对一批公认的困难问题，研究者早已不必暴力枚举全部可能性：通过巧妙剪枝、排除无效候选，往往能大幅缩减运算量。可更快的算法接连问世的同时，一个疑问始终悬而未决：算法的提速空间到底还有多大？换言之，计算速度是否存在天然极限？

1998年，因帕利亚佐、帕图里与弗朗西斯·赞恩（Francis Zane）在IEEE计算机科学基础研讨会（FOCS）上发表论文，试图划定这条边界，相关成果后续正式刊发于《计算机与系统科学杂志》（Journal of Computer and System Sciences）。他们研究的问题，可以类比成一场聚会的席位安排：

假设要筹办一场聚会，每个人只有参加或不参加两种状态，同时附带一系列约束条件：小李、小王至少一人到场；如果小王来，小张就必须到场；小李和小张不能同时出席。人数只有三人时，稍加思考就能找到符合全部条件的方案。可如果规模扩大到几百人，每个人都被多条类似规则约束，问题难度会急剧上升。

最朴素的解法，是逐一枚举所有组合方案。10个人对应1024种可能性，30个人就超过十亿种，60个人的组合数量更是突破百亿亿。只要人数小幅增加，候选方案总量就会爆炸性增长。精巧的算法不需要遍历全部组合，但我们始终无法确定，算法最多能砍掉多少运算步骤。

在计算机科学里，这类寻找满足整套逻辑约束赋值方案的问题，被称为布尔可满足性问题（Boolean Satisfiability Problem，SAT）。其中3-SAT限定每一条约束条件最多只涉及三个布尔变量。ETH猜想的核心是：对于3-SAT问题，总能构造出足够棘手的实例，不存在通用算法能在最坏情况下跑出优于指数级的时间复杂度。

ETH刻画的是最坏情形，它并不代表现实里所有同类场景都难以计算，也不是说算法只能暴力穷举；它的核心是否定了存在普适的亚指数时间算法。芯片验证、软件测试、复杂排班等实际场景，都存在相似的逻辑约束。即便这些工程应用未必直接引用ETH，它们也让“计算的难度边界”不再只是纯粹的理论猜想。

有意思的是，假说的提出者从没有笃定ETH一定成立。2012年，因帕利亚佐在普林斯顿高等研究院的报告中提到，当时学界对ETH以及它的更强版本的真伪，本就没有共识。而他并不为此焦虑——无论假说成立或是被推翻，结果都能帮人类更好地理解各类问题的计算复杂度。

这些困难问题之间，还藏着奇妙的归约关系。举个例子：给地图着色，要求相邻区域颜色不同，判断只用三种颜色是否可行，这件事和聚会安排看似毫无关联，但研究者可以把一类3-SAT问题转化为这个图着色问题。倘若三色着色存在极速算法，那么对应的3-SAT问题也能跟着提速；反过来，如果ETH成立，就相当于给地图着色这类问题锁死了计算速度的上限。

这套思路，让本身悬而未决的ETH发挥了巨大价值。研究者不需要逐个证明每一类问题的复杂度，而是以ETH作为基石，推导出一条条条件性结论，也能用来评估自研算法还有多少优化余地。据估算，从图论、数据库到计算生物学，数百篇论文都建立在ETH成立的前提之上。这也是为什么OpenAI的这项声明，会在理论计算机圈内掀起巨大波澜。

AI找到了一条计算捷径？

就在不久前，OpenAI刚公开一批由AI生成的数学研究文稿，声称解决了上百个未解难题，学界还在研读核验这批材料。10月26日，OpenAI再度发布《与学术共同体合作，推动科学理解》（Working with Academic Communities to Build Scientific Understanding），一口气公布数学、理论计算机与物理方向三项新成果，其中一项，目标直指ETH。

在题为《指数时间假说是错误的》（The Exponential Time Hypothesis is False）的论文中，OpenAI表示，其模型构造出新算法，能够在亚指数时间里，精确统计某一类布尔逻辑公式可行解的总数。

继续沿用聚会安排的例子：ETH认为，不存在一套通用算法，可以在亚指数时间内处理所有这类复杂约束问题的最坏实例。而OpenAI声称，这套新算法不止能回答“是否存在可行的聚会安排”，还能统计一共有多少种合规方案。如果该算法对全部3-SAT实例都成立，那么只要判断可行解数量是否大于零，就能在亚指数时间判定问题有无解，直接和ETH形成矛盾。

按照OpenAI的说明，AI在10月16日生成了自然语言版本的证明，次日完成基于Lean的形式化验证。Lean是一款数学证明校验工具：研究者把定义、前提和推理步骤改写为机器可识别的严谨形式语言，由它逐行排查逻辑漏洞。OpenAI的材料显示，Lean所验证的时间上界，弱于论文里最强的主结论，但依旧属于亚指数级别，足以挑战ETH。

不过Lean只能校验输入给它的形式命题是否被完整证明，无法自动判断这套形式化内容是否忠实对应原始问题，定义、前置假设是否存在偏差，这部分依旧需要学者人工研判。OpenAI文档里也写明，Lean核验得到的复杂度界限和论文主结果并不完全一致，只是二者都足以冲击ETH。因此到目前为止，远远谈不上ETH已经被学术界公认推翻。

即便未来ETH最终被证伪，也不代表过去依托它完成的数百篇论文会全部失效。很多论文证明的是条件命题：如果ETH为真，那么不存在某种快速算法。就算前提不再成立，条件推导本身的逻辑链条依旧可以是正确的，只是我们不能再借此断定这类快速算法一定不存在。届时科学家需要重新寻找计算难度的边界，一些曾经被认定走不通的算法方向，也会迎来重新探索的机会。

谁来核验AI产出的科学结论？

为评估这项成果带来的影响，OpenAI邀请因帕利亚佐、帕图里，以及长期深耕算法加速与复杂度证明的麻省理工学者瑞安·威廉姆斯（Ryan Williams）牵头组织审查。前两位正是ETH的提出者，威廉姆斯则是该领域的资深研究者。如今，他们需要带领同行，审视这个有可能重塑整个领域的结论。

10月26日，威廉姆斯在社交平台Bluesky发文，谨慎地将这份成果描述为OpenAI“所声称的证伪”。他特别说明，三人没有签署保密协议、不收取酬劳，可以自由对外同步审查进展；他们还要求OpenAI公开论文、Lean代码等全部原始材料，并资助学界举办专题讨论会，相关诉求已经得到OpenAI应允。

之后三人联合发布《致理论计算机科学界关于ETH的信》，再次划清边界：牵头组织核查，不等于背书这项结论。如此重大的学术主张，必须经过学界独立、审慎的检验。他们号召更多研究者加入，一同审读数学证明，同时探讨AI产出科研成果之后，证明核验流程、论文署名、学术贡献该如何界定。在传统学术范式里，读者可以直接联系作者，追问证明里的难点、漏洞；但生成这份证明的AI模型，没办法像人类学者一样答疑阐释，核验的责任该由谁承担，成了新问题。

这份疑问早已超出ETH个案。10月25日，由蒂莫西·高尔斯（Timothy Gowers）、马丁·海雷尔（Martin Hairer）等数学家组成的数学与人工智能咨询小组（AGMAI）发布文章《指定数学家参与AI成果发布的弊端》，公开反对AI企业挑选少数学者优先解读成果。他们担忧，商业公司安排小范围优先审阅，容易造成信息不对称，还可能借知名学者的声望，为尚未充分核验的结论间接背书。

争论很快延伸到OpenAI同期公布的另一项未完全公开的证明。除ETH之外，OpenAI同日宣称AI证明了数学中的局部平滑猜想，还在四维量子场论的严格构造上取得突破。前两项研究材料已经对外公开，物理方向成果先交由诺贝尔物理学奖得主戴维·格罗斯（David Gross）带队审阅。10月26日，AGMAI随即呼吁OpenAI公开这份物理方向的材料，向全体研究者开放核验通道。

随着AI持续产出数学证明，科学家们的工作分成两层：既要判断证明本身是否成立，也要搭建机制，让更多研究者能够读懂、参与检验。而因帕利亚佐或许对这种状态并不陌生。2024年接受《量子杂志》采访时，他聊起自己坚持多年的即兴喜剧。一开始，他总忍不住纠正搭档台词里的疏漏，后来慢慢学会接纳那些并不完美的想法：“很多好想法，本就不是百分之百正确的。”ETH会不会也是这样一个想法？此刻，他和同行的审查工作仍在继续。