--- title: "指数时间假说被推翻了吗：两篇 AI 论文里的 3-SAT 新算法" description: "2026 年 10 月底，OpenAI 和 Anthropic 先后放出论文，说各自的模型证明了指数时间假说（ETH）是错的。我们从一道聚会邀请的逻辑题讲起：SAT 是什么，怎么比较算法快慢，P、NP 和 NP 完全是什么，几十年的努力为什么只能改底数，ETH 又断言了什么；再核对新闻里哪些属实、哪些被夸大；然后顺着证明往下走：老的分而治之为什么只能改常数，一个两百年前的八平方恒等式怎么用正负相消减少要对上的比特，递归又怎么把指数压到零；最后看 OpenAI 的另一条路，以及这件事改变了什么、没改变什么。" pubDate: 2026-10-28 updatedDate: 2026-10-28 tags: ["计算复杂性", "算法", "3-SAT", "AI", "数学证明", "入门"] hero: "./hero.svg" clc: "TP301" refs: - id: openai title: "The Exponential Time Hypothesis is False" url: https://github.com/openai/math/blob/main/preprints/The-Exponential-Time-Hypothesis-is-False-October-25-2026/paper.pdf author: OpenAI site: GitHub · openai/math date: 2026-10-25 note: "手稿 10 月 17 日，修订 10 月 25 日，10 月 26 日公开。主定理：对每个固定 k，确定性地在 2^O(n·loglog n/√log n) 时间、多项式空间内精确计数 k-CNF 的解。" - id: anthropic title: "A 2^o(n) Time Algorithm for 3-SAT" url: https://hexagonmath.org/2610.00577v1 author: Claude (Anthropic) site: Hexagon 预印本 2610.00577v1 date: 2026-10-27 note: "核心算法 10 月 16 日由内部研究模型在无人类输入下找到，用了 1400 万输出 token。第 1 节给出“只有 n 大于 10^(10^8) 才比穷举快”的估计，附录 E 说明 Lean 里检查了什么、没检查什么。" - id: anthropic-lean title: "anthropics/formal-math: eth" url: https://github.com/anthropics/formal-math/tree/main/eth author: Anthropic site: GitHub date: 2026-10-27 note: "Lean 4 形式化，入口是 `MainResults.lean`。" - id: kintali title: "A simplified proof of ETH is false" url: https://shivakintali.github.io/papers/ETH.pdf author: Shiva Kintali date: 2026-10-26 note: "对 OpenAI 证明主线的 22 页简化讲解，只用稀疏化引理、线性代数和插值；第 2.4 节是本文复现的四变量例子。" - id: techcrunch title: "Frontier AI labs say their models refuted the Exponential Time Hypothesis. What does that mean?" url: https://techcrunch.com/2026/10/27/frontier-ai-labs-say-their-models-refuted-the-exponential-time-hypothesis-what-does-that-mean/ site: TechCrunch date: 2026-10-27 note: "Ryan Williams 的评价（“两三处很陌生”）、审查组与公开信、OpenAI 对密码学影响的说法。" - id: cook title: "The Exponential Time Hypothesis is False" url: https://www.johndcook.com/blog/2026/10/27/eth-false/ author: John D. Cook date: 2026-10-27 note: "汇总三份证明链接；评论区提到 Lean 里形式化的界比论文略弱。" - id: ip01 title: "On the Complexity of k-SAT" url: https://doi.org/10.1006/jcss.2000.1727 author: Russell Impagliazzo, Ramamohan Paturi site: Journal of Computer and System Sciences 62(2) date: "2001" note: "ETH 和 SETH 的出处，会议版 CCC 1999。" - id: ipz01 title: "Which Problems Have Strongly Exponential Complexity?" url: https://doi.org/10.1006/jcss.2001.1774 author: Russell Impagliazzo, Ramamohan Paturi, Francis Zane site: Journal of Computer and System Sciences 63(4) date: "2001" note: "稀疏化引理：任意 3-CNF 可以写成 2^(εn) 个子句数线性的公式之“或”。" - id: schoning title: "A Probabilistic Algorithm for k-SAT and Constraint Satisfaction Problems" url: https://doi.org/10.1109/SFFCS.1999.814612 author: Uwe Schöning site: FOCS 1999 date: "1999" - id: ppsz title: "An Improved Exponential-Time Algorithm for k-SAT" url: https://doi.org/10.1145/1066100.1066101 author: Ramamohan Paturi, Pavel Pudlák, Michael Saks, Francis Zane site: Journal of the ACM 52(3) date: "2005" - id: akk title: "Tensor Network Complexity of Multilinear Maps" url: https://arxiv.org/abs/1712.09630 author: Per Austrin, Petteri Kaski, Kaie Kubjas site: Theory of Computing 18(16) date: "2022" note: "按一棵收缩树计算这类求和的模型里的下界；Anthropic 论文附录 G 据此算出该模型下指数至少约为穷举的 49%。" - id: baez title: "The Octonions" url: https://arxiv.org/abs/math/0105155 author: John C. Baez site: Bulletin of the AMS 39(2) date: "2002" note: "第 1 节讲 Degen 1818 年、Graves 1843 年的八平方恒等式与八元数。" - id: williams19 title: "Some Estimated Likelihoods for Computational Complexity" url: https://doi.org/10.1007/978-3-319-91908-9_2 author: R. Ryan Williams site: Computing and Software Science, LNCS 10000 date: "2019" note: "主观估计 ETH 为真约 70%，SETH 为真约 25%。" --- > 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[^anthropic]。翻译过来是：“我们给出一个在 $2^{o(n)}$ 时间内解决 $n$ 个变量的 3-SAT 的确定性算法，从而推翻了指数时间假说（ETH）。”前一天，OpenAI 也在 GitHub 上放出了一篇标题直接叫《指数时间假说是错的》的论文[^openai]。转到中文社交媒体上，标题很快变成了“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$）把它们连起来： $$ (a \lor b)\land(\lnot a \lor \lnot c)\land(\lnot b \lor c)\land(a \lor c) $$ “一串子句用‘且’连起来”的这种写法叫**合取范式**（CNF，合取就是“且”的意思）。现在问题可以说得很精确了：**给定一个合取范式，有没有一组 0/1 取值，让它整体成立？**这个问题叫**可满足性问题**，英文 Boolean Satisfiability，缩写就是 **SAT**。如果每个子句最多只有 3 个变量，就叫 **3-SAT**。我们的聚会问题每句只有 2 个变量，当然也算 3-SAT 的一个例子。 ### 最笨的办法：挨个试 三个人，每人两种状态，一共 $2\times2\times2=8$ 种方案。全部列出来检查一遍：
8 种邀请方案逐一检查（1 = 来，0 = 不来）
abc哪条要求没满足结果
000第 1 条（A、B 都没来）不行
001第 1 条不行
010第 3 条（B 来了 C 没来）不行
011都满足可以
100都满足可以
101第 2 条（A、C 都来了）不行
110第 3 条不行
111第 2 条不行

