#模型时代# OpenAI 与 Anthropic 同日推翻 ETH，离解决 P vs NP 还有多远？

10 月 26 日，OpenAI 宣布，它的内部模型推翻了存在 27 年的“指数时间假设”，简称 ETH。几个小时后，竞争对手 Anthropic 也发布了一篇由内部 Claude 模型独立完成的论文，得出了完全相同的结论。两家公司不仅把论文公开到了 GitHub 上，还都附上了经软件逐行检查的数学证明。

为了确认这一结果的含金量，OpenAI 请了三位学者组织公开审查——其中两位正是 1999 年提出 ETH 的“本尊” Russell Impagliazzo 和 Ramamohan Paturi，另一位是 MIT 教授 Ryan Williams。三位学者不签保密协议、不拿任何报酬，OpenAI 则应他们的要求，同意公开全部原始数据。

为什么推翻一条数学假设，会牵动整个学界？

因为在过去 27 年里，虽然没人能证明 ETH 对不对，但大家都默认它是对的，图论、数据库、计算生物学等领域的几百篇论文都拿它当大前提。更重要的是，ETH 还连着克雷数学研究所悬赏一百万美元的世纪难题：P vs NP。

ETH 到底说了什么，凭什么撑起几百篇论文？AI 究竟找到了什么，让它不再成立？ETH 倒了，P vs NP 是不是也快有答案了？

一、一道让人头疼的开关谜题

ETH 讨论的是一道叫 3-SAT 的经典难题，可以把它想成一道开关谜题。

面前有一排开关，比如 100 个，每个只能拨向“开”或“关”。手头另有几百条规则，每条规则只挑其中三个开关提要求，比如“A 开着，或者 B 关着，或者 C 开着”，三个条件只要满足一个，这条规则就算过关。你要找的是一种开法，让几百条规则同时过关。名字里的“3”指每条规则牵涉三个开关，SAT 是英文 satisfiability 的缩写，意思是“可满足”。

单看一条规则，随手一拨就能满足。麻烦在于开关是共用的。同一个开关会出现在十几条规则里，为了满足这一条去拨动它，原本已经过关的另外几条可能就坏了；等去修补那几条，又会牵动更多开关。

规则一多，往往只能在所有可能的开法里大海捞针。100 个开关共有多少种开法？答案是一个大约 1 后面跟 30 个零的天文数字，就算用全世界最快的超级计算机挨个试，也得算上几万年。

但反过来，如果有人直接给你一种现成的开法，检查它对不对只需要对照规则逐条核对，一眨眼就能做完。找答案极难，查答案极易，这就是开关谜题的特点。

二、ETH 断言了什么？

为什么仅仅 100 个开关，试错的工作量就会膨胀到这种天文数字？因为开关每多一点，工作量就会翻倍暴涨。

假设现在有 100 个开关，你在用最笨的办法挨个试。这时候，旁边新加了第 101 个开关。这个新开关有“开”和“关”两种状态：它拨到“开”时，前面 100 个开关的所有组合你得试一遍；它拨到“关”时，前面所有的组合你又得重头再试一遍。也就是说，用笨办法，每多加 1 个开关，工作量就立刻翻一倍。

几十年来，研究者想出了不少抄近道的聪明办法，利用规则提前排除掉大量错误组合，来压制这种翻倍的速度。用上这些办法后，多加 1 个开关不再让工作量立刻翻倍了，而是每多加 2 到 3 个开关，工作量才翻一倍。

那么，如果未来的算法再聪明一点，能不能变成多加 10 个、100 个、甚至 1000 个开关，工作量才翻一倍？

1999 年，Impagliazzo 和 Paturi 提出了 ETH，直接给这种设想泼了一盆冷水。ETH 断言：面对最难的那些开关谜题，人类就算把算法改进到极致，“多加几个开关工作量才翻倍”的这个数字，也有一个固定的上限，具体是多少，ETH 没有说。不管谜题扩大到一万个还是一亿个开关，这个数字永远超不过那个天花板。

像这样“每隔固定数量的开关，工作量就翻一倍”的爆炸式增长，数学上叫做“指数时间”，这也是“指数时间假设”名字的由来。这条假设从来没人能证明，但整整 27 年里，绝大多数研究者都相信它是对的。

三、ETH 凭什么撑起几百篇论文？

因为其他领域的很多难题，其实都是开关谜题“乔装打扮”成的。

在物流排程、数据库、计算生物学里，也有大量算起来极慢的难题。科学家很想证明这些难题“算法已经到顶、不可能再快了”，但直接证明往往无从下手。

后来科学家发现了一个妙招：可以把一道开关谜题，原封不动地“翻译”成一道物流排程题。比如把“开关 A 打开”对应成“1 号货车走东线”，把开关规则对应成送货要求。只要排程题一解开，对照着翻回来，开关谜题的答案也就出来了。

这就意味着：假如有人能发明一种快速算法，把物流排程算得飞快，那他就等于顺手把开关谜题也算得飞快了。

可 ETH 偏偏断言“开关谜题绝对快不了”。既然开关谜题快不了，反过来也就证明了：物流排程题也绝对快不了。

