OpenAI于2026年10月26日宣布,其一款AI模型给出了一份证明,表明指数时间假设(Exponential Time Hypothesis,简称ETH)不成立。这一猜想在约三十年里一直被计算机科学家视为基础性假定。该证明已在交互式定理证明器Lean中完成检验,由机器逐步核对每一个逻辑步骤;OpenAI还将论文交给当初提出这一假设的复杂性理论学者审阅并把关。这一结果并不意味着P等于NP,OpenAI总裁格雷格·布罗克曼当天也明确表示了这一点。它真正表明的是:一类长期被认为只能靠暴力搜索求解的问题,其实存在亚指数时间的捷径,而这动摇了大量理论工作赖以立足的根基。
指数时间假设说了什么
ETH涉及布尔可满足性问题,通常简称SAT:给定一个由若干变量构成的逻辑公式,每个变量可取真或假,是否存在一种赋值使整个公式为真?这一假设由Russell Impagliazzo、Ramamohan Paturi和Francis Zane在大约三十年前提出,断言求解该问题的k-CNF版本所需的时间会随变量数量严格呈指数增长。通俗地说,它认为除了逐一尝试各种组合直到找到答案之外,不存在实质上更好的策略。
这一假定后来成了理论研究的主力工具。图论、计算生物学、数据库理论和计算几何领域的数百篇论文都以ETH为前提推导条件性困难结果,即"若ETH成立,则另一个问题同样无法快速求解"这类命题。前提被推翻并不意味着这些下游结论各自都错了,但它们确实不再立于作者原先假定的基础之上。可以这样打比方:一整片理论建筑群建在同一块地皮上,而这块地皮最终被发现并不像所有人以为的那样存在。
新论文证明了什么
OpenAI这篇论文题为《指数时间假设不成立》(The Exponential Time Hypothesis is False),初稿日期为2026年10月17日,修订日期为2026年10月25日。据随附的公告,模型在10月16日找到了这一反证,Lean形式化工作于10月17日完成。核心定理给出了一个确定性算法,能在2的o(n)次方时间内求解k-CNF可满足性问题,这是亚指数增长的正式记法。论文将机器检验的Lean证明与自然语言解释并列呈现。
有两层表述需要分开看待:
| 命题 | 公告之后的状态 |
|---|---|
| ETH成立 | 已被推翻,依据OpenAI经Lean验证的证明 |
| SAT可在亚指数时间内求解 | 已由论文中的算法确立 |
| P等于NP | 未被证明;布罗克曼称很可能仍不成立 |
| 现代加密已被攻破 | 未被证明;取决于仍悬而未决的P与NP问题 |
Anthropic似乎也几乎在同一时间得出了非常相似的结果。若得到确认,这将是两个独立AI系统之间一次值得注意的殊途同归。

▲ 指数级搜索与快速验证的对比
为何"亚指数"不等于"快"
P、NP与指数时间之间的区别,可以借几件日常物品来理解。
一把只有一个十位数字拨盘的密码挂锁,暴力破解最多试10次就能打开。两个拨盘把次数提高到100次,三个拨盘是1000次,十个拨盘则是100亿次。每增加一个拨盘,搜索空间就成倍扩大,这就是指数增长:规模的小幅增加会带来工作量的爆炸式增长。
数独展示了另一半图景。徒手填满一个空白的9乘9网格很慢,但检查一个已完成的网格只需几秒,因为你只需确认每行、每列和每个3乘3宫格都包含1到9这九个数字。候选答案可以被快速检验的问题属于NP类,即非确定性多项式时间。
P类即多项式时间,涵盖那些规模增长时难度以可预测、可控方式上升的问题。整理一篮衣物可能要十分钟,整理五篮所需时间按比例增加,而不是几十亿年。
P与NP问题问的是:每一个容易检验的问题是否也都容易求解?五十多年来,研究者一直试图要么为某个NP完全问题找到多项式时间算法,要么证明这样的算法不存在。两者都没有发生,共识逐渐倾向于假定P不等于NP。
ETH是比"P不等于NP"更尖锐的论断。它不仅说SAT没有多项式时间算法,还说它需要完全的指数时间。新算法打破的正是这一更强的论断。它不再盲目转动每一个拨盘,而更像一个听弹子声响的开锁匠:确定某个拨盘停在9,就能从逻辑上排除其他位置的数千种组合,于是整片搜索分支根本无需访问。就目前已证明的结论而言,其运行时间仍比任何多项式增长得更快,但慢于纯粹的指数。
用山来打比方,可以把这个层级关系说得更具体。从A点翻过山顶到B点,就是穷举搜索,即P不等于NP的世界。一条平地水平的隧道则对应P等于NP。推翻ETH并没有打通山脚的隧道,却揭示出在半山腰不同高度上穿山而过的通道,这些通道是数十年的人类努力都未曾找到的。
为何这一结果关乎密码学,又为何没有攻破它
现代密码学几乎全部依赖一个假定:恢复密钥是一个难以处理的NP搜索问题。斯科特·阿伦森在综述论文《P =? NP》中就指出了这一点。密码和加密密钥的设计目标是猜测需要上千年,验证只需几毫秒。这种不对称正是全部意义所在,并可追溯到该领域最早的思考:约翰·纳什1955年致美国国家安全局的一封信中论证,破解密码需要搜索一个随密钥长度呈指数增长的空间;库尔特·哥德尔1956年致约翰·冯·诺依曼的一封信则勾勒了同一问题的元数学内核。
如果有朝一日P被证明等于NP且有实用算法,互联网安全、电子银行和加密货币体系将被根本性地破坏,数字基础设施需要彻底重建。同样的捷径也会让巨大的优化问题变得可解:排班调度、供应链路径规划、半导体芯片布局、蛋白质结构建模和药物设计都将大幅提速。OpenAI的一位研究人员还指出,物理学、数学和计算机科学的基础性突破本身也会成为推动AI进步的顺风。

