Simple, Faster (min, +) Matrix Multiplication and APSP
Barna Saha, Christopher Ye
cs.DS
2026-10-14
Saha 与 Ye 用薄矩阵乘定理补上稀疏证书,在多项式有界整数上把 (min,+) 乘积的确定性复杂度降到 Õ(N^2.9964),低于 Anthropic 的 N^2.9995,APSP 等同一批问题跟着变快。
全源最短路(APSP)要在 N 个顶点的图上算完每一对顶点的距离。Floyd-Warshall 是 O(N^3)。随后几十年的算法只改进次多项式因子,Williams 2018 年的上界是 N^3 / 2^{Θ(√log N)},仍然写不成 N^{3-δ}(δ > 0 且不随 N 趋于 0)。细粒度复杂度里,「APSP 没有真正的次立方算法」因此是一条中心假设。
(min, +) 矩阵乘和 APSP 只差多项式对数因子。(A ∗ B)[i, j] = mink (A[i, k] + B[k, j]),乘法换成加法,求和换成取最小。普通矩阵乘已有上界 ω ≤ 9/4,这一族问题还贴着立方。
2026 年 Alman 与 Vassilevska Williams 的工作(论文称为 Anthropic 的突破)第一次给出确定性的 O(N^{2.9995}),假设被推翻。实数权另有期望 O(N^{2.998}) 的 Las Vegas 算法。2.9995 离 3 只有 0.0005。这篇在多项式有界的整数上把指数再往下推,并把证明放回 2016 年的分阶段框架。
要算的是两个 N×N 矩阵的 (min, +) 乘积,元素为多项式有界整数,平移后当作正整数。
先降到见证相等。给定 A、B 和候选矩阵 C,问每个位置 (i, j) 有没有 k 使 A[i, k] + B[k, j] = C[i, j]。把 A、B 各项除以 2 再向上取整,递归得到的乘积 X′ 满足 2X′ − 2 ≤ 真值 ≤ 2X′。于是每个位置只有三个候选整数,做三次判定,取其中有见证的最小值。U 每次折半,总时间乘上一个 log U 因子。
中间下标切成大小为 B 的块,块内有真 k 就是块见证。素数取自 [P, 2P],P ≫ B log U。假块的非零差值绝对值至多 3U,区间内素因子少;素数定理给出 Θ(P / log P) 个素数,随机 p 误判假块的概率至多 1/2。再独立抽 ⌈log S⌉ 个,概率降到不超过 1/S。真块不会被丢掉。
同余不能逐项扫。突破论文的薄矩阵乘(Theorem 25)规定:内维 D ≤ N^ε,ε < (ln 4)/(5 ln 10) ≈ 0.1204,并且只算至多 N^2 / D^κ 个输出位置时,这些普通乘积能在 O(N^2 log^2 D / D^γ) 时间内确定性算完。
实现时列下标是 (k, a),a 为模 p 的余数。X 标记 A 的余数,Y 标记 B 凑出目标余数 r。乘积为正,当且仅当该块对这个 p 是候选。内维为 Bp,需要 2BP ≤ N^ε。
随后只枚举候选块。每个 (i, j) 一旦找到真 k 就停,真块花费 O(N^2 B)。假块通过全部素数的概率至多 1/S,假候选期望 O(N^3 / (BS)) 个,枚举期望 O(N^3 / S)。
参数取 Table 2 的 ε = 0.056、κ = 0.5、γ = 0.0653。令 S = N,B 略小于 N^{ε/2} / log U。主导项对齐后时间是 Õ(N^{3 − γε} log U)。γε = 0.0036568,指数 2.9963432。log U 在多项式有界时被 Õ 吸收,定理写成 Õ(N^{2.9963432}),摘要记为 2.9964。
随机性只在抽素数。确定性版本把块对半拆开做深度优先,找到真见证就停。每层的势函数 Φ 上限假候选,但 Φ 要区分真假,不好算,改用只差常数因子的 Z(p),用多项式环上的矩阵乘对全部候选素数求值,再取最小。查询用 Corollary 31:预处理更便宜、单次更贵,高层查询少,预算拨给预处理。c = 21、t = 8,同一组 ε、γ,确定性上界不变。
比较对象是时间上界,论文没有实验数据。
| 方法 | 设定 | 时间 |
| Floyd-Warshall | 一般图 | O(N^3) |
| Williams 2018 | 一般图 | N^3 / 2^{Θ(√log N)} |
| Alman、Vassilevska Williams 2026 | 确定性 | O(N^{2.9995}) |
| 同上 | 实数权,Las Vegas | 期望 O(N^{2.998}) |
| 本篇 Theorem 1.1 | 多项式有界整数,Las Vegas | 期望 Õ(N^{2.9963432}) |
| 本篇 Theorem 1.3 | 同一输入,确定性 | Õ(N^{2.9963432}) |
按论文印刷的指数,确定性上界从 2.9995 降到 2.9963432。离 3 的空隙从 0.0005 变成 0.0036568,约为 7.3 倍。Õ 里的 polylog 改变不了这个差距。归约把同一上界送到 APSP、负三角形、替换路径、次短简单路径、度量性、(min, +) 验证、带权树编辑距离和二维最大子数组。
实数权没有新结果。期望 O(N^{2.998}) 仍是突破论文在实数上的界,这里没有直接对照。
这一步很小。要压过 Floyd-Warshall,N 得大到不现实,Õ 后面是代数矩阵乘的大常数,论文也没有实现。
它把 2016 年 Bringmann、Grandoni、Saha、Vassilevska Williams 的分阶段框架补完了。那个框架已能次立方地给出加性近似,并说明剩下的三元组个数也是次立方的,缺一张不依赖结构的稀疏证书。薄矩阵乘把证书补上。Theorem 25 的 ε、γ 再好,指数 3 − γε 就再降。Saha 是该框架 2016 年的作者之一。
随机版本先把每个位置收成三个整数,再用模素数丢掉大多数假块。薄矩阵乘负责核验,最后只扫剩下的候选。确定性算法维持同一指数,额外付出分层搜索、势函数和多项式环上的矩阵乘。
输入限于多项式有界的整数。实数矩阵没进入定理,突破论文对实数权 APSP 的期望 O(N^{2.998}) 也没被刷新。实数推广被留作以后的方向。
2.9963432 是 3 − γε 算出来的,γε 来自别人的薄矩阵乘。ε = 0.056 明显低于允许上限约 0.1204,换这一组只是为了配上 γ = 0.0653、κ = 0.5。黑盒不动,指数就不动。
确定性部分的常数卡得很死。一组导数组合要小于 0.5,R21(0.075) = 0.05663927 还得大于 ε。论文写明,随机算法的核对、调参和数值计算用了公开的 ChatGPT Pro,确定性算法的后续想法也来自那里,作者逐条核过并改写了证明。把算法再提示给 ChatGPT 后,还得到更低运行时间和一条借助已有归约走向实数矩阵的建议,作者尚未确认能放进这个框架。
简单指的是模块怎么拆。确定性那一半并不简单。预备知识引用了 ω ≤ 9/4,证明同时写明不必用到这么强的矩阵乘上界。