OpenAI或证伪科学家30年假说

撰文 | 不周 

审校 | 王昱

高中时，拉塞尔·因帕利亚佐（Russell Impagliazzo）上过一门编程课。若想让程序运行，他需要先把代码转到纸带上，再送进一台老旧的计算机。偏偏机器很容易出故障，有时连纸带都能扯成两半。多年后，他在接受《量子杂志》（Quanta Magazine）采访时回忆，自己当时觉得计算机科学“无聊透顶”，于是打算去研究逻辑学。

没想到，越是研究逻辑，他越对计算产生了兴趣：怎样判断一个数学命题是真是假？一道难题究竟难在哪里？有些难题究竟能算得多快？是否存在无论如何都无法跨越的计算极限？1998年，因帕利亚佐和两位同事共同提出了指数时间假说（Exponential Time Hypothesis，ETH），认为在计算某些难题时，无论采用多么巧妙的算法，都无法摆脱指数级增长的计算时间。

在这之后近30年里，计算机科学家不断以ETH假说为前提，推导其他问题的计算时间下界，判断现有算法究竟还有多少改进空间，开展了数百篇论文的研究。

然而，当地时间10月26日，OpenAI发布了一篇论文，声称其人工智能（AI）系统找到了一种新算法，能够在亚指数时间内解决ETH所涉及的计算问题，从而证伪这一假说。OpenAI同时公布了相关证明，并邀请科学家组织独立核查。其中两位正是当年提出ETH的因帕利亚佐和拉马莫汉·帕图里（Ramamohan Paturi）。目前，这项结果尚未通过独立审查。

计算究竟能有多快？

20世纪90年代，寻找更快的算法是计算机科学家的一项日常工作。对于一些公认困难的问题，他们已经不必再逐一试遍所有可能：巧妙地排除某些无效选择，常常能省下大量时间。但改进后的新算法一个接一个地出现，也让人忍不住追问：算法究竟还有多少加速空间？换句话说，计算速度是否存在极限？

1998年，因帕利亚佐与帕图里、弗朗西斯·赞恩（Francis Zane）在计算机科学基础研讨会（IEEE FOCS）上发表论文，试图寻找这道边界。这项研究后来发表于《计算机与系统科学杂志》（Journal of Computer and System Sciences）上，他们研究的是一道看起来有点像排座位游戏的问题。

假设你要安排一场聚会，每个人只有来或不来两种选择。但这些人要求颇多：小李、小王和小李至少得来一人；小王来了，小张也必须来；小李和小张不能同时出席。如果只涉及三个人，稍加琢磨便能找到满足所有条件的合适安排。但如果有几百个人，每个人都受许多类似的条件约束呢？

图片来源：Unsplash

一种笨办法是把所有安排挨个试一遍。10个人有1024种组合，30个人就超过10亿种，60个人更是超过100亿亿种。人数每增加一些，可能性便会飞快膨胀。聪明的算法不必逐一检查所有组合，但困难的是，我们不知道它们究竟能省下多少步骤。

在计算机科学中，这类寻找满足一组逻辑条件的方案的问题，称为布尔可满足性问题（Boolean Satisfiability Problem，SAT）。其中的3-SAT要求每个条件最多涉及三个真假变量。而ETH猜测：面对3-SAT，总有足够刁钻的题目，使得任何通用算法都不能比指数级的计算时间更快。

ETH描述的是最难的情况，并不是指所有现实中的安排都会慢得无法计算，也不要求算法一定要穷举全部组合，而是排除了增长速度低于指数级的“亚指数时间”算法。在现实中，芯片验证、软件测试和复杂排班都会碰到类似的逻辑约束；虽然这些应用未必直接用到ETH，它们却让“计算究竟有多难”不再只是纸上的问题。

有趣的是，提出假说的几位科学家并没有断言它必然正确。2012年，因帕利亚佐在美国普林斯顿高等研究院的一场报告中表示，当时学界对ETH及其更强版本究竟是真是假，并没有达成共识。他并不担忧，因为无论是哪一种答案，都能帮助人们理解其他问题的计算难度。

美国计算机科学家拉塞尔·因帕利亚佐（Russell Impagliazzo）。图片来源：BöhmMartin/Wikipedia

事实上，这些难题之间存在一些奇妙的联系。比如，给一张地图涂色，要求相邻地区不能同色，如何才能判断三种颜色是否够用？它与安排聚会毫无关联，但研究人员可以把一类3-SAT问题转化成这样的图论问题。假如后者存在一种特别快速的算法，3-SAT也能有类似的加速。反过来，如果ETH成立，就可以为地图着色等问题划出一道计算速度的极限。

这种方法让尚无定论的ETH假说发挥了出人意料的作用。研究人员不必逐一证明每类问题究竟有多难，而是能以ETH为出发点，推导出一个又一个条件性结论，也可以判断自己设计的算法还有多少改进空间。据估计，从图论到数据库、计算生物学，已有数百篇论文以ETH为前提建立计算难度方面的结论。这也是为什么OpenAI发布了一则声明，会引发业内如此多的关注。

AI发现一条捷径？

就在几周前，OpenAI刚公开了一批由AI生成的数学研究文稿，声称解决了数百个未解问题。学界还在阅读、核实这些材料，10月26日，OpenAI又发布了《与学术共同体合作，推动科学理解》（Working with Academic Communities to Build Scientific Understanding），宣布数学、计算机科学和物理学三项新成果。其中一份成果便直指ETH。

根据OpenAI公开的论文《指数时间假说是错误的》（The Exponential Time Hypothesis is False），其内部模型设计了一种新算法，能够在亚指数时间内精确统计某类布尔逻辑公式有多少组满足条件的答案。

