3SUM 与全源最短路的真正更快的做法

zhouhuanyi · 2026-10-06 23:51:58 · 算法·理论

书接上文一个假的全源最短路更快做法：全源最短路的更快做法，以及对于贡献定位没有那么准确的技术报告：O(n^{2-eps}) 3sum。

二次与三次屏障同时失守

一场由 AI 发现触发的算法革命

3SUM、APSP、Exact Triangle，以及经由归约连接的 MinConv，在同一条算法链上接连跨过了固定指数的障碍。

这件事的震撼程度，不能只用小数点后的几位变化衡量。细粒度复杂性长期研究的核心命题之一，就是这些问题是否存在任何固定的 \varepsilon>0，使二次时间降为 n^{2-\varepsilon}、三次时间降为 n^{3-\varepsilon}。这篇论文给出了肯定答案，并通过既有归约，把突破传送到图算法、序列优化、背包、部分计算几何问题与数据结构。arxiv.org

一、论文是谁写的，AI 究竟做了什么

论文标题：
Truly Subquadratic 3SUM and Truly Subcubic APSP via Triangles in Sparse Lopsided Graphs

作者：

• Josh Alman
• Virginia Vassilevska Williams

论文署名列出的单位分别为 Columbia University 与 MIT。

固定版本与地址：

• arXiv:2610.06783v1
• 论文完整 HTML
• 论文原始 PDF

本文分析的是 2026 年 10 月 5 日提交的 v1 预印本。论文摘要给出的整数确定性界为：

其中，定理 22 将 APSP 的指数写得更细，为 2.99942。实数版本则给出 Las Vegas 期望时间：

实数上的运算仅需加法、减法和比较。arxiv.org

AI 发现过程：从密码构造转向击穿其困难性基础

按照论文末尾 Acknowledgments and Methodology 的公开声明，最初的任务来自密码学：Anthropic 的一位员工让内部研究版 Claude 检查、改进基于 Zero-k-Clique 平均情形困难性的密码构造。

模型转而发展出更快的算法，先处理平均情形，再推进到最坏情形。作者记录，这次会话使用了 1600 万输出 token，期间没有人类继续输入。这一表述指该次探索会话内部；问题设置与后续研究仍有人类参与。arxiv.org

Anthropic 在 2026 年 9 月将算法分享给两位作者。被分享的核心基本对应论文第 2 节的薄矩阵稀疏输出算法，原始参数和表述有所不同。作者随后理解、简化、加强并扩展算法，组织既有归约，发展出在线数据结构版本及 Hinted OMv 后果，并承担论文内容的全部责任。arxiv.org

因此，AI 的贡献可以准确地写成：

Claude 发现了推翻核心猜想的算法；人类研究者将这一发现发展为一套清晰、可扩展、与既有复杂性理论连接起来的数学成果。

论文还报告，在写作完成后，内部研究模型使用 Lean 4 与 Mathlib 形式化验证了 Exact Triangle 的定理 19、3SUM／Min-Plus Product／APSP 的定理 22，以及推论 39 的 Zero-Weight k-Clique 情形及其依赖。公开目录为 anthropics/formal-math/3sum-apsp。这份清单有明确范围；下面额外推导的应用不能一并宣称已经获得同样的形式化认证。arxiv.org

二、复杂度刷新总表

读表约定

完整报告将结果拆为 76 行；这里将相关问题合并展示，覆盖同一组已核验的结果及直接推论。

• D：确定性。
• LV：Las Vegas，答案始终正确，时间为期望时间。
• MC：以高概率输出正确答案。
• 默认整数的绝对值为输入规模的固定次多项式；实数版本单独标明。
• 各行的 \delta>0 可以不同，不能默认相等。
• “二次型／三次型”表示此次跨越的指数台阶，省略此前的对数或次多项式节省。

使用四个缩写：

其中，T_{\mathrm I} 来自论文脚注 10 提示的逐边 Exact Triangle 路线，比摘要中经全局检测得到的界更强；两个卷积界再由矩阵到卷积的归约得到。后文会把这两步展开。arxiv.org

这张表来自论文主定理、既有正向归约和报告中展开的组合推论。APSP 类、计数类、MinConv／背包类分别依赖相应的路径—矩阵归约、检测—计数归约和卷积归约；它们的随机性与指数损失必须逐项保留。arxiv.org