检查一个方案只要看四条要求；找出可行方案，这里靠的是把 8 种都试一遍。

表 1 · 聚会问题有两个解：只请 A，或者请 B 和 C
答案是有两种方案：只请 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 增长
nn²n³2ⁿ
101001,0001,024
204008,000约 100 万
502,500125,000约 10¹⁵
10010,0001,000,000约 1.3 × 10³⁰
每秒 10¹² 步的计算机，n = 100 时要算
用时不到 1 微秒1 微秒约 400 亿年
表 2 · n = 10 时三者差不多；n = 100 时多项式还是一眨眼，指数已经比宇宙年龄还长
多项式时间的算法，$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 与 NP 完全 NP 是答案容易检查的问题，里面左边是能高效解决的 P 类，例如排序和最短路线；右边是 NP 完全问题，例如 SAT、3-SAT 和数独。任何 NP 问题都能归约成 SAT。 NP：答案能在多项式时间内检查的问题 都能归约成 P：能高效解决 多项式时间 排序一串数 地图上的最短路线 判断一个数是不是质数 能解决，当然也能检查答案 NP 完全：NP 里最难的 目前没有多项式算法 SAT、3-SAT 数独（推广到 n×n） 排课、地图三着色 任一个有了快算法，整个 NP 都有 P = NP 吗？如果相等，左右两块其实是同一块；绝大多数人相信不相等。 这个问题只问“有没有多项式算法”，不问“最快能多快”，后者正是 ETH 要回答的。
图 1 · NP 里有容易解决的 P 类，也有最难的 NP 完全问题；SAT 是 NP 完全问题的代表
于是就有了那个著名的问题：**P 是否等于 NP？**也就是说，凡是答案容易检查的问题，是不是也都容易解决？这是克雷数学研究所悬赏一百万美元的七个千禧年难题之一，至今没有解决。绝大多数研究者相信 P ≠ NP，也就是 SAT 没有多项式时间算法。 但“没有多项式时间算法”并没有回答**到底要多慢**。下面我们就来看，人们为此努力了几十年，SAT 到底被做到了多快。 ## 三、几十年的努力：只能改底数 ### 比穷举快一点 挨个试的方法叫**穷举**，要 $2^n$ 步。人们找到过不少聪明的办法。1985 年 Monien 和 Speckenmeyer 发现，可以挑一个子句，按其中的变量分情况讨论，很多情况会提前出现矛盾、不必再往下试，这样做到了约 $1.618^n$ 步。1999 年 Schöning 的算法做到了 $(4/3)^n$[^schoning]：先随机给所有变量赋值，哪个子句不满足，就随机翻转它里面的一个变量，反复多次。它是一个**随机算法**，允许“抛硬币”，以极高的概率给出正确答案；与之相对，每一步都确定、同样的输入一定得到同样结果的叫**确定性算法**。PPSZ 算法[^ppsz]经过多年改进，在 2014 年降到 $1.308^n$。 ### 换成以 2 为底来比较 这些底数看起来五花八门，换成以 2 为底就能放在一起比。用对数，$1.308 = 2^{\log_2 1.308} \approx 2^{0.388}$，所以 $$ 1.308^n = 2^{0.388n} $$ 这相当于说：用 PPSZ 解 $n$ 个变量的问题，和穷举 $0.388n$ 个变量一样难。**每一次进步，都只是把指数里 $n$ 前面的系数往下压一点**，从 1 压到 0.69，再到 0.42、0.39。
3-SAT 最坏情况算法的底数 从穷举的 2 的 n 次方到 2014 年的 1.308 的 n 次方，几十年的进步都是把底数往下压，指数里 n 前面的系数始终大于零；2026 年的两篇论文把这个系数压到任意小。 每多一个变量，最坏时间乘以几 条形长度 = log₂(底数)，即 2 的多少 n 次方 穷举所有组合 2ⁿ ≈ 2^1.00n Monien 等 1985 · 确定性 1.618ⁿ ≈ 2^0.69n Schöning 1999 · 随机 1.334ⁿ ≈ 2^0.42n 确定性纪录 2018 1.328ⁿ ≈ 2^0.41n PPSZ / Hertli 2014 · 随机 1.308ⁿ ≈ 2^0.39n 2026 年的两篇论文 确定性 · 计数 2^δn，δ 可以任意小 前五行的系数都停在 0.38 以上；虚线框表示系数不再有下限，但这只在 n 大到天文数字时才兑现。
图 2 · 几十年的改进都在压底数，系数从 1 降到约 0.39；新结果说这个系数没有大于零的下限
时间仍然是“每多一个变量就乘上一个固定倍数”，只是倍数从 2 变成了 1.3。按 1.308 倍算，$n=1000$ 时步数约 $10^{117}$，照样算不完。**这个系数能不能一直压下去，压到任意小？还是存在一个大于零的下限？** ## 四、指数时间假说说的是什么 ### 假说的内容 1999 年，Russell Impagliazzo 和 Ramamohan Paturi 把大家的直觉写成了一个明确的猜想[^ip01]，叫**指数时间假说**（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。
几条复杂性假说之间的蕴含关系 SETH 蕴含 ETH，ETH 蕴含 P 不等于 NP，SETH 还蕴含正交向量假说。新结果推翻 ETH，于是 SETH 也被推翻；P 不等于 NP 和正交向量假说不受影响。 从强到弱：箭头表示“左边成立，则右边成立” 蕴含 蕴含 蕴含 SETH 强指数时间假说 k 越大，k-SAT 越接近 2ⁿ 随 ETH 一起被推翻 ETH 指数时间假说 1999 3-SAT 至少要 2^δn，δ>0 被推翻 P ≠ NP 1971 年提出 3-SAT 没有多项式算法 不受影响，仍未解决 OV 正交向量假说 找内积为 0 的一对没捷径 不受影响 右边的被推翻，左边的跟着倒：ETH 错了，SETH 也就错了。 左边倒了，右边不受牵连：P ≠ NP 和 OV 都还站着。
图 3 · 新结果推翻了 ETH，也就连带推翻了更强的 SETH；更弱的 P ≠ NP 和旁支的 OV 假说不受影响
这些假说之所以重要，是因为大量“下界”结果建立在它们之上。**下界**是指“某个问题不可能比多快更快”。直接证明下界极难，研究者通常绕一个弯：先证明“如果问题 X 有某种快算法，那么把 3-SAT 归约到 X，3-SAT 就会有次指数算法”，然后写下“除非 ETH 不成立，X 就没有这种快算法”。Anthropic 的论文里用 Claude 做了一次文献检索，找到 800 多篇论文至少有一个结果只在 ETH 或比它更强的假设下成立[^anthropic]。 并不是所有人都坚信这些假说。2019 年 Ryan Williams 给过一个主观估计：ETH 为真的可能性约 70%，SETH 约 25%[^williams19]。 **那么这一次，是谁、用什么推翻了它，证据有多硬？** ## 五、新闻核实：发生了什么 ### 时间线 把几份原始材料对一遍，事情的经过是这样的： - **10 月 16 日**，OpenAI 和 Anthropic 的内部模型各自得到了证明。Anthropic 说核心算法是一个内部研究模型在没有人类输入的情况下找到的，用了 1400 万个输出 token（模型输出文字的计数单位，大致一个 token 是一个汉字或半个英文单词）[^anthropic]。 - **10 月 17 日**，OpenAI 把证明**形式化**到了 Lean，也就是翻译成计算机能逐步检查的形式（下文细说），10 月 25 日修订论文，26 日公开[^openai]。 - **10 月 26 日**，Shiva Kintali 发了一份 22 页的简化讲解，只用多项式、解方程这类基础数学，重写了 OpenAI 证明的主线[^kintali]。 - **10 月 27 日**，Anthropic 在 Hexagon 预印本平台发出论文，并公开 Lean 证明[^anthropic-lean]。 - ETH 的提出者 Impagliazzo、Paturi 和 MIT 的 Ryan Williams 牵头组成审查组。他们在公开信里写明：参与审查不代表认证这个结论。Williams 对 TechCrunch 说，证明里有些部分看起来很常规，但有“两三处”非常陌生[^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 个文件[^anthropic]。 但机器只能检查“从这些定义推出这个结论”。**定义本身是不是真的表达了 ETH，机器管不了。**Anthropic 在附录 E 里写得很直白：Lean 证明是 AI 写的，由同一模型的其他实例审阅，写作时没有已知的人检查过。OpenAI 一边，Lean 里形式化的运行时间界比论文正文略弱，但仍然是次指数的[^cook]。 所以合理的判断是：两家用**不同的方法**独立得到同一个结论，各自有机器检查，又有一位人类研究者把其中一份改写成了可以逐行读懂的证明，这比通常“某某猜想被推翻”的新闻要可靠得多；但它还没有经过**同行评审**（投稿后由同领域专家审稿），审查组也还没有给出结论。 ### 哪些说法被夸大了
常见说法与原文对照
说法原文怎么说判断
AI 推翻了指数时间假说两篇论文都给出 3-SAT 的确定性次指数算法，有 Lean 检查，审查进行中基本属实
被推翻的只是某个变体推翻的是 ETH 的标准形式，更强的 SETH 随之一起倒下不对
P = NP 更近了Anthropic 原文：结果不直接涉及 P vs NP不对
NP 难题从此能快速求解只有 n 大于约 10108 时才比穷举快，原文明确说它对实际求解公式没有帮助不对
密码学要变天OpenAI 称检查后相当有把握不影响现有密码系统没有依据
三十年难题ETH 1999 年提出，到现在 27 年略有夸张