图片来源：OpenAI

依然以聚会安排为例。ETH认为，不可能找到一套适用于所有复杂安排问题的算法，使最坏情况下的计算时间降到亚指数级。但OpenAI声称，新算法不仅能回答“有没有办法让聚会顺利举办”，还能算出“究竟有多少种安排能行”。如果它真能适用于任意3-SAT问题，只需看答案数量是否大于零，就能在亚指数时间内判断问题有无解，与ETH直接冲突。

OpenAI称，AI在10月16日生成了自然语言证明，次日又完成了Lean形式化验证。Lean是一种检查数学证明的软件——人们先把概念、条件和推理步骤写成传统计算机能理解的精确语言，再让它逐步检查有没有逻辑错误。OpenAI公开的说明显示，Lean所验证的计算时间界限比论文中的主要结果稍弱，但依然属于亚指数时间。

但Lean只能检查写给它的命题是否得到证明，但却不能保证其形式化证明是否准确对应原来的问题，所用定义和假设是否恰当，这仍需要人类来审视。在OpenAI公开的说明中，Lean验证的时间上界与论文最强的结果并不完全相同，尽管二者都足以挑战ETH假说。因此，如今还远称不上ETH已被学界公认推翻。

不过，如果ETH最终被证伪，也并不意味着过去建立在它之上的数百篇论文会作废。实际上，许多论文证明的都是“如果ETH为真，某种快速算法便不存在”。即使前提后来被否定，这段条件推理的逻辑依然可能完全正确，只是不能再凭它断言某种算法真的不存在。而科学家也需要重新寻找计算难度的边界，与此同时，某些曾经被认为走不通的路，或许也值得再次尝试。

谁来验证AI的发现？

为了厘清这些可能的影响，OpenAI邀请了因帕利亚佐、帕图里和美国麻省理工学院的瑞安·威廉姆斯（Ryan Williams）组织审查。前两人参与提出了ETH，威廉姆斯则长期研究怎样加快算法、证明算法的极限。现在，他们要组织同行审视这个可能改变自己研究领域的结果。

10月26日，威廉姆斯在社交平台“蓝天”（Bluesky）上发文，谨慎地将这项成果称为OpenAI“声称的证伪”。他特意说明，三人没有签署保密协议，也不收取报酬，可以自由向同行分享审查进展。他们还要求OpenAI公开论文、Lean代码等原始材料，并出资支持学界举行讨论会议，OpenAI已同意他们的要求。

随后，三人在《致理论计算机科学界关于ETH的信》（Message to the TCS Community on ETH）中再次划清界限：组织核查并不等于为结论背书。如此重要的主张，仍须由学界独立、仔细地检验。他们邀请更多研究者参与，一同审查数学证明，同时也讨论AI提出成果后，验证工作、研究署名和学术贡献该怎样认定。此前，一篇论文问世，研究者都知道该去找作者讨论证明中可能存在的问题和难点。但如今，生成证明的模型并不能像人类研究者那样承担解释与答疑，此时核查的责任应该落到谁身上？

这样的疑问早已不局限于ETH。10月25日，由蒂莫西·高尔斯（Timothy Gowers）、马丁·海雷尔（Martin Hairer）等数学家组成的数学与人工智能咨询小组（Advisory Group on Mathematics and Artificial Intelligence，AGMAI）发表《指定数学家参与AI成果发布的弊端》（Disadvantages of Designating Mathematicians for AI Output Releases），公开反对由AI公司挑选少数学者优先解读新成果。他们担心，商业公司让少数人优先接触成果，不仅容易造成信息不平等，也可能无意间借科学家的声誉为尚未经充分审查的发现背书。

争论很快落到了另一项尚未公开的证明上。除了ETH，OpenAI同日还声称，AI证明了数学中的局部平滑猜想，并在四维量子场论的严格构造上取得突破。前两项研究材料已公开，物理学成果则先交由诺贝尔奖得主戴维·格罗斯（David Gross）领衔的团队审阅。10月26日，AGMAI随即要求OpenAI公开相关材料，让其他研究者也能参与检验。

随着AI接连交出新的数学证明，科学家不仅要判断它们是否正确，还得考虑如何让更多人参与理解和检验。因帕利亚佐或许很熟悉这样的处境。2024年，因帕利亚佐在接受《量子杂志》（Quanta Magazine）采访时，聊起自己坚持了近30年的即兴喜剧。起初，他总忍不住纠正搭档的表达，后来却学会了接纳那些不够完美的想法。“很多好想法，并不是百分之百正确的，”他说。ETH会不会也是这样一个想法？眼下，他和同行还在仔细审查AI给出的证明。

参考链接：

https://openai.com/index/building-scientific-understanding-with-academic-communities/

https://github.com/openai/math/blob/main/lean/docs/378.md

https://github.com/openai/math/blob/main/preprints/The-Exponential-Time-Hypothesis-is-False-October-25-2026/paper.pdf

https://en.wikipedia.org/wiki/Exponential_time_hypothesis

https://agmai.org/

https://www.quantamagazine.org/the-researcher-who-explores-computation-by-conjuring-new-worlds-20240327/

https://cseweb.ucsd.edu/~paturi/myPapers/pubs/ImpagliazzoPaturi_2013_ipec.pdf

https://www.sciencedirect.com/science/article/pii/S002200000191774X?utm_source=chatgpt.com

https://cseweb.ucsd.edu/~paturi/myPapers/pubs/ImpagliazzoPaturi_2013_ipec.pdf

https://bsky.app/profile/rrwilliams.bsky.social

https://ethdiscussion.blog/