靠着这种“拉开关谜题当垫背”的办法，过去二十多年，图论、数据库、生物信息学里的几百篇论文，全都顺理成章地证出了各自领域的速度极限。ETH 就像最底下的那块承重墙，这几百个结论全都压在它上面。

四、AI 找到了什么？

两家公司的 AI 模型找到了一种全新的解法，打破了 ETH 所说的“固定上限”。

用上这个新解法后，不再是固定每加几个开关工作量就翻倍，而是开关总数越多，让工作量翻倍所需增加的开关数也越多。不过这个间隔长得极慢：开关从 100 个涨到 100 万个，它也只多出寥寥几个。

由于翻倍的步子越迈越大，工作量的增长速度比刚才说的“指数时间”慢了一档，所以在数学上叫做“亚指数时间”，“亚”就是次一等的意思。ETH 断言开关谜题的工作量不可能增长得这么慢，所以 ETH 直接被推翻了。

而且，AI 的这个解法不靠“掷骰子随机蒙”，每一步都按固定公式稳扎稳打地算，数学上叫“确定性算法”。它也不只判断谜题有没有解，还能精准数出符合所有规则的开法一共有多少种。

OpenAI 的论文题为《The Exponential Time Hypothesis is False》，意思是“指数时间假设是错的”。论文显示，其内部模型在 10 月 16 日找到了证明，并在第二天写成了 Lean 格式。Lean 是一种像检查代码一样逐行核对数学推理的软件。而 Anthropic 披露，它的内部 Claude 模型也是在 10 月 16 日这天独立找到了核心算法，找到核心算法的过程中没有人工参与。

五、ETH 倒了，P vs NP 有答案了吗？

还没有，而且差得还远。

推翻 ETH 之所以让人联想到 P vs NP，是因为这两件事本质上都是在猜“开关谜题到底能算多快”，只是 ETH 赌它连亚指数时间都做不到，P vs NP 问的是它能不能真正算得快。

在计算机科学里，题目按难度分为两类：

⚬ P 类问题，是“能很快算出答案”的题。
⚬ NP 类问题，是“只要有人给出答案，就能很快检查对不对”的题。

那些“很容易检查答案”的题（NP），是不是其实都能“很快算出答案”（P）？这就是 P vs NP 难题：如果都能很快算出来，就是 P=NP；如果有些题就是好检查、但永远算不快，就是 P≠NP。

而开关谜题正是所有“好检查、难计算”难题的总代表，数学上叫 NP 完全问题：所有 NP 类问题都能“翻译”成开关谜题。因此，整个 P vs NP 难题就归结为一句话：开关谜题到底能不能“很快”算出来？

数学上把这种“真正算得快”的速度叫做多项式时间。放到开关谜题里，它和 ETH、AI 新解法的差距有多大？

假设面前摆着一道 100 万个开关 的大谜题，把解题速度排成三级台阶就一目了然了：

⚬ 第一级：指数时间（ETH 认为的死限）。哪怕已经有 100 万个开关了，翻倍间隔也停在一个固定的数上；眼下最好的方法，是多加 两三个 开关，工作量就翻一倍。
⚬ 第二级：亚指数时间（AI 做到的这一步）。间隔会随开关增多慢慢变长，但长得极慢：到了 100 万个开关，也只比第一级多出 寥寥几个 开关。
⚬ 第三级：多项式时间（证明 P=NP 需要的速度）。面对 100 万个开关，要一口气多加 几十万个 开关，工作量才会翻一倍。

AI 带着人类从第一级迈上了第二级，确实把赌人类“迈不出第一级”的 ETH 给推翻了；但从“多加几个开关翻倍”到“多加几十万个开关才翻倍”，中间还隔着十万八千里。所以，ETH 虽然倒了，P=NP 依然遥远，学界主流仍然认为 P≠NP 大概率成立。

审查组成员 Ryan Williams 对 TechCrunch 说，这次的结果动摇了学界的不少直觉，每个计算机科学家都该给“P=NP 可能成立”多留一点心理空间。但他同样认为，AI 给出的这个解法大概还不是终点；至于 P=NP 本身，也就是所有好检查的题都能真正算得快，在他看来依然像是一件“天上掉馅饼的美事，美好得不太可能成真”。

六、这对日常计算有影响吗？

基本没有，冲击主要集中在理论界。

在理论层面，过去二十多年压在 ETH 这块承重墙上的几百个结论，突然失去了大前提。不过这并不代表那些问题明天就能算得飞快。把其他难题“翻译”成开关谜题时，题目规模往往会膨胀得比原题大得多，比如从 100 个变量变成 1 万个，AI 在开关谜题上省下来的那点工夫，很容易在翻译过程中被抵消掉。接下来，学者们需要把这几百个结论一个个拿出来重新检查，看看哪些是真的快不了，哪些其实还有提速空间。

至于工业界平时用来做芯片验证、物流排程的专用软件，也就是 SAT 求解器，处理的都是现实中带有特定规律的问题，靠的是日积月累的工程技巧。正如复杂性理论学者 Lance Fortnow 所评价的，新解法的思路有希望，但不会给工业界的实际软件带来多大改变。