指数时间假说被推翻了吗：两篇 AI 论文里的 3-SAT 新算法

We refute the Exponential Time Hypothesis (ETH) by presenting a deterministic algorithm for 3-SAT on n variables that runs in $2^{o(n)}$ time.

这是 2026 年 10 月 27 日公开的一篇预印本（还没经过期刊审稿、先放到网上的论文）摘要的第一句，作者一栏写的是 Claude¹。翻译过来是：“我们给出一个在 $2^{o(n)}$ 时间内解决 $n$ 个变量的 3-SAT 的确定性算法，从而推翻了指数时间假说（ETH）。”前一天，OpenAI 也在 GitHub 上放出了一篇标题直接叫《指数时间假说是错的》的论文²。转到中文社交媒体上，标题很快变成了“AI 推翻三十年计算机难题”“P=NP 又近了一步”“密码学要变天”。

这句话里几乎每个词都需要解释：3-SAT 是什么？“指数时间”指什么，凭什么是一个“假说”？$2^{o(n)}$ 是快还是慢？它和大名鼎鼎的 P vs NP 又是什么关系？两家 AI 是怎么做到的，结论靠得住吗？

这些问题都可以从一道简单的逻辑题讲起。

一、一道逻辑谜题：什么是 SAT

安排一次聚会

假设你要请三位朋友 A、B、C 来家里，但他们之间有些讲究：

1. A 和 B 至少要来一个，不然没人张罗。
2. A 和 C 不能都来，他们俩合不来。
3. 如果 B 来，C 也得来，B 一个人不肯来。
4. A 和 C 至少要来一个，因为只有他们会做饭。

有没有一种邀请方案，让四条要求同时满足？

每位朋友只有“来”和“不来”两种状态。我们用一个变量表示，来记作 1，不来记作 0。这种只能取 0 和 1（也可以说“真”和“假”）两个值的变量叫布尔变量，名字来自 19 世纪的数学家布尔（George Boole），他最早把逻辑写成了代数。下面用小写的 $a,b,c$ 分别表示 A、B、C 来不来。

再看每条要求。第 1 条是“A 来，或者 B 来”，写成 $a \lor b$，符号 $\lor$ 读作“或”，两边只要有一个成立，整句就成立。第 2 条“A 和 C 不能都来”换个说法是“A 不来，或者 C 不来”。“不来”是“来”的反面，用 $\lnot a$ 表示，读作“非 $a$”，$a=1$ 时 $\lnot a=0$，反之亦然。于是第 2 条写成 $\lnot a \lor \lnot c$。第 3 条“如果 B 来，C 也得来”，等价于“B 不来，或者 C 来”，写成 $\lnot b \lor c$。第 4 条是 $a \lor c$。

像 $a \lor b$ 这样，几个变量（或它们的反面）用“或”连起来的一句话，叫一个子句。四条要求必须同时成立，用“且”（$\land$）把它们连起来：

“一串子句用‘且’连起来”的这种写法叫合取范式（CNF，合取就是“且”的意思）。现在问题可以说得很精确了：给定一个合取范式，有没有一组 0/1 取值，让它整体成立？这个问题叫可满足性问题，英文 Boolean Satisfiability，缩写就是 SAT。如果每个子句最多只有 3 个变量，就叫 3-SAT。我们的聚会问题每句只有 2 个变量，当然也算 3-SAT 的一个例子。

最笨的办法：挨个试

三个人，每人两种状态，一共 $2\times2\times2=8$ 种方案。全部列出来检查一遍：

答案是有两种方案：只请 A，或者请 B 和 C。

这张表也显示出 SAT 的一个特点。拿到一个方案，检查它对不对很容易，四条要求逐条看一遍就行；但要找到一个对的方案，最直接的办法只有挨个试。

人数一多，挨个试就不行了。每多一个变量，方案数就翻一倍，$n$ 个变量就有 $2^n$ 种。$n=50$ 时大约是 $10^{15}$ 种，一台每秒检查一万亿（$10^{12}$）种的计算机要算 19 分钟；$n=100$ 时约 $1.3\times10^{30}$ 种，要算 400 亿年，是宇宙年龄的三倍。实际中的 SAT 问题常有几千、几万个变量。