树编辑距离采用保持矩阵乘法指数的归约；近似 Subset Sum 使用 \widetilde O(n+T(1/\epsilon)) 的接口；MonoConvolution 和 Polyhedral 3SUM 则来自各自的专门联系。arxiv.org

这张表最需要防止的误读，是把“3SUM-hard”直接变成“现在有更快算法”。 若已知的只有

更快的 3SUM 并不自动给出更快的 P。因此，一般平面三点共线，以及许多只有单向困难性归约的几何、动态问题，没有被冒进地塞进新算法表。论文也明确指出，这些问题仍然开放。arxiv.org

三、算法真正突破的地方：只算薄矩阵中需要的位置

整篇论文的核心任务是：

给定位置集合 W，只输出

这里是普通加乘矩阵乘法。输入可以稠密，完整输出也可以稠密；稀疏的是我们请求的输出位置。

当

新算法的时间为

这比写出整个 N\times N 乘积所需的 N^2 次输出还少。它也比逐个算内积的 |W|D 快一个多项式因子。arxiv.org

这个任务与三角形的关系非常直接。若 X,Y 是三部图两侧的邻接矩阵，那么

再把 (a,b)\in W 视作第三条边，这个矩阵元素就是经过该边的三角形数量。

下面的箭头表示算法成果的传播方向：

flowchart TD
    A["十乘法恒等式与递归剪枝"] --> B["薄矩阵的稀疏输出"]
    B --> C["整数逐边 Exact Triangle"]
    B --> D["实数比较计数"]
    B --> J["集合相交与 Hinted OMv"]
    C --> E["3SUM"]
    C --> F["APSP 与 min-plus 矩阵"]
    D --> E
    D --> F
    F --> G["min-plus 卷积"]
    F --> I["图指标与树编辑距离"]
    G --> H["序列优化与背包"]

3.1 先找到一种适合省略输出的代数分解

Schönhage 的经典恒等式，把九个外积项 x_i y_j 和一个四项内积

放进一个十次乘法的构造中。直接分别计算需要 9+4=13 次乘法；十次乘法构造的外积部分会带误差，需要后续结构将其精确消去。

令

计算九项

以及第十项

由于 \widehat p 每列和为零、\widehat q 每行和为零，

所以内积是精确的。

更关键的是输出依赖关系：

• 一个外积输出只依赖某一个 P_{ij}；
• 内积输出依赖全部十项；
• 外积误差中的每个单项式，都至少含有一个内积类型的输入变量。

论文利用的正是这三种结构。arxiv.org

3.2 递归之后，误差为什么会完全消失

把恒等式递归 L 层，只保留左右输入各有恰好 m 层使用 inner 变量的部分。记

每选一个大小为 m 的层集合 Q，就得到一个

的薄矩阵乘积。整棵递归树同时装入 K 个这样的独立乘积。

固定一个所需输出，它的 inner 层集合也是 Q。

在最终解码的多线性系数中，Q 内的每一层都要求左右输入为 inner。这已经用完了输入允许的全部 m 个 inner 层。因此，Q 外只能使用 outer 输入。

而误差恰好要求在某个 outer 输出层出现 inner 输入。于是误差无法进入所需输出，全部被精确排除。

算法没有使用数值近似，也没有把误差当成“小量”丢掉。它通过固定层数，让误差在代数结构上无处进入。

3.3 真正决定速度的是“叶子的并集”

递归树有 10^L 个乘法叶子。算法按需求递归：只有能够影响所需输出的分支才执行，同一个叶子被多个输出需要时只算一次。

设一个小块请求的输出集合为 U。将叶子按阶数 d 分类，可以得到两种上界：

是一个输出依赖的第 d 阶叶子数量；

是整棵树里第 d 阶叶子的总数量。

因此：

这条式子是突破的组合核心：某些叶子虽然会被很多输出使用，但它们在全局的总数很少；另一些叶子数量多，但一个输出只需要其中很少的一部分。

取 L=19m，则

以 m/9 为分界，低阶按 |U|\alpha_d 收费，高阶按 \beta_d 收费，得到

