Claude 发现的算法首次推翻 3SUM 与 APSP 复杂度猜想

Truly Subquadratic 3SUM and Truly Subcubic APSP via Triangles in Sparse Lopsided Graphs

Josh Alman, Virginia Vassilevska Williams

cs.DS, cs.CC

2026-10-06

3SUM 首次加速到 O(n^1.9992)、APSP 到 O(n^2.9995),推翻两大复杂度猜想,算法由 Claude 发现

这篇在解决什么

3SUM 问的是:n 个整数里有没有三个数加起来为零。教科书解法 O(n²),几十年只换来 polylog 级改进。APSP(所有点对最短路)同样卡住,Floyd–Warshall 的 O(n³) 至今只被砍掉一个亚多项式因子。精细复杂度(fine-grained complexity)把这团停滞写成两条猜想:3SUM 需要 n^{2-o(1)} 时间,APSP 需要 n^{3-o(1)}。两条猜想与 SETH 一起构成领域条件性下界的地基,计算几何、字符串、动态图里几十个问题的「hard」标签都溯源于此。这篇给出两者的第一个多项式级改进,两条猜想同时被推翻。

方法

全部结果出自同一个算法:只算稀疏输出集的薄矩阵乘法。X 是 N×D 整数矩阵,Y 是 D×N,D ≤ N^{1/18},W 是至多 N²/√D 个输出位置;只算 W 里的元素,耗时 O(N²/D^{0.063}),比把整个乘积写下来(Ω(N²))还少。输出多、运算少,下界就是这么破的。

难点在数叶子。逐条目数,每个条目要 10^m ≈ D^{1.66} 个叶子,比直接算 D 次乘法的内积还贵;省时全靠共享。每个条目有一个专属「私有叶」,其余叶子被大量条目共用;按 order 分类后,L = 19m 时高阶叶子按 2 的幂几何衰减,N²/√D 个条目合计只需约 N²/D^{1/18} 个叶子(加强版做到 O(N²/D^{0.063}))。

图论表述:Lopsided All-Edges Sparse Triangle,三部图两部分各 n 个点、第三部分只有 n^ε(ε < 0.12),对指定边对计数三角形,时间 O(n^{2-0.063ε})。3SUM、Exact Triangle、APSP 都有已知归约落到这个问题上,一个算法撬动一整片问题域。另有数据结构版:预处理 O(N²/D^{0.063}),此后单点查询 O(D^{0.437})。

结果

问题此前最好这篇
3SUM(整数)O(n²),仅 polylog 改进O(n^1.9992),确定性
3SUM(实数)n²O(n^1.998),Las Vegas
APSP(整数权重)≈n³O(n^2.9995),确定性
APSP(实数权重)≈n³O(n^2.998),Las Vegas
有向无权 APSPO(n^2.5275),Zwick 算法二十余年未动O(n^{2+µ-ε′′}),首个不靠更快矩形矩阵乘法的改进

Exact Triangle(确定性 O(n^2.9983))、Zero-Weight k-Clique、(min, +)-convolution 的猜想一并倒下,三个 hinted OMv 猜想在 thin 区间被推翻;MonoConvolution 提到 O(n^1.4999),0/1 Knapsack 首次进入 Õ(n + t^{2-δ})。不受影响的清单论文写得很明确:SETH、Orthogonal Vectors、无 hint 的 OMv、k ≥ 4 的 k-SUM 与 k-XOR、3SUM-Indexing。

摘要自述:推翻 3SUM、APSP、Exact Triangle 猜想的算法由 Claude 发现,作者 Josh Alman(Columbia)与 Virginia Vassilevska Williams(MIT)负责理解、简化、加强、扩展与写作;主要结果另由 Claude 用 Lean 4 加 Mathlib 做了形式化验证。

为什么重要

对理论界,这是精细复杂度成立以来最大的一次震动:三大支柱倒了两根,几十个问题的条件硬度失去地基;同一张归约网反过来变成算法分发网络,APSP 等价类、3SUM 等价类、(min, +)-convolution 类整体加速。论文自己也把这层意思讲透:归约本来就是算法,只是过去被当作 hardness 证据用。

对 AI 圈,看点在别处:悬置近三十年的核心构造由 AI 模型给出,再配上机器验证的证明。AI 参与数学从「补细节」推进到「给出关键构造」,这是目前最硬的公开案例之一。对工程实践,当前没有直接影响:指数从 2 挪到 1.9992,隐藏常数巨大,实用实现不会变快。它回答的是「下界是否成立」,不是「程序是否更快」。

局限与存疑

作者自列:常数极大,当前形式不实用;指数大概率还能压,项目过程中与 Claude 生成过指数更好但复杂得多的算法,故意未收录;技术只覆盖 lopsided 区间,第三部分超过 n^0.12 即失效,balanced sparse 情形与 m^{4/3} 壁垒原样保留,平面上三点共线是否真次二次重新变回 open;k ≥ 4 的 k-SUM 缺 self-reduction,这条思路推不过去;hinted OMv 的主下界(τ ≈ 0.53)不受影响,倒掉的只是快速查询端尾部。

单向归约的那批问题要单独看:大量动态图与计算几何问题没有拿到新算法,只是失去下界证据。另外「Claude 发现算法」的过程细节放在 Acknowledgments and Methodology 一节,本次抽取的正文不含该节,发现过程无从核验;作者此前用 Coppersmith–Winograd 恒等式试过同类思路未果,也说明这个构造并不顺理成章。

术语

原文与代码

社区讨论

相关论文

全部论文解读