▲ P与NP问题牵动的密码学与优化
仅凭ETH被推翻,上述一切都不会随之发生。布罗克曼那条"P很可能仍不等于NP"的帖子获得了超过35万次浏览,其他评论者也强调,这一结果指向的是亚指数算法,而非多项式时间的全面坍塌。还有第二层保留:即便是多项式时间算法,如果常数因子大得离谱,在实践中也可能毫无用处。一个只有当问题规模超过几千年人工尝试量时才胜过暴力搜索的算法,对任何人都没什么帮助。X平台上一位评论者把这个想法推得更远,认为如果P等于NP但其常数是我们这个世界的居民无法企及的,最合理的结论就是现实是一个被刻意设定了速度上限的工程化模拟。这是一个思想实验,而非研究发现,但它恰好说明了为何理论效率与实际效率之间的差距在此处如此重要。
OpenAI如何处理发布
OpenAI不署任何正式作者名义。相反,它安排加州大学圣迭戈分校的Impagliazzo和Paturi,以及麻省理工学院的Ryan Williams(他此前曾证明过ETH若干更强版本的反驳)来审阅并把关这篇论文。这一做法看来是为了让结果接受最有能力发现漏洞的人的审视,并避免此前一些AI成果公告曾引发的那种反弹。
ETH论文是同一公告中的三项成果之一。OpenAI还发布了纯杨-米尔斯理论的严格存在性证明,该证明建立在Tadeusz Bałaban的构造性量子场论方法之上,并于2026年10月16日在Lean中完成形式化。这解决了克雷数学研究所"杨-米尔斯与质量间隙"问题的一个主要组成部分,但并非官方表述的千禧年大奖难题的完整解答。第三项成果涉及调和分析中的局部光滑性与挂谷猜想,这是Christopher Sogge在1991年提出的问题。大约三十天前,OpenAI曾发布纳维-斯托克斯方程存在性与光滑性的解析证明及Lean形式化,目前仍在接受学术同行评审。综合来看,AI系统在大约90天内为多个重大猜想给出了证明。
斯科特·阿伦森在公告发布前约18小时的一档播客中谈到,曾经认定AI不会触及自己领域的理论物理学家,如今正紧张地注视着它的进展;他还主张,数学家并不是决定谁有资格研究其问题的仲裁者。
一个值得记住的历史规律
这一结果符合东北大学计算机科学教授Emanuele Viola在2018年一篇题为《我相信P=NP》(I Believe P=NP)的文章中勾勒的规律。20世纪50年代,安德烈·柯尔莫哥洛夫猜想两个n位整数相乘需要平方时间,他23岁的学生阿纳托利·卡拉楚巴在一周之内就找到了更快的算法。1968年,沃尔克·施特拉森推翻了标准矩阵乘法已是最优的假定。Viola的论点是,研究者反复宣布某些计算壁垒,随后又被巧妙的算法突破,人类一直低估了高效计算的能力范围。推翻ETH看来是这份清单上的又一条目,不过它究竟代表真正的实用捷径,还是只是对理论边界的小幅推进,目前仍不清楚。
从中应当了解什么
- 沿用约三十年的指数时间假设已被一份AI生成的证明推翻,该证明经Lean机器检验,并由该假设的原作者审阅把关。
- 这一证明给出了k-CNF可满足性问题的确定性亚指数算法。它没有证明P等于NP,格雷格·布罗克曼也表示P很可能仍不等于NP。
- 这一结果并未证明加密、银行和加密货币的安全已被攻破。
- 要把理论上的界限转化为真实软件的提速,还需要大量后续研究,常数因子也可能限制其实际用途。
对于关注这一领域的读者,可以采取几项具体行动。研究结果依赖ETH作为条件性困难假定的研究者,应重新检视这些结果。评估未来AI生成的数学成果时,应先确认是否在Lean这类证明助手中完成了形式化验证,再把相关论断视为定论;同时要核查所声称的算法是否具有可行的常数和指数,而不是默认它可以直接部署。至于日常安全,挂锁的比喻依然适用:每多一个字符,攻击者的搜索空间就成倍扩大,所以密码长度仍是最简单的防御手段。