对所有小块求和，再使用 |W|\le N^2/\sqrt D，便得到少于 N^2 的总工作量。

输入编码同样需要控制。论文把矩阵组织成行带、列带，使同一条带的编码在许多小乘积之间复用，编码总费用为

稀疏输出、叶子共享、编码复用，三者共同兑现了复杂度节省。arxiv.org

3.4 在线版本为什么还能更强

如果查询位置逐个到来，不能提前知道要保留哪些递归分支。论文于是预存高度共享的叶子部分和，称为 boxes。

高阶叶子按照 inner 位置中最靠右的 t 个非 P_0 项来划分，其余适当位置用星号表示。星号展开成全部十项，利用动态规划计算每个 box 的和。一次查询只读取少量低阶叶子和少量 box。

取

并吸收对数因子，得到：

因为 0.5-0.437=0.063，处理 N^2/\sqrt D 个查询仍在同一预算内。

更一般的参数分析把薄维度范围扩展到

这个 0.1204 是当前恒等式和编码分析给出的参数界，后续仍有改进空间。arxiv.org

四、怎样把这个矩阵算法变成真正亚三次的 Exact Triangle

给定三部加权图，要寻找

整数权重允许先模一个素数 p 筛选候选。但模零可能是假阳性，所以算法必须同时控制：

1. 产生多少个薄矩阵实例；
2. 最后核查多少个假阳性。

4.1 素数选择也能确定性完成

取 p 约为 \sqrt D。记 F(p) 为模 p 等于零、原整数和却不为零的三角形数量。

算法通过模 p 的多项式矩阵乘法，计算每个候选素数下的模零三角形数量。真正零三角形的数量对所有 p 都相同，因此最小化这个总数就等价于最小化假阳性数量，无须预先知道真正零三角形有多少个。

可以确定性地选到满足

的素数。

随后将顶点与剩余类拆分成偏斜稀疏实例，交给薄矩阵算法，最后对候选见证检查原整数权和。arxiv.org

4.2 0.00175 是怎样算出来的

设切分参数为 g。实例求解的成本约为

假阳性核查成本约为

令

两项平衡。再取

便得到

从而：

这解释了核心指数的每一层来源：薄矩阵节省 0.063，平衡真假候选损失一半，再通过 D=n^{1/18} 换算成原问题规模。

五、3SUM 与 APSP 的指数怎样落地

5.1 3SUM：保留一半节省

已知确定性归约把规模 n 的整数 3SUM，变成约 n^{1/2+o(1)} 个规模 n^{1/2+o(1)} 的 Exact Triangle 实例。因此：

这里的 o(1) 不能随意删除。arxiv.org

5.2 APSP：保留逐边输出，才能避免多损失一次指数

经全局检测版 Exact Triangle 的归约，APSP 只保留三分之一节省：

对应定理中的 O(n^{2.99942})。

但作者脚注 10 指出，同一个算法实际上可以在相同主导时间内回答每条边是否有零权三角形。利用这一更丰富的接口，矩阵乘法可以保留全部节省。arxiv.org

下面是一个具体的恢复办法。

先将矩阵项平移为非负整数。定义

如果已经知道 C_h，加入下一位时必有

每一位只需两次逐边 Exact Triangle，询问是否存在 k 满足

以及右端加 1 的等式。

第一式有解，取第一个候选；否则第二式有解，取第二个；都没有，答案必为第三个。

整个过程只有 O(\log U) 轮，矩阵规模始终不变，于是得到：

这一逐位推导也说明，算法没有把“等式检测”未经证明地当成“不等式判定”。

5.3 实数版本：通过比较计数绕开整数取模

任意实数不能直接套用模素数哈希。实数路线采用 Fredman 技巧：

右边把行相关信息与列相关信息分开。把带颜色的比较元素排序、分块后：

• 不同块之间的比较由一个普通整数矩阵乘积计数；
• 同块内的比较直接核查。

矩阵项只是元素个数，所以原始数据即使是任意实数，核心薄矩阵步骤仍满足整数定理的条件。

取 d=n^{1/40} 后，比较计数的预算最终给出

的 3SUM，以及

的 Min-Plus Product 和 APSP。随机性来自前驱／后继搜索中的抽样，答案始终正确，因此是 Las Vegas。arxiv.org