为什么要关心这样一道谜题？因为大量现实问题都能写成 SAT。排课（某老师周一上午不能有课，两门课不能同时在一间教室）、检查芯片设计有没有错、填数独，都可以把“选或不选”“是或不是”设成布尔变量，把规则写成子句。SAT 会解了，这些问题就都会解了。

那么，除了挨个试，到底有没有本质上更快的办法？要讨论“更快”，得先说清楚怎么比较快慢。

二、算法的快与慢

数步数，而不是看秒表

同一个算法，在新电脑上跑得快，在旧电脑上跑得慢，所以计算机科学不用秒表衡量算法，而是看步数怎样随问题规模增长。问题规模记作 $n$，对 SAT 来说就是变量个数。

有的算法的步数是 $n^2$、$n^3$ 这样的幂函数，或者几个幂函数相加，这叫多项式时间；有的是 $2^n$ 这样的指数函数，叫指数时间。这两类函数在 $n$ 小的时候看不出差别，$n$ 一大差距就大得离谱：

多项式时间的算法，$n$ 翻一倍，$n^3$ 也只是变成原来的 8 倍，电脑快一点就追得上。指数时间的算法，$n$ 只要加 1，步数就翻倍，电脑快一千倍也只能多处理 10 个变量。所以大家通常把“有多项式时间算法”当作“能高效解决”的标准。

P、NP 和 NP 完全

按这个标准，问题可以分成几类。

能在多项式时间内解决的问题，叫 P 类（P 是 Polynomial，多项式）。比如把一串数从小到大排好序、在地图上找两点之间的最短路线，都属于 P。

答案能在多项式时间内检查的问题，叫 NP 类。SAT 就属于 NP：给你一组取值，逐个子句检查一遍，步数和公式长度成正比。NP 的全称是 Nondeterministic Polynomial（非确定性多项式），名字来自一种假想的“能同时猜遍所有答案”的机器，我们只要记住它的意思是“答案容易检查”就够了。能解决的问题当然也能检查答案，所以 P 包含在 NP 里面。

NP 里面最难的一批问题叫 NP 完全问题。1971 年 Cook 证明了 SAT 就是其中之一，1972 年 Karp 又找出了一大批。它们“最难”的含义是：NP 里的任何问题，都能在多项式时间内改写成一个 SAT 问题，答案保持不变。这种改写叫归约。比如数独可以改写成 SAT：每个格子填每个数字设一个变量，“每格恰好一个数”“每行不重复”等规则写成子句。既然所有 NP 问题都能这样改写，只要 SAT 有了多项式时间算法，所有 NP 问题就都有了。3-SAT 也是 NP 完全的，因为再长的子句，引入几个辅助变量后都能拆成每句不超过 3 个变量的几个子句，可满足性不变。

于是就有了那个著名的问题：P 是否等于 NP？也就是说，凡是答案容易检查的问题，是不是也都容易解决？这是克雷数学研究所悬赏一百万美元的七个千禧年难题之一，至今没有解决。绝大多数研究者相信 P ≠ NP，也就是 SAT 没有多项式时间算法。

但“没有多项式时间算法”并没有回答到底要多慢。下面我们就来看，人们为此努力了几十年，SAT 到底被做到了多快。

三、几十年的努力：只能改底数

比穷举快一点

挨个试的方法叫穷举，要 $2^n$ 步。人们找到过不少聪明的办法。1985 年 Monien 和 Speckenmeyer 发现，可以挑一个子句，按其中的变量分情况讨论，很多情况会提前出现矛盾、不必再往下试，这样做到了约 $1.618^n$ 步。1999 年 Schöning 的算法做到了 $(4/3)^n$³：先随机给所有变量赋值，哪个子句不满足，就随机翻转它里面的一个变量，反复多次。它是一个随机算法，允许“抛硬币”，以极高的概率给出正确答案；与之相对，每一步都确定、同样的输入一定得到同样结果的叫确定性算法。PPSZ 算法⁴经过多年改进，在 2014 年降到 $1.308^n$。

换成以 2 为底来比较

这些底数看起来五花八门，换成以 2 为底就能放在一起比。用对数，$1.308 = 2^{\log_2 1.308} \approx 2^{0.388}$，所以

