OpenAI and Anthropic simultaneously claim their internal models overturned the Exponential Time Hypothesis (ETH)

OpenAI 一口气在理论计算机、纯数学和理论物理三大领域投下核弹：

这可能是今年最炸裂的科技新闻，甚至没有之一。

Claude更是直言，如果这些结果成立，这将是数学和理论计算机领域历史上最重要的一天。

其中，数学突破与菲尔茨奖得主王虹此前在挂谷猜想上的工作高度相关，而物理突破可能是三者中最重要的，或解决了诺奖得主杨振宁遗留的难题。

而这次要说的是计算机领域的突破：指数时间假设不成立。

按照 Claude 的说法，这是一个图灵奖级别的颠覆性成果，「如果声明正确无误，这将改变计算机科学」。

现OpenAI研究员、原微软人工智能副总裁兼杰出科学家Sebastien Bubeck称赞这位「20 年来见过的最大惊喜」。

OpenAI与Anthropic两大AI巨头，几乎在同一时间，宣布自家内部模型推翻了统治理论计算机科学长达27年的「指数时间假设」（ETH）！

更让人细思极恐的是：Anthropic甩出的论文里，明确标注核心算法由内部模型Claude在零人类干预的情况下独立推演发现。

这篇可能载入人类科学史册的论文，署名的唯一作者，只有Claude。

理论计算机界的「天」塌了，这到底意味着什么？

简单来说，1999年，指数时间假设（ETH）由加州大学圣地亚哥分校的Russell Impagliazzo和Ramamohan Paturi提出。

你可以把它想象成一把有n个开关的密码锁，也就是3SAT问题。

半个世纪以来，无数绝顶聪明的大脑想尽办法去开锁，但没人能打破一件事：破解这把锁的时间，永远随着开关数量的增加呈「指数级」暴涨。

举个例子，假设一把锁需要填入n个数字，每个数字都在1到9之间。每个位置都有9种选择，因此总共有9ⁿ种可能，也就是9连乘n次。

我们可以通过穷举所有9ⁿ种可能来解决这个谜题。但这种方法极其低效：对于一个需要填入n = 100个数字的数独谜题，即使用上世界上所有的计算机，也要等到太阳冷却之后才能完成。

长期以来，人们一直试图找到运行时间随 n 增长得比 9ⁿ 更慢的算法，却始终没有成功。

1999年，学者们把这种集体直觉写成了一个正式假设：3SAT不存在亚指数时间算法。

你可以改进一点点速度，但永远翻不过这堵「指数墙」。这就好比物理学里的「光速不可超越」一样。

这个猜想提出已经二十多年了，过去有数百篇论文以 ETH 成立为前提，去研究各种计算问题的复杂性下界。

从图论、组合优化，到数据库和计算生物学，很多研究都建立在这个假设之上。

黎曼猜想如果被推翻，倒的是数论；ETH 被推翻，倒的是复杂度和参数化算法。

ETH 的分量没到「P vs NP」或黎曼猜想这种千禧年级别。

但它比 P≠NP 更强、更具体：如果ETH成立，就能推出 P≠NP；但 ETH 被推翻，并不能推出 P=NP。

大量依赖ETH的条件性研究结论，都需要重新评估了。

群里还有个哥们儿，他之前写的一篇论文就是以 ETH 成立为前提的。

现在这个前提可能直接没了，论文的结论要重新审视。

你想象一下，你花了几年时间研究一个问题，写论文、做证明，甚至一个领域的学者围绕这个假设研究了二十多年（比如图里这个教授）。

跨越科学研究的卢比孔河：唯一作者 Claude

戏剧性的一幕紧接着就出现了。

OpenAI总裁Greg Brockman前脚刚发帖官宣，老对手Anthropic后脚直接甩出了一篇同题论文，正面硬刚，当场撞车！

Anthropic表示：巧了这不是，我们的Claude内部模型在10月16日就已经独立推翻了ETH！

而且，Anthropic在论文页面上留下了一段「来源声明」：

核心算法由一个内部Claude研究模型于10月16日找到，消耗1400万输出Token，没有任何人类输入。

1400万Token是个什么概念？一本《三体》全集大约90万字。1400万Token，相当于Claude一口气疯狂推演了十几套《三体》厚度的草稿。

在这几天里，Claude自己摸索路径，自己推演公式，自己验证逻辑，甚至跨界调用了八竿子打不着的冷门数学工具，最终把一份证明拍在了人类面前。

祖师爷连夜被叫醒，数学家化身「审计员」极速瘦身

最魔幻的一幕发生了。两家公司为了自证清白，都没有仅仅扔出一篇PDF，而是同时公开了Lean形式化证明代码。

Lean是一位「铁面无私的电子审稿人」，哪怕有一步逻辑跳跃，它都会直接报错。既然代码能跑通，说明逻辑底层几乎封死了出错的可能。交出「机器可验」的卷子，这是AI无可辩驳的底气。

但这还不能完全确认证明的正确性。

当年提出ETH猜想的两位奠基人——Russell Impagliazzo与Ramamohan Paturi，据传已被紧急请出山。

27年前，两位学者写下一个猜想；27年后，他们被叫醒，去检查一个AI是怎么把它推翻的。

这大概是学术史上最复杂的一种心情。

目前，这两位泰斗正联合MIT等高校的顶级团队，对两家的代码展开逐行审验。

与此同时，另一条战线也在飞速推进。

面对AI产出的这份长达60多页的「外星」证明，人类大脑读起来极其吃力。

英伟达高级AI架构师Shiva Kintali连夜爆肝，将OpenAI原版60多页的ETH证伪证明，硬生生压缩成22页的精简版！

他的目标只有一个：「让人类同行能真正看懂。」

现在，一个前所未有的学术奇观出现了：

AI负责攻坚：在几天里撞开一道27年没人撞开的门；

基础科研的「主客易位」

早在2023年3月，OpenAI曾发布过一份轰动一时的《AI对就业市场影响预测报告》。在这份榜单里，高居「被AI冲击最大职业」榜首的，赫然是数学家。

然而，整整三年后的今天，伴随着ETH被AI连夜证伪、Kakeya猜想接连被模型攻破……

这颗三年前射出的子弹，终于正中了人类理论科研的眉心。

这是否意味着科学家们要集体失业了？并不。

正如北大校友、学者Weijie Su在三年前所洞察的那样：AI不会简单粗暴地「取代」任何领域，而是会重塑它们。未来的科研，将极大奖励那些能与现实世界挑战、以及其他学科产生深度连接的人。

就像照相机发明后，画家不再需要比拼「谁画得更像」，于是诞生了印象派和现代艺术。

27年前，当那两位学者写下ETH猜想时，绝对想不到，终结它的不是人类。

本文来自微信公众号“新智元”（ID：AI_era），作者：大卫，36氪经授权发布。