六、从 Min-Plus 矩阵到卷积，再到背包

这条传播链最值得展开，因为它会直接改变许多动态规划的通用上界。

6.1 为什么矩阵快了 \eta，卷积就快了 \eta/2

需要计算全部

取 h=\lceil\sqrt n\rceil。对每个余数 r\in\{0,\ldots,h-1\}，构造

越界位置设为适当的哨兵。计算 C_r=A\star B_r，再取

因为

所有合法分拆都准确落在相应位置。

这样共有 O(\sqrt n) 个边长 O(\sqrt n) 的矩阵乘法。因此，如果方阵乘法为 \widetilde O(s^{3-\eta})，则

这正是矩阵—卷积关系在此处的具体展开。arxiv.org

代入两种矩阵算法：

这些都是完整卷积输出，不是只回答一个位置。

6.2 无界背包：重复平方

令容量为 t，物品重量为正整数。建立精确重量数组：

缺失状态记为不可达。

一次 Max-Plus 自卷积得到至多两件物品的答案，再平方得到至多四件、八件、十六件……由于重量至少为 1，任何可行解最多使用 t 件物品，故 O(\log t) 次截断平方足够。

最后做前缀最大，得到全部容量的最优值：

或

6.3 0/1 与有界背包：必须保留外层随机性

0/1 背包不能重复平方同一个数组，否则同一物品会被重复使用。既有归约通过重量分层、随机分组和颜色编码，将总卷积工作压到

代入较快的卷积算法，得到

即使内部卷积始终正确，外层颜色编码仍可能漏掉最优方案，因此不能把整个算法标成 LV。arxiv.org

有界背包先将每类重数截断到 \lfloor t/w_i\rfloor，再用标准二进制分组转成 O(n\log t) 个 0/1 物品，得到同样的 MC 上界。

这里的参数是容量 t，不能替换成最大单件重量 w_{\max}。这些结果也仍是伪多项式算法；它们不意味着精确背包有了强多项式算法。

6.4 更多序列动态规划如何跟着变化

几个典型例子：

• 每种长度的最大区间和是 \max_i(P_{i+k}-P_i)，可用前缀和的反向卷积统一求出。
• 超可加性、次可加性是一次自卷积后的逐项比较。
• Tree Sparsity 的预算分配是卷积；已有树分解归约控制全树的总合并成本。
• 多个序列连乘可以使用平衡合并树。若总输入长度为 L，每一层满足 \sum_v s_v\le L，所以对固定 \alpha>1，有 \sum_v s_v^\alpha\le L^\alpha，总成本为 \widetilde O(L^\alpha)。

最后一条覆盖不等长序列，也解释了为什么不能简单把“合并次数”乘上“全长卷积成本”。

七、额外推导：计数甚至打开了中位数卷积

原论文的影响不止于“求一个最优值”。既有研究证明，整数 Exact Triangle、Min-Plus Product、3SUM 与适当的计数版本之间存在细粒度归约；结合去随机化结果，可以得到确定性的整数逐输出计数算法。arxiv.org

报告进一步展开了下面这条链：

这些扩展在报告中明确标为组合推论，没有冒充原论文逐条陈述的定理。

7.1 等式计数怎样变成不等式计数

对非负整数定义

因为

符号变化只有两种：

对全部位求和，左端望远镜消去为 [a+b<c]。

因此，不等式计数可转换为 O(\log U) 次带位掩码的等式计数。这里的负项不可省略：它不是按不同位作互不相交分类，而是有符号求和。

保留下标编码后，就能同时得到每个 k 的

并允许每个输出使用不同阈值。

7.2 并行二分求每个输出的指定秩

每个反对角线维护自己的二分区间，一轮中使用各自的中点作为阈值。一次全输出阈值计数，就足以更新所有位置的区间。

所以每条反对角线的一个指定秩，包括中位数，只需再乘 O(\log U) 因子：

此前通用的中位数／指定秩卷积加速仍是对数因子级；这里的结论限于多项式大小整数输入。tmc.web.engr.illinois.edu

7.3 为什么知道中位数后，还要计算一个加权和

记该反对角线的多重集为 D_k，中位数为 z_k，并令

则

