3SUM 与 APSP 能否超越教科书算法？

两个指数推翻了长期假设

这两个问题的教科书算法数十年未被多项式改进：3SUM 问 n 个给定数中是否有三个数之和为零，此前只被加速了多对数因子；APSP 要求算出 n 顶点图中每一对顶点的最短路径距离，此前只被改进了次多项式因子。论文报告，对多项式大小的 n 个整数求解 3SUM 的确定性时间为 O(n^1.9992)，对边权为多项式界整数的有向 n 顶点图求解 APSP 的确定性时间为 O(n^2.9995)。

这两个指数之所以关键，是因为 3SUM 假设和 APSP 假设断言不存在真正次二次或真正次三次的算法，即指数无法与 2 或 3 拉开固定差距。如今两个假设都被推翻。节省的幅度绝对值很小，但它是多项式级的，而非多对数级的，而后者正是这两个假设划出的定性界线。

所有加速都来自一个薄矩阵乘积算法

全部结果都源自同一个新的薄矩阵乘积算法。取 N×D 整数矩阵 X 和 D×N 整数矩阵 Y，其中 D ≤ N^(1/18)，再取 N×N 输出矩阵中至多 N^2/√D 个位置组成的集合 W。算法恰好计算 (I,J) 属于 W 的条目 (XY)[I,J]，用 O(N^2/D^0.063) 次运算。

这个结果的意义来自与显然替代方案的比较：写出整个乘积 XY，或逐个计算 N^2/√D 个内积，代价都多项式地更高。算法通过改造 Coppersmith 矩形矩阵乘法算法的一个变体得到，而该变体本身建立在 Schönhage 的十次乘法恒等式之上；改造后它只执行所需条目需要的运算，而不计算完整乘积。

不平衡三角形把矩阵乘积接到 3SUM

把矩阵结果当作图算法来读，它在稀疏不平衡三部分图上以真正次二次时间解决了 All-Edges Sparse Triangle 问题：其中两部分各有 n 个顶点，第三部分只有 n^ε 个顶点，ε < 0.12。不对称正是关键——该技术能处理一侧远小于其他两侧的实例。

已知归约把 Exact Triangle 以及经由它的 3SUM 和 APSP 化归到这个不平衡问题，矩阵乘积的改进由此变成 3SUM 和 APSP 的改进。同样的归约还推翻了 3SUM 假设和 APSP 假设的实值版本、Exact Triangle 假设、Zero-Weight k-Clique 假设，以及 van den Brand、Nanongkai 和 Saranurak 提出的三个矩形 hinted Online Matrix–Vector 猜想，并为多种其他问题带来多项式加速。

预处理与查询时间、稀疏度相互权衡

论文还给出了数据结构版本，可以回答事先未知的 XY 单个条目查询。对每个小于 ε* = ln4/(5 ln10) ≈ 0.1204 的 ε 和每个 q > 0，满足 2 ≤ D ≤ N^ε 的矩阵可以在 O(N^2 log^2 D / D^γ) 时间和空间内被确定性预处理，之后任意单个条目可在 O(D^q log D) 时间内确定性算出。

显式参数表把这种权衡具体化。比值 c = L/m 越大，节省指数 γ 越大，但 ε 越小，意味着乘积必须更薄；查询更慢或集合 W 更稀疏，也允许更大的 γ。头条结果采用的设置是 c = 21、切换阶 t = m/9，得到 O(N^2/D^0.063) 的预处理和 O(D^0.437) 的单条目查询，因此任何满足 |W| ≤ N^2/√D 的 W 都能在 O(N^2/D^0.063) 内处理完。

乘积薄于 N^0.1204 时技术失效

常数 ε* ≈ 0.1204 是这一构造允许的乘积不平衡程度上限。论文指出，把 c 压向 10 就得到这个极限，因此不平衡三角形结果只覆盖 ε < 0.12，对 hinted Online Matrix–Vector 猜想的推翻也只在 τ1 < 0.1204 τ2 的范围内成立。

