OpenAI 说 ETH 为假，但 P vs NP 没被解决：一文讲清「指数时间假设」
10 月 26 日，OpenAI 一次性发布三项成果声明：数学（局部光滑猜想）、计算机（ETH 为假）、物理（QCD 存在性）。
三项里讨论度最高的是第二个。AI 群里立刻出现两种解读：「P vs NP 被证明了？」「加密要完了？」
都不是。
这篇文章用大白话讲清三件事：ETH 是什么、它被推翻意味着什么、以及为什么现在还不能下结论。
一、先用数独讲清 P vs NP
一个空数独，填满它很难。一个填好的数独，检查它对不对很简单——看每行、每列、每个宫有没有重复就行。
「找答案难、验证答案易」——这就是 P vs NP 问题的核心。
- P 类：能快速解出来的问题。比如排序一堆数字。
- NP 类：答案能快速验证的问题。比如数独——解出来费劲，检查只要几秒。
- 能快速解的，一定能快速验证。所以 P 包含在 NP 里。
反过来呢？凡是能快速验证的，是不是也一定能快速解出来？
- 如果是，P = NP：加密体系可能全部失效（网上的支付、聊天、登录，靠的都是「很难解、很容易验」的数学题），物流路线、芯片设计、蛋白质折叠这类难解问题会突然变简单。
- 如果不是，P ≠ NP：有些问题就是天生难。
多数人相信 P ≠ NP。但五十多年了，没人能证明。克雷数学研究所把它列为七大千禧年难题之一，悬赏 100 万美元。
二、ETH：P vs NP 旁边那个「更能干活」的假设
P vs NP 的问题是：它太笼统了。「难」到底有多难？「快」到底有多快？证明起来无从下手。
所以计算机科学家在它旁边立了一个更具体、更好用的假设：ETH（Exponential Time Hypothesis，指数时间假设）。
它说的是：判断一个布尔公式能不能被满足（SAT 问题），大致需要指数时间——不存在什么聪明算法能把它压到「明显快于指数」。
SAT 有多重要？它是历史上第一个被证明的 NP 完全问题——NP 里「最难」的那批问题。只要 SAT 能被快速求解，所有 NP 问题都能被快速求解。它相当于所有难问题的「总开关」。
ETH 和 P vs NP 的逻辑关系，是全文最需要记住的一段：
- ETH 成立 ⇒ P ≠ NP（如果 SAT 连指数时间都省不掉，它肯定不属于 P）；
- 反过来不成立（P ≠ NP 不意味着 SAT 必须有指数时间，它可能有个「亚指数但超多项式」的算法）；
- 所以 ETH 为假 ≠ P = NP。这是本次传播中最容易被混淆的一点。
ETH 为什么好用？因为它是条件性困难结果的地基。过去二十年，几百篇论文的固定句式是：「在 ETH 成立的前提下，这个问题不可能比某某算法更快」。这类结论覆盖图论、计算生物学、数据库、计算几何等领域。
一句话：ETH 是算法世界地图上「此路不通」标牌的制造机。
三、ETH 为假，意味着什么？
按 OpenAI 的说法（10 月 26 日官方公告）：他们的系统证明了 ETH 为假，并且已经用 Lean 做了形式化验证。
如果这个证明成立：
- 那几百篇「在 ETH 前提下」的困难性结论，前提全部动摇——不是结论一定错了，而是「困难」的边界可能整体上移：这些问题也许存在更快的算法。
- 对算法研究者来说，这是地图重画级别的消息：原先标着「此路不通」的地方，可能值得重新探索。
- 但 OpenAI 自己的措辞也很克制：「找到这些算法、把理论进展变成实际改进，还需要大量后续研究。」理论上的加速空间，和工程上真的更快，中间隔着很远。
而且它对 P vs NP 本体什么都没说（见上）。对密码学也没有直接冲击：加密依赖的是「很难解」的问题，只要 P ≠ NP 还成立，密码学的地基就在。
四、这次为什么值得认真对待
三个细节，让这次声明和「狼来了」式的 AI 大新闻不太一样：
1）验证班子很硬，而且是「当事人审自己」。
OpenAI 组建的外部审查组里有 Russell Impagliazzo 和 Ramamohan Paturi（UCSD）——他们是 ETH 的原始提出者（2001 年，与 Francis Zane 一起）；还有 Ryan Williams（MIT）——他此前否定过 ETH 的强版本。
让假设的提出者亲自审查「否定自己假设」的证明，这在科学史上都不常见。他们的结论会很有分量。
2）Lean 形式化 + 原始数据全公开。
自然语言证明 10 月 16 日产出，10 月 17 日完成 Lean 形式化；论文和 Lean 证明都放进了 OpenAI 的公开仓库（openai/math），任何人都可以下载复编译。他们还承诺出资办会议，专门研讨这个结果对领域的冲击。
3）发布机制变了。
这是 OpenAI 在 10 月初「722 篇手稿风波」后的第一次重大发布。上一次是先发后议，被数学界批评「权力展示」；这一次改成了「先议后发」：先请外部专家当「牧羊人」（shepherd），再按他们的建议决定怎么公开——物理那一项甚至决定先不放出材料、由外部组自己写。还附了四条原则：透明（不签保密协议）、不求学术功劳、认可外部组、保持独立。
这套机制能不能持续，比单个结果更值得观察。
五、现在该信几分
目前的状态是：宣称级，待审查。
- Lean 验证 ≠ 学界认可。Lean 只保证「推导逻辑自洽」，不保证「被验证的命题就是你理解的那个问题」——中间还有一层人工核对。
- 外部专家组「刚开始审查」。Impagliazzo 参与审查是双刃剑：他是最懂 ETH 的人，也最可能有立场——自己的假设被推翻，需要极高的证据标准才会认。
- 在审查结论出来之前，把「ETH 为假」当成既成事实，为时过早。
三个可以跟踪的点：
- 审查组的公开结论（以及是否出现异议）；
- 条件性困难文献是否出现系统性重审（「无条件化」改写潮）；
- SAT 求解器社区的反应——理论上的「更快算法」是否引出实际改进。
附：另外两项声明一句话版
- 局部光滑猜想（数学）：声称在所有维度被证明——由此顺带解决所有维度的挂谷猜想与 Stein 限制猜想。这是继 10 月初「三维极大函数版、四维集合版」手稿之后的再度推进。
- QCD 存在性（物理）：给出了含量子色动力学与标准模型统一完成的严格存在性证明，子问题包含纯杨-米尔斯理论存在性——千禧年难题「杨-米尔斯存在性与质量间隙」的一部分（注意：只是存在性部分，不是完整命题）。
结语
把三件事分开看：
- P vs NP：没被解决，还在原地；
- ETH：被声称推翻，待审查——它动摇的是几百篇论文的「前提」，而不是密码学；
- AI4Math：继 722 篇手稿之后，AI 开始碰「基础假设」级别的目标了。
一句话总结：「AI 在逼近世界难题，但 P vs NP 还在原地。」
事实来源与口径：OpenAI 官方公告《Working with academic communities to build scientific understanding》（2026-10-26）；ETH 提出时间口径为 2001 年 JCSS 论文《Which Problems Have Strongly Exponential Complexity?》（1998 年有前置工作）；「几百篇」为公告原文 "hundreds of papers" 的转述；所有结果均为「声称级」，待外部审查，本文不构成任何结论背书。