这相当于说：用 PPSZ 解 $n$ 个变量的问题，和穷举 $0.388n$ 个变量一样难。每一次进步，都只是把指数里 $n$ 前面的系数往下压一点，从 1 压到 0.69，再到 0.42、0.39。

时间仍然是“每多一个变量就乘上一个固定倍数”，只是倍数从 2 变成了 1.3。按 1.308 倍算，$n=1000$ 时步数约 $10^{117}$，照样算不完。这个系数能不能一直压下去，压到任意小？还是存在一个大于零的下限？

四、指数时间假说说的是什么

假说的内容

1999 年，Russell Impagliazzo 和 Ramamohan Paturi 把大家的直觉写成了一个明确的猜想⁵，叫指数时间假说（Exponential Time Hypothesis，ETH）：

存在一个常数 $\delta>0$，使得没有任何确定性算法能在 $2^{\delta n}$ 步内解决 $n$ 个变量的 3-SAT。

用图 2 的话说：那些条形有一个最短长度 $\delta$，再聪明的算法也压不破。它叫“假说”，是因为没有人能证明它，只是几十年来所有人都没能突破，大家倾向于相信它。

它和 P ≠ NP 说的不是一回事。P ≠ NP 只说 3-SAT 没有多项式时间算法，比如 $n^3$ 步。但在多项式和 $2^{\delta n}$ 之间还有一大片地带。比如 $2^{\sqrt n}$：$n=10000$ 时，$n^3$ 是 $10^{12}$，$2^{\sqrt n}=2^{100}\approx10^{30}$，而 $2^{0.388n}$ 有一千多位数。$2^{\sqrt n}$ 比任何多项式都慢，又比任何 $2^{\delta n}$ 都快。P ≠ NP 不排除这片地带里的算法，ETH 把它们也排除了。所以 ETH 是比 P ≠ NP 更强的断言：ETH 成立能推出 P ≠ NP，反过来不行。

$2^{o(n)}$ 是什么意思

新论文说的 $2^{o(n)}$，读作“2 的小 o(n) 次方”。$o(n)$ 表示一个和 $n$ 相比越来越微不足道的量，准确说是它除以 $n$ 的比值随 $n$ 增大趋于 0。比如 $\sqrt n$：$\sqrt n / n = 1/\sqrt n$，$n=100$ 时是 0.1，$n=10000$ 时是 0.01，越来越小，所以 $\sqrt n$ 是 $o(n)$。而 $0.001n$ 不是，它除以 $n$ 永远是 0.001。

$2^{o(n)}$ 的时间叫次指数时间。它的意思是：对任何你给定的 $\delta>0$，哪怕是 0.000001，只要 $n$ 足够大，它都比 $2^{\delta n}$ 小。所以推翻 ETH 只需要做到：对每一个 $\delta>0$，都有一个 $2^{\delta n}$ 步的算法，也就是图 2 里的系数可以压到任意小。

这和“多项式时间”还差得很远。上面的 $2^{\sqrt n}$ 就是次指数的，照样算不完。

一串互相牵连的假说

ETH 还有一个更强的兄弟，强指数时间假说（SETH）。允许每个子句有 $k$ 个变量的问题叫 $k$-SAT。SETH 说：$k$ 越大，$k$-SAT 的最好算法越接近穷举，系数越接近 1。SETH 成立能推出 ETH 成立。

另一个常用的假设是正交向量假说（OV）。给你两堆由 0 和 1 组成的等长串，比如 1010 和 0101，要找出一对“没有同一位都是 1”的串（数学上叫内积为 0、互相正交）。最直接的做法是两两比较，每堆 $n$ 个串就要比 $n^2$ 次。OV 说没有本质上更快的办法。SETH 能推出 OV。

这些假说之所以重要，是因为大量“下界”结果建立在它们之上。下界是指“某个问题不可能比多快更快”。直接证明下界极难，研究者通常绕一个弯：先证明“如果问题 X 有某种快算法，那么把 3-SAT 归约到 X，3-SAT 就会有次指数算法”，然后写下“除非 ETH 不成立，X 就没有这种快算法”。Anthropic 的论文里用 Claude 做了一次文献检索，找到 800 多篇论文至少有一个结果只在 ETH 或比它更强的假设下成立¹。