这条边界有作者明确说明的后果。有 m 条边的 All-Edges Sparse Triangle 平衡情形没有被加速，而它仍是若干来自 3SUM 和 Exact Triangle 的下界归约的目标。由被推翻猜想导出的动态算法权衡，在 τ ≈ 0.53 等参数下仍由未被推翻的形式支撑，因为那里的乘积远不够薄，不适用这一构造；只有查询最快的小 τ 一端失去了条件最优性。

曾用于证明困难的归约如今损耗指数

每个算法都把已知归约与矩阵定理组合起来，作者指出许多归约会损失节省量中的一个固定比例。从 Exact Triangle 到 Lopsided All-Edges Sparse Triangle 的归约只保留指数节省的一半，而从 3SUM 和 APSP 到 Exact Triangle 的归约分别保留一半和三分之一。

这些归约原本是为证明困难性设计的，那时只需保留某个多项式节省；如今当作算法使用，保留多少就成了决定因素。作者还指出，本文给出的指数已经可以不太费力地略微改进——APSP 可以绕开 Exact Triangle 的判定版本，3SUM 可以通过到离线 Set Disjointness 的直接随机归约——但他们优先选择了更简洁的表述，而非进一步的小幅提升。

哪些假设可以取代 3SUM 与 APSP

论文自己的优先关注点不是具体指数，而是接下来该用什么。它建议把假设限制在组合算法上，或采用这样的假设：有 m 条边的 All-Edges Sparse Triangle 平衡情形需要 m^(4/3−o(1)) 时间，因为这一平衡情形未被本文触及，且仍支撑许多困难性归约。

那些只被证明是 3SUM-hard 或 APSP-hard、而非等价于 3SUM 或 APSP 的问题没有得到更快的算法，因为归约方向相反；作者举了判断 n 个平面点中是否有三点共线的例子，其已知最快时间仍是 O(n^2)。k ≥ 4 的 k-SUM、3SUM-Indexing、无提示的 Online Matrix–Vector 以及 Orthogonal Vectors 也是如此。因此最具决策意义的分界，是这一技术能触及的不平衡实例与它触及不到的平衡实例之间。

核心算法由一个 AI 模型产出

方法部分记录了一段不寻常的来源。Anthropic 的一名员工用内部研究模型研究密码学理论中的开放问题，其中包括基于 Zero-k-Clique 平均情形困难性的构造；模型被要求验证并改进这些构造，却转而发展出这个算法，先解决平均情形，再解决最坏情形，整个过程使用 1600 万输出 token，没有人类输入。

Anthropic 于 2026 年 9 月根据保密协议把算法分享给作者。论文写完后，一个内部研究模型用 Lean 4 证明助手和 Mathlib 认证了主要结果，涵盖 O(n^2.9983) 时间的 Exact Triangle、O(n^1.9992) 时间的 3SUM 以及 O(n^2.99942) 时间的 (min,+) 乘积和 APSP，还有 k-Clique 推论的 Zero-Weight 情形。作者声明他们使用 Claude 协助写作、制图和检查数学细节，并对内容负全部责任。

关键是不平衡阈值而非头条指数

对判断该给这一结果多少分量的读者来说，有信息量的量不是 n^1.9992 的第四位小数，而是阈值 D ≤ N^0.1204。论文关于 3SUM、APSP 和被推翻猜想的所有主张，都经由这一范围内的薄乘积实现；作者也明确指出，要触及大于 n^0.12 的中间部分，例如围长近似某方法中出现的 n^1/2，需要另一种技术。

论文自己的表述也指向同一处：矩阵定理的任何改进都会传导到本文所有其他加速，而作者并不知道在给定 D 和 |W| 时计算薄乘积一组条目 W 的真实复杂度。实际读法是：All-Edges Sparse Triangle 的平衡情形，以及那些只是 3SUM-hard 或 APSP-hard 的问题，仍是旧假设继续发挥作用的地方。

本文引用的文献