原文出处见文末的 OpenAI、Anthropic 论文和 TechCrunch 报道。

表 3 · 结论本身基本属实，转述时附加的推论大多不成立
既然结论大概率成立，真正有意思的问题就来了：**几十年只能改底数，新算法到底多做了什么？**我们先看老办法卡在哪里。 ## 六、分而治之的极限 ### 把公式切成两半 两篇论文的算法都是在数解的个数，我们也从“怎么数”说起。数解的个数有一个天然的分而治之思路。如果一个公式的变量能分成两组，每个子句只用到其中一组，那么两组各自数出解的个数再相乘就行。比如聚会再多请两位朋友 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 公式，用一种近似方法找尽量小的**均衡切口**（切开后两半的变量数相等）。作为对照，再生成一种“链状”公式，它的每个子句只用三个编号相邻的变量。结果如下：
均衡切口的大小（启发式能找到的最小值）
变量数 n链状公式（m = 4n）随机 3-CNF（m = 2n）随机公式切口 / n
1002400.40
2002810.41
40021590.40
80023370.42

m 是子句数。脚本见 /mnt/project-files/eth-research/experiment/e3_separator.py。

表 4 · 链状公式的切口始终是 2，随机公式的切口始终是 n 的四成左右
对比很鲜明。链状公式的子句只连相邻的变量，从中间一刀切下去只有 2 个变量跨着两边，不管 $n$ 多大都是 2。随机公式就不一样了，切口始终在 $0.4n$ 左右，不随 $n$ 变小。近似方法找到的不一定是最小的，但理论上早就知道这不是方法的问题。把每个变量画成一个点，在同一个子句里出现过的变量之间连线，就得到一张**图**（这里的“图”指点和连线组成的结构）。随机公式对应的图是一种**扩张图**：从中任取一大块点，它和外面的连线都很多。所以不管怎么切成两个大小相当的部分，跨过去的变量都正比于 $n$。
分而治之要枚举切口变量 左边是链状公式，变量排成一行，从中间切开只有两个变量同时连着两半；右边是随机公式，切开后大量变量同时连着两半，这些都要枚举。 链状公式：切口只有 2 个变量 随机公式：切口随 n 线性增长 左半 右半 固定强调色的 2 个变量（4 种取值）， 两半就互不相干，可以各数各的再相乘。 实验：n = 100 … 800，切口恒为 2 强调色的变量都连着两半，都得枚举。 实验（m = 2n）：切口约 0.4n，不随 n 变小
图 4 · 分而治之的代价是 2 的“切口变量数”次方：链状公式切口恒定，随机公式无论怎么切都有一大截
切口正比于 $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$ 成立： $$ 2\,[x=v]\,[y=u] = [x\oplus y\oplus u\oplus v = 0]\,\bigl(\sigma(x,y)\,\sigma(v,u) + \sigma(x,u)\,\sigma(v,y)\bigr) $$ 其中 $\oplus$ 是**按位异或**：两个串逐位比较，相同得 0、不同得 1，比如 `101` $\oplus$ `011` = `110`。四个串异或为零，就是每一位上四个串的 1 的个数都是偶数。$\sigma$ 是一个只取 $+1$ 和 $-1$ 的函数，论文给出了它的具体写法（见文末代码）。 这个恒等式的来历很古老。先看一个熟悉的等式： $$ (a^2+b^2)(c^2+d^2) = (ac-bd)^2 + (ad+bc)^2 $$ 两个“两数平方和”相乘，结果还是两数平方和，它对应复数的模可以相乘。1818 年 Degen 发现，把“两个数”换成“八个数”同样成立，这就是**八平方恒等式**；1843 年 Graves 重新发现了它，背后是一种由八个实数组成的“数”，叫八元数[^baez]。Anthropic 在附录 H 里讲了模型怎样在寻找分解方式的过程中走到这个恒等式，上面的式子就是从它推出来的。Anthropic 在附录 H 里讲了模型怎样在搜索分解方式的过程中走到这个恒等式。 这个式子一共涉及 12 个比特，可以直接验证。我们把 $4096$ 种取值全部代进去算了一遍，全部成立。更有意思的是它为什么成立：
恒等式两边逐项比较（x, y, u, v 各 3 比特）
取值左边 2[x=v][y=u]行选择项列选择项组合数
x = v 且 y = u2+1+164
异或为零，但不相等0一个 +1、一个 −1，相消448
异或不为零0003584
两个具体例子
101, 011, 011, 1012+1+1相等
101, 011, 110, 0000+1−1相消