阈值以下的和值 S_{<,k}，可以把输入值按二进制位加掩码，再做阈值计数恢复，仍只增加多对数因子。

这就补齐了“中位数值”到“最小 \ell_1 代价”的完整算法。再接上项链的圆周展开关系，即得到多项式整数网格上的真正亚二次 \ell_1 项链对齐。实数 \ell_\infty 项链对齐则直接由 Min／Max-Plus 卷积得到。arxiv.org

八、为什么无权 APSP、Clique 和在线问题也受到冲击

有向无权 APSP：替换原算法的瓶颈

一般 APSP 的 n^{2.998} 显然不足以直接改善约 n^{2.5275} 的无权算法。真正的连接来自 Zwick 算法在瓶颈处的

Min-Plus 乘积。

将其切成 n^{2-2\mu} 个 n^\mu 阶方阵乘法，若方阵指数为 3-\eta，总成本为

在瓶颈周围平衡参数，并用确定性桥接集合控制长路径，便获得 O(n^{2+\mu-\delta})。这解释了为什么一个“早已亚三次”的特殊问题，也能继续获得固定指数改进。arxiv.org

加权 k-Clique：把位置分成三组

令 k=3h+r，r\in\{0,1,2\}。先枚举余下 r 个顶点，再把其余位置分成三组。每组的部分 clique 成为新顶点，三组间的连接形成一个加权三角形实例。

若三角形算法为 N^{3-\eta}，则总时间为

这直接解释了论文的 k-Clique 指数形式，也给出了实数版本的相应组合推论。arxiv.org

Hinted OMv：只在确实足够“薄”的提示区间击穿猜想

令中间维度 D=n^\tau。预处理薄矩阵乘积后，输出一列需要 n 次单项查询，于是：

两阶段同时改善了对应猜想的界。一般参数分析将正改进区间扩展到 \tau<0.1204。

这一结果针对三种具体的 Hinted OMv 及其参数范围。普通 OMv，以及在更厚矩形区间建立的动态矩阵逆主界，仍需分别研究。arxiv.org

九、这场突破对理论计算机科学意味着什么

1. 一组长期充当“停止线”的猜想，已经成为可以越过的路标

细粒度复杂性积累了大量这样的关系：

它既传递困难性，也传递算法。此前，因为 3SUM、APSP 长期没有固定指数改善，人们更多使用前一种解释；现在后一种解释开始集中兑现。

一篇论文提供底层技术，几十个问题族同时获得新算法。归约网络在这一刻成为了算法传播网络。 这正体现了细粒度复杂性最有价值的积累。arxiv.org

2. 代数算法的研究目标发生了具体变化

新的问题不只是“怎样降低完整矩阵乘法的秩”，还包括：

• 哪些分解的输出依赖足够稀疏？
• 哪些乘法叶子能被大量请求共享？
• 怎样预存部分和，支持任意位置查询？
• 怎样组织输入编码，使复用真正抵消初始化成本？

Schönhage 的恒等式与 Coppersmith 的递归都来自经典工作；此次新发现，是它们的支持结构可以服务于稀疏输出，并且能被精确分析到足以跨越 3SUM 与 APSP 的指数屏障。

3. 归约损耗从“无关紧要的常数”变成优化目标

证明困难性时，只要保留某个正数节省即可。现在真正设计算法时，保留一半、三分之一还是全部节省，会直接改变最后的指数。

APSP 的逐边加强就是一个鲜明例子：

核心矩阵算法没有变化，只是更充分地利用了它已经提供的输出信息。作者也明确指出，许多归约仍有改进空间。arxiv.org

4. 渐近突破与工程加速需要分别评价

从 n^3 到 n^{2.9995}，纯指数改善因子是 n^{0.0005}。即使 n=10^{12}，它也只有约 1.014，尚未计入巨大常数。因此，目前结果的力量主要体现在理论边界上。

但对“是否存在任何固定 \varepsilon>0”这个命题，0.0005 已经具有决定性。

这篇论文没有给出 3SUM 与 APSP 的最终指数，却已经打开了一整组曾经关闭的指数区间。 后续研究现在拥有一个具体起点：恒等式、递归支持、共享计数、确定性归约，以及可以继续优化的每一处指数损耗。