并不是所有人都坚信这些假说。2019 年 Ryan Williams 给过一个主观估计：ETH 为真的可能性约 70%，SETH 约 25%⁶。

那么这一次，是谁、用什么推翻了它，证据有多硬？

五、新闻核实：发生了什么

时间线

把几份原始材料对一遍，事情的经过是这样的：

• 10 月 16 日，OpenAI 和 Anthropic 的内部模型各自得到了证明。Anthropic 说核心算法是一个内部研究模型在没有人类输入的情况下找到的，用了 1400 万个输出 token（模型输出文字的计数单位，大致一个 token 是一个汉字或半个英文单词）¹。
• 10 月 17 日，OpenAI 把证明形式化到了 Lean，也就是翻译成计算机能逐步检查的形式（下文细说），10 月 25 日修订论文，26 日公开²。
• 10 月 26 日，Shiva Kintali 发了一份 22 页的简化讲解，只用多项式、解方程这类基础数学，重写了 OpenAI 证明的主线⁷。
• 10 月 27 日，Anthropic 在 Hexagon 预印本平台发出论文，并公开 Lean 证明⁸。
• ETH 的提出者 Impagliazzo、Paturi 和 MIT 的 Ryan Williams 牵头组成审查组。他们在公开信里写明：参与审查不代表认证这个结论。Williams 对 TechCrunch 说，证明里有些部分看起来很常规，但有“两三处”非常陌生⁹。

两篇论文的结论基本一致：存在确定性算法，能在大约 $2^{n\log\log n/\sqrt{\log n}}$ 步（再乘上一个常数倍数，这里 $\log$ 以 2 为底）内数出 3-SAT 公式有多少组解，对 $k$-SAT 也成立。指数里的 $\log\log n/\sqrt{\log n}$ 随 $n$ 增大趋于 0，所以这正是 $2^{o(n)}$。数出解的个数比只判断“有没有解”更难，比如聚会问题会数出 2；数出来大于零，就说明有解。

Lean 检查了什么

Lean 是一种证明助手：把数学证明写成程序，每一步推理都由一个很小的“内核”程序机械地检查，内核接受了，就说明从定义到结论没有逻辑漏洞。Anthropic 的 Lean 证明被三个独立实现的内核接受，除了 Lean 的三条标准公理（数学里不加证明、直接承认的出发点）外不依赖任何额外假设，整个证明分成 1050 个文件¹。

但机器只能检查“从这些定义推出这个结论”。定义本身是不是真的表达了 ETH，机器管不了。Anthropic 在附录 E 里写得很直白：Lean 证明是 AI 写的，由同一模型的其他实例审阅，写作时没有已知的人检查过。OpenAI 一边，Lean 里形式化的运行时间界比论文正文略弱，但仍然是次指数的¹⁰。

所以合理的判断是：两家用不同的方法独立得到同一个结论，各自有机器检查，又有一位人类研究者把其中一份改写成了可以逐行读懂的证明，这比通常“某某猜想被推翻”的新闻要可靠得多；但它还没有经过同行评审（投稿后由同领域专家审稿），审查组也还没有给出结论。

哪些说法被夸大了

既然结论大概率成立，真正有意思的问题就来了：几十年只能改底数，新算法到底多做了什么？我们先看老办法卡在哪里。

六、分而治之的极限

把公式切成两半

两篇论文的算法都是在数解的个数，我们也从“怎么数”说起。数解的个数有一个天然的分而治之思路。如果一个公式的变量能分成两组，每个子句只用到其中一组，那么两组各自数出解的个数再相乘就行。比如聚会再多请两位朋友 D 和 E，他们只受一条“D 和 E 至少来一个”的约束，和 A、B、C 毫无关系，那么总解数就是“A、B、C 的解数”乘“D、E 的解数”。代价从 $2^n$ 降到 $2 \times 2^{n/2}$：$n=100$ 时，从 $2^{100}$ 降到 $2\times2^{50}$，相当于从 400 亿年降到 40 分钟左右。

实际的公式没这么干净，总有一些子句横跨两组。办法是把同时连着两边的那些变量（叫切口变量）的取值逐一枚举：每固定一种取值，两半就互不相干，可以分别数完再相乘，最后把所有取值的结果加起来。切口有 $c$ 个变量，就要枚举 $2^c$ 种取值。两半还可以继续往下切。

这个办法好不好用，全看切口有多大。

切口没法变小

我们做了个小实验：随机生成 3-SAT 公式，用一种近似方法找尽量小的均衡切口（切开后两半的变量数相等）。作为对照，再生成一种“链状”公式，它的每个子句只用三个编号相邻的变量。结果如下：

对比很鲜明。链状公式的子句只连相邻的变量，从中间一刀切下去只有 2 个变量跨着两边，不管 $n$ 多大都是 2。随机公式就不一样了，切口始终在 $0.4n$ 左右，不随 $n$ 变小。近似方法找到的不一定是最小的，但理论上早就知道这不是方法的问题。把每个变量画成一个点，在同一个子句里出现过的变量之间连线，就得到一张图（这里的“图”指点和连线组成的结构）。随机公式对应的图是一种扩张图：从中任取一大块点，它和外面的连线都很多。所以不管怎么切成两个大小相当的部分，跨过去的变量都正比于 $n$。

切口正比于 $n$，枚举它就要 $2^{cn}$。所以事先固定好怎么切、再枚举切口的算法，最多只能把系数从 1 压到某个常数，这正是图 2 里几十年的样子。

切口本身没法变小，那能不能让“跨过切口必须对上的信息”变少？

七、八平方恒等式：用正负相消换掉相等检验

把公式画成图

Anthropic 的证明先换了一个视角。把每个子句当成图里的一个节点，节点有自己的一份变量副本；两个子句共用变量时连一条边，边要检查两边副本的取值相等。一个 0/1 位叫一个比特，一条边要对上几个变量，就说它带几个比特。解的个数就是“所有副本的所有取值”上，每个节点“子句是否满足”（1 或 0）和每条边“两边是否相等”（1 或 0）全部乘起来再求和。

切口的代价，就是跨过切口的边一共带多少比特。前面的实验说明，对随机公式，这个数怎么切都降不下来。

网格和矩形

算法先把节点分成若干组，合并成少数几个大节点，使任意两个大节点之间都有一条边，每条边带的比特数差不多。然后把这些大节点摆到一个 $g\times g$ 的网格上。摆法是算法随便定的，它只用来提供两种分组：按行分和按列分。

网格上任取两行两列，交出四个角：左上 $a$、右上 $a'$、左下 $b$、右下 $b'$。对角线 $a$–$b'$ 和 $a'$–$b$ 这两条边既跨行又跨列。设 $a$ 手里有一个 3 比特串 $x$（三个 0/1 排成一串，比如 101，共 8 种可能）要和 $b'$ 手里的 $v$ 对上，$a'$ 手里的 $y$ 要和 $b$ 手里的 $u$ 对上，这两条边合起来就是检验 $[x=v]\cdot[y=u]$（方括号里成立记 1，不成立记 0）。

如果把每一行合并成一个大节点，这两条对角边都跨在两行之间，要付 6 比特；按列合并也一样是 6 比特。行、列两种合并方式的代价加起来是 12。

一个两百年前的恒等式

关键的一步是下面这个恒等式。它对所有 3 比特串 $x,y,u,v$ 成立：

其中 $\oplus$ 是按位异或：两个串逐位比较，相同得 0、不同得 1，比如 101 $\oplus$ 011 = 110。四个串异或为零，就是每一位上四个串的 1 的个数都是偶数。$\sigma$ 是一个只取 $+1$ 和 $-1$ 的函数，论文给出了它的具体写法（见文末代码）。

这个恒等式的来历很古老。先看一个熟悉的等式：

两个“两数平方和”相乘，结果还是两数平方和，它对应复数的模可以相乘。1818 年 Degen 发现，把“两个数”换成“八个数”同样成立，这就是八平方恒等式；1843 年 Graves 重新发现了它，背后是一种由八个实数组成的“数”，叫八元数¹¹。Anthropic 在附录 H 里讲了模型怎样在寻找分解方式的过程中走到这个恒等式，上面的式子就是从它推出来的。Anthropic 在附录 H 里讲了模型怎样在搜索分解方式的过程中走到这个恒等式。