4096 种取值全部满足恒等式。脚本见 /mnt/project-files/eth-research/experiment/e1_eight_square.py。

表 5 · 奇偶约束比相等检验宽松得多，多放进来的 448 种组合靠正负号两两抵消
右边的方括号只要求四个串异或为零，我们把这个条件叫**奇偶约束**。满足它的组合有 512 种，其中真正满足 $x=v$、$y=u$ 的只有 64 种。剩下 448 种里，括号中两项总是一个 $+1$ 一个 $-1$，恰好抵消。**原来的“相等检验”被换成了一个更宽松的奇偶约束，多放进来的组合靠正负号自己消掉。** ### 换了之后省在哪里 把右边乘开，得到两项。论文把含 $\sigma(x,y)\sigma(v,u)$ 的叫**行选择**，含 $\sigma(x,u)\sigma(v,y)$ 的叫**列选择**。
一个矩形在恒等式前后的代价 左：矩形四角 a、a′、b、b′ 分别持有 x、y、u、v，两条对角边要求 x 等于 v、y 等于 u，按行合并要 6 比特。中：行选择项只要两行在 x 异或 y 上一致，3 比特。右：列选择项按行合并仍要 6 比特，按列合并只要 3 比特。 原来：两条对角边 行选择项 列选择项 a · x a′ · y b · u b′ · v a–b′ 要求 x = v，a′–b 要求 y = u 合并行 6 比特 · 合并列 6 比特 上一行 x, y 下一行 u, v x⊕y = u⊕v 只对上 3 比特 因子 σ(x,y)·σ(v,u)，取 ±1 合并行 3 比特 · 合并列 6 比特 上一行 x, y 下一行 u, v x、y 全部 要对上 6 比特 因子 σ(x,u)·σ(v,y)，取 ±1 合并行 6 比特 · 合并列 3 比特 恒等式 2·[x=v]·[y=u] = [x⊕y⊕u⊕v=0]·(σ(x,y)σ(v,u) + σ(x,u)σ(v,y)) 4096 种取值全部成立
图 5 · 恒等式把一个矩形拆成两项，每一项都有一个只要 3 比特的合并方向，行、列代价之和从 12 降到 9
看行选择这一项：按行合并时，上一行手里有 $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 研究过“按一个固定的顺序逐步合并求和”这类算法，并证明了它们不可能太快[^akk]，Anthropic 据此算出，这类算法的指数至少要有穷举的 49% 左右。新算法不受这个限制，因为它把一个和拆成许多带正负号的和，每个和按不同的方式合并。 一轮只省 $1/12$，**怎么从“省一点”变成“省到任意多”？** ## 八、递归：把指数压到零 一轮合并完，再按比特数重新分组、补齐，得到的正好又是一个“节点数更少、每对节点之间一条边”的同类问题，只是节点上的值变成了任意整数。于是可以对它再用一次同样的办法，这种“对缩小后的同类问题再用同一个办法”的做法叫**递归**。论文把每一层的系数写成一个数列的递推式： $$ e_0 = 1,\qquad e_\ell = \Bigl(\tfrac{11}{12} + \tfrac{2}{K_{\ell-1}}\Bigr)e_{\ell-1} + \tfrac{5}{K_{\ell-1}} $$ 其中 $K_\ell$ 是第 $\ell$ 层要求的节点数，$K_0 = 64$，$K_\ell = 9K_{\ell-1}^{16}$。时间大约是 $2^{e_\ell m}$，$m$ 是子句数。我们按这个递推式算了 30 层：
每加一层递归，指数乘以约 11/12 横轴是递归层数，纵轴是运行时间 2 的 e 乘 m 次方里的系数 e。第 1 层因为节点太少略高于 1，从第 2 层起按 11/12 的比例下降，约第 13 层低于 PPSZ 的 0.39，第 28 层左右低于 0.1。 递归层数与指数系数 e（时间约为 2^(e·m)） 0 0.5 1 0 5 10 15 20 25 30 递归层数 穷举 e = 1 PPSZ 1.308ⁿ ≈ 2^0.39n 第 1 层 e≈1.03，K≈10^30 第 2 层 e≈0.94，K≈10^479 第 28 层 e≈0.10 K 是这一层要求的节点数：第 1 层就要约 10^30 个，层数越多要求越是天文数字。
图 6 · 递归的每一层把指数系数乘上约 11/12，层数够多就能低于任何给定的 δ，代价是对输入规模的要求爆炸式增长
第 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 的**稀疏化引理**[^ipz01]，可以把任意公式拆成若干个子句数不超过变量数固定倍数的公式，于是 $2^{\delta m}$ 也就变成了 $2^{\delta n}$。这就推翻了 ETH。 但图里的 $K$ 同样值得看：第 1 层就要求约 $10^{30}$ 个节点，第 2 层约 $10^{479}$ 个。输入不够大，这些层根本搭不起来。Anthropic 自己估计：对子句数是变量数 5 倍的公式，要 $n > 10^{10000}$ 才比穷举快；只看 $n$ 的那个界，要 $n > 10^{10^8}$[^anthropic]。这种只在天文规模上才兑现的算法，圈内叫“银河算法”。 即使不管常数，$o(n)$ 本身也收缩得极慢。两篇论文的指数是 $n\log\log n/\sqrt{\log n}$ 的量级，我们把它除以 $n$（把前面省略的常数倍数当成 1，这已经是对算法很宽容的假设）：
次指数的指数除以 n：log₂log₂n / √log₂n
变量数 n比值相当于
10³1.05比穷举还慢
10⁶0.97和穷举差不多
10¹²0.84仍不如 PPSZ 的 0.39
10¹⁰⁰0.46
10¹⁰⁰⁰⁰0.08终于明显低于老算法

