AI模型推翻指数时间假设？先别急着改写教科书

据TechCrunch在2026年10月28日报道，前沿AI实验室声称其模型反驳了计算复杂性理论中的指数时间假设（Exponential Time Hypothesis，ETH）。报道摘要称，TechCrunch采访了一位MIT计算机科学家，他的任务正是向外界解释OpenAI这一最新、令人费解的发现。消息之所以引发震动，是因为ETH不是一条普通猜想，而是精细复杂性理论的核心支柱之一；若它真被推翻，受影响的将不只是数学界，还包括算法设计、密码学参数和AI辅助科研的可信度。

ETH是什么，为什么重要？

ETH由Impagliazzo和Paturi在1999年前后系统提出，核心断言是：3SAT等经典NP完全问题不存在亚指数时间算法。换句话说，随着变量数增加，最坏情况下的求解时间不能低到exp(o(n))。它比P≠NP更强、更具体，是许多细粒度下界结果的基石。研究者常以ETH为假设，证明某类问题“不可能更快”，例如编辑距离、图算法和某些参数化问题。若ETH被反驳，意味着3SAT存在亚指数算法，大量下界证明需要重写，算法竞赛与理论计算机科学的地图都会被改写。

“前沿AI实验室称，其模型反驳了指数时间假设。”——TechCrunch报道标题所述核心主张

AI如何“反驳”一个假设？

从报道信息看，最可能的情形是模型产出了一个证明、一个算法或一个反例，声称能推翻ETH。但数学主张与数学真理之间隔着验证。AI模型可能混淆定义、引用未证明引理、进行循环论证，或在自然语言证明中隐藏关键步骤。因此，MIT科学家的角色不是为模型背书，而是帮助公众理解这项发现到底意味着什么、哪些部分可检验。现代数学界已有Lean、Coq等形式化验证工具，但把复杂证明完整形式化仍是巨大工程。没有形式化验证和独立复现，所谓“反驳”只能视为待检验的强主张。

若成立，冲击波会有多大？

首先，算法领域将出现范式变化：亚指数3SAT算法会带动大量NP问题的加速，影响优化、规划、验证和自动推理。其次，密码学需重新评估安全参数，但要注意，SAT有更快算法不等于所有密码立即被攻破，实际影响取决于具体归约和算法常数。再次，复杂性理论会进入重构期，许多以ETH为条件的下界结果失去前提，研究者需要寻找新假设。最后，对AI行业而言，若模型真能提出可验证的数学突破，AI for math将从辅助猜想走向发现引擎；若不能，则是一次关于AI科研炒作的警示。

编者按：先过三道验证关

面对“AI推翻ETH”这样的标题，理性态度是看证据而非看声量。第一关是形式化：证明能否被证明助手检查；第二关是独立复现：外部专家能否在相同设定下得到结论；第三关是社区评审：结论是否经得起长期同行检验。前沿实验室也应公开模型输出、提示词、验证脚本与失败案例，而不是只发布令人震惊的摘要。科学传播的挑战在于，AI生成的“发现”越惊人，越需要可审计的证据链。

目前TechCrunch披露的信息仍有限，MIT科学家的解释或许能帮助我们区分“模型说了什么”和“数学证明了什么”。在更多细节公布前，最稳妥的判断是：这是一条值得追踪的重大线索，但还不是改写教科书的时刻。

本文编译自TechCrunch