这个式子一共涉及 12 个比特，可以直接验证。我们把 $4096$ 种取值全部代进去算了一遍，全部成立。更有意思的是它为什么成立：

右边的方括号只要求四个串异或为零，我们把这个条件叫奇偶约束。满足它的组合有 512 种，其中真正满足 $x=v$、$y=u$ 的只有 64 种。剩下 448 种里，括号中两项总是一个 $+1$ 一个 $-1$，恰好抵消。原来的“相等检验”被换成了一个更宽松的奇偶约束，多放进来的组合靠正负号自己消掉。

换了之后省在哪里

把右边乘开，得到两项。论文把含 $\sigma(x,y)\sigma(v,u)$ 的叫行选择，含 $\sigma(x,u)\sigma(v,y)$ 的叫列选择。

看行选择这一项：按行合并时，上一行手里有 $x,y$，下一行手里有 $u,v$，奇偶约束其实是 $x\oplus y = u\oplus v$，两行只需要在“$x\oplus y$”这一个 3 比特串上对上就行。$\sigma(x,y)$ 只依赖上一行，$\sigma(v,u)$ 只依赖下一行，各自乘进所在行即可。我们的实验也验证了，行选择项可以写成“枚举 3 比特 $\theta$，上一行一个函数乘下一行一个函数”的形式。于是按行合并时，行选择只付 3 比特，列选择付 6 比特；按列合并时正好反过来。

所以对每一项，挑它便宜的那个方向合并就行。行、列两种合并的代价之和，从原来的 $6+6=12$ 降到了 $3+6=9$。

代价：项数和一点额外开销

问题在于，边上的比特远不止 3 个。设一条边带 $3t$ 比特，就把它切成 $t$ 块，每块用一次恒等式，每个矩形就展开成 $2^t$ 项，整张网格的项数是 $2$ 的“总比特数的六分之一”次方，又回到指数了。

论文的处理是把项合并：一个矩形里，按“有几块选了列”分组，只有 $t+1$ 组，项数变成多项式级。代价是每组内部还要多记 $t$ 个比特，标出哪几块选了列。这样行、列两种合并的代价之和是 $11t$，而原来是 $12t$。两者中较小的一个不超过 $5.5t$，原来是 $6t$。每做一轮，跨在合并后节点之间的比特就乘上了 $11/12$。

有一点要注意：乘开以后，节点上的值会出现负数，每一项算出来的已经不是“有多少组解”，而是一个带正负号的和，只有所有项加起来，才回到真正的解数。Austrin、Kaski 和 Kubjas 研究过“按一个固定的顺序逐步合并求和”这类算法，并证明了它们不可能太快¹²，Anthropic 据此算出，这类算法的指数至少要有穷举的 49% 左右。新算法不受这个限制，因为它把一个和拆成许多带正负号的和，每个和按不同的方式合并。

一轮只省 $1/12$，怎么从“省一点”变成“省到任意多”？

八、递归：把指数压到零

一轮合并完，再按比特数重新分组、补齐，得到的正好又是一个“节点数更少、每对节点之间一条边”的同类问题，只是节点上的值变成了任意整数。于是可以对它再用一次同样的办法，这种“对缩小后的同类问题再用同一个办法”的做法叫递归。论文把每一层的系数写成一个数列的递推式：

其中 $K_\ell$ 是第 $\ell$ 层要求的节点数，$K_0 = 64$，$K_\ell = 9K_{\ell-1}^{16}$。时间大约是 $2^{e_\ell m}$，$m$ 是子句数。我们按这个递推式算了 30 层：

第 1 层因为 $K_0=64$ 太小，额外开销盖过了节省，系数是 1.03，比穷举还差。从第 2 层起，系数基本按 $11/12$ 的比例往下走，第 13 层低于 PPSZ 的 0.39，第 28 层低于 0.1。对任何给定的 $\delta$，取足够多的层数（层数只和 $\delta$ 有关，和输入无关），时间就低于 $2^{\delta m}$。这里的时间是按子句数 $m$ 算的。再用 Impagliazzo、Paturi、Zane 的稀疏化引理¹³，可以把任意公式拆成若干个子句数不超过变量数固定倍数的公式，于是 $2^{\delta m}$ 也就变成了 $2^{\delta n}$。这就推翻了 ETH。

但图里的 $K$ 同样值得看：第 1 层就要求约 $10^{30}$ 个节点，第 2 层约 $10^{479}$ 个。输入不够大，这些层根本搭不起来。Anthropic 自己估计：对子句数是变量数 5 倍的公式，要 $n > 10^{10000}$ 才比穷举快；只看 $n$ 的那个界，要 $n > 10^{10^8}$¹。这种只在天文规模上才兑现的算法，圈内叫“银河算法”。

即使不管常数，$o(n)$ 本身也收缩得极慢。两篇论文的指数是 $n\log\log n/\sqrt{\log n}$ 的量级，我们把它除以 $n$（把前面省略的常数倍数当成 1，这已经是对算法很宽容的假设）：

到 $n=10^6$ 时这个比值还有 0.97；要到 $10^{100}$ 才降到一半。$2^{o(n)}$ 在数学上比任何 $2^{\delta n}$ 都快，在现实里和穷举没有区别。

OpenAI 的证明也是这条路吗？

九、另一条路：变形，再插值

OpenAI 的证明走的是另一条路线。Kintali 的简化稿把它整理成了只用多项式和解方程的版本⁷，大意如下。

先把每个子句写成多项式。比如子句 $x_1 \lor \lnot x_2$ 写成 $1-(1-X_1)X_2$：只有 $X_1=0$、$X_2=1$ 时它等于 0，其余三种取值都等于 1，恰好是子句的真假。所有子句的多项式乘起来，满足全部子句时乘积是 1，否则是 0；对全部取值求和，就是解的个数。

然后对公式做一个变形：把每个变量替换成一个带参数 $T$ 的式子，比如把 $X_3$ 换成 $X_3 + T X_4$，$T=0$ 时就是原来的变量。巧妙之处在于，构造好的变形在 $T=1,2,\dots$ 这些整数点上，每个子句只依赖一小组变量，再加上少量测量值（若干变量的整数加权和）。把测量值枚举一遍，各组就能分开求和再相乘。这时算出来的数可以是负的，不再是解的个数。

最后，把求和结果看成 $T$ 的多项式 $H(T)$，它在 $T=0$ 处的值就是解数。我们在 $T=1,2,\dots$ 这些容易算的点上求出 $H$ 的值和它的几阶导数，再把整个多项式反推出来，代入 $T=0$。这一步叫插值，道理和“两点确定一条直线、三点确定一条抛物线”一样：一个多项式在足够多点上的信息，能唯一确定它本身。

Kintali 给了一个四变量的例子，我们照着算了一遍。公式是 $(x_1\lor x_3)\land(x_2\lor\lnot x_4)$，两个子句各有 3 组满足，答案是 9。变形取 $x_3 \to X_3 + T X_4$，$x_4 \to X_4 + T X_3$，在 $T=1$ 时两个子句都只依赖 $x_1$、$x_2$ 和测量值 $y = x_3 + x_4$：

这里 $H(T) = 9 - 2T - T^2$，在 $T=1$ 处只有 6。算法拿不到 $H$ 的完整表达式，但能在 $T=1$ 附近求出它的展开：令 $z = T-1$，$H = 9 - 2(1+z) - (1+z)^2 = 6 - 4z - z^2$。$H$ 最多是二次的，这三个系数就确定了它，代入 $z=-1$（即 $T=0$）就回到了 9。注意 $y=2$ 那一行，第一组的和是 0，是因为里面出现了 $-1$ 和 $+1$ 相消。

要让这一招在大公式上省时间，参数也是天文数字。简化稿里取一个整数 $s$，每个测量值的取值范围是 $s^{2s^4}$ 量级；$s=64$ 时系数已经降到 0.36，但要求变量数至少约 $10^{1.2\times10^8}$，否则直接退回穷举。

两条路线细节完全不同，相同的是都放弃了“每一步都在数真实的解”：中间量可以是负数、可以不是整数，靠最后的相消或插值回到正确答案。按老算法的思路，这样的步骤不会出现，这大概就是 Williams 说的“陌生”的部分。

十、改变了什么，没改变什么

几点展开说一下。

P vs NP 没有变。$2^{o(n)}$ 仍然比任何多项式慢，两篇论文都在开头声明了这一点。