大 O 里的常数取 1，真实常数更大。脚本见 /mnt/project-files/eth-research/experiment/e4_numbers.py。

表 6 · 即使不管常数，o(n) 也要到 n 成为天文数字才比老算法省
到 $n=10^6$ 时这个比值还有 0.97；要到 $10^{100}$ 才降到一半。**$2^{o(n)}$ 在数学上比任何 $2^{\delta n}$ 都快，在现实里和穷举没有区别。** **OpenAI 的证明也是这条路吗？** ## 九、另一条路：变形，再插值 OpenAI 的证明走的是另一条路线。Kintali 的简化稿把它整理成了只用多项式和解方程的版本[^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$：
T = 1 时按测量值 y = x₃ + x₄ 分组求和
测量值 y第一组（x₁, x₂）的和第二组中 x₃ + x₄ = y 的个数乘积
0212
1224
2010
从容易算的点回到 T = 0
H(1)2 + 4 + 0 = 6，不是解数
H(1 + z)6 − 4z − z²
代入 z = −16 + 4 − 1 = 9 = 解数

与穷举结果一致。脚本见 /mnt/project-files/eth-research/experiment/e2_kintali_toy.py。

表 7 · 在变形后的点上分组求和，得到的不是解数；用插值退回 T = 0 才得到 9
这里 $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没变次指数仍比任何多项式慢
实际 SAT 求解没变要 n 大于约 10 的 1 亿次方才比穷举快
现有密码系统没变次指数时间不能随意通过归约传递；OpenAI 称已检查
以 ETH、SETH 为前提的下界失去前提800 多篇论文需要逐个检查，能改挂到 OV 等假设上的保留
图上的独立集、团等问题有了新算法n 个点上 2^δn 步，对任意 δ > 0
电路规模的理论下界有了新结论某类问题无法用线性规模的逻辑电路计算
表 8 · 改变的是理论上的地图，不是实际的计算
几点展开说一下。 **P vs NP 没有变。**$2^{o(n)}$ 仍然比任何多项式慢，两篇论文都在开头声明了这一点。 **实际的 SAT 求解没有变。**工业界的 SAT 求解器每天在处理上百万变量的公式，靠的是实际公式里的结构，和最坏情况的理论界本来就是两回事。这次的算法在可想象的规模上都比穷举慢。 **密码学没有被攻破。**OpenAI 称检查过，相当有把握不影响现有密码系统[^techcrunch]。从理论上说，次指数时间也不能随便通过归约传给其他问题：把别的问题改写成 3-SAT 时，变量数往往会从 $n$ 变成 $n^2$ 甚至更多，$2^{o(n^2)}$ 就不再是次指数了，OpenAI 论文里专门指出了这一点[^openai]。 **理论上的影响是实实在在的。**建立在 ETH 和 SETH 上的那 800 多篇论文的条件性结论失去了前提，需要逐个检查能不能改挂到别的假设上，比如没有被推翻的正交向量假说。另一方面，一批问题直接得到了新算法：在 $n$ 个点的图上挑出一批互不相连的点（独立集）、挑出一批两两相连的点（团）等经典问题，都有了 $2^{\delta n}$ 步的算法[^anthropic]；数地图涂色有多少种方案、数两两配对有多少种方案，也有了次指数算法[^openai]。借助 Williams 的“快算法推出电路下界”定理，还能推出一个关于逻辑电路规模的理论新结论。 **做数学的方式在变。**这是一个被普遍相信的猜想，由模型在没有人类输入的情况下推翻，再由机器检查。审查组发公开信，一部分就是为了讨论 AI 参与研究的规范[^techcrunch]。 ## 小结 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 种取值全部代进去： ```python 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 ``` ## 参考资料