实际的 SAT 求解没有变。工业界的 SAT 求解器每天在处理上百万变量的公式，靠的是实际公式里的结构，和最坏情况的理论界本来就是两回事。这次的算法在可想象的规模上都比穷举慢。

密码学没有被攻破。OpenAI 称检查过，相当有把握不影响现有密码系统⁹。从理论上说，次指数时间也不能随便通过归约传给其他问题：把别的问题改写成 3-SAT 时，变量数往往会从 $n$ 变成 $n^2$ 甚至更多，$2^{o(n^2)}$ 就不再是次指数了，OpenAI 论文里专门指出了这一点²。

理论上的影响是实实在在的。建立在 ETH 和 SETH 上的那 800 多篇论文的条件性结论失去了前提，需要逐个检查能不能改挂到别的假设上，比如没有被推翻的正交向量假说。另一方面，一批问题直接得到了新算法：在 $n$ 个点的图上挑出一批互不相连的点（独立集）、挑出一批两两相连的点（团）等经典问题，都有了 $2^{\delta n}$ 步的算法¹；数地图涂色有多少种方案、数两两配对有多少种方案，也有了次指数算法²。借助 Williams 的“快算法推出电路下界”定理，还能推出一个关于逻辑电路规模的理论新结论。

做数学的方式在变。这是一个被普遍相信的猜想，由模型在没有人类输入的情况下推翻，再由机器检查。审查组发公开信，一部分就是为了讨论 AI 参与研究的规范⁹。

小结

1. SAT 是什么？可满足性问题：一组用“或”连成的子句，能否找到 0/1 取值让它们同时成立。3-SAT 是每句最多 3 个变量的版本。检查答案容易，寻找答案难。
2. 怎么比较快慢？看步数随变量数 $n$ 怎么增长。多项式时间算高效，指数时间不算。SAT 是 NP 完全问题，它有多项式算法当且仅当 P = NP。
3. 几十年做到了多快？穷举要 $2^n$，改进把系数压到了约 0.39，但始终是指数。
4. ETH 说什么？这个系数有一个大于零的下限。它比 P ≠ NP 更强，大量下界结果以它为前提。
5. 新闻属实吗？基本属实：OpenAI 和 Anthropic 用不同方法独立证明了 3-SAT 有确定性的次指数（$2^{o(n)}$）算法，ETH 和 SETH 都被推翻，并有 Lean 机器检查和一份人类简化稿；但还没有经过同行评审。它和 P = NP、实用求解、密码破解都没有关系。
6. 老办法为什么不行？分而治之要枚举切口变量，随机公式的切口正比于 $n$，所以只能改常数。
7. 新办法多做了什么？用八平方恒等式把一对相等检验换成奇偶约束加两个带正负号的项，多放进来的组合正负相消；每一项挑便宜的合并方向，跨节点的比特每轮乘以 $11/12$。
8. 怎么压到零？同样的办法递归使用，系数按 $(11/12)^\ell$ 下降，层数只依赖目标 $\delta$。代价是每层要求的规模爆炸式增长，要 $n>10^{10^8}$ 才比穷举快。
9. OpenAI 的路线呢？给变量加一个参数做变形，在容易算的点上求值，再插值回原问题。两条路的共同点是允许中间量为负、靠相消回到答案。

第七节的恒等式最容易亲手验证。下面这段 Python 按 Anthropic 论文第 2.4 节给出的 $\sigma$，把 4096 种取值全部代进去：

from itertools import product
B3 = list(product((0, 1), repeat=3))

def sigma(p, q):  # 论文 2.4 节的 σ，取 ±1
    s = sum(p[k] * q[j] for k in range(3) for j in range(k, 3))
    s += q[0]*p[1]*p[2] + p[0]*q[1]*p[2] + p[0]*p[1]*q[2]
    return -1 if s % 2 else 1

def xor(*vs):
    return tuple(sum(b) % 2 for b in zip(*vs))

ok = sum(
    2 * (x == v) * (y == u)
    == (xor(x, y, u, v) == (0, 0, 0)) * (sigma(x, y) * sigma(v, u) + sigma(x, u) * sigma(v, y))
    for x, y, u, v in product(B3, repeat=4)
)
print(ok)  # 4096

参考资料