3SUM 与 APSP 猜想被推翻：首次真次二次算法问世

ctjlewis · x · 2026-10-06

Josh Alman 与 Virginia Vassilevska Williams 发布论文，给出 3SUM 和全对最短路径（APSP）教科书算法的首个多项式级改进：3SUM 可在 O(n^1.9992) 时间内确定性求解，APSP 可在 O(n^2.9995) 时间内求解。这直接推翻了 3SUM 与 APSP 猜想，并连带推翻实数版本、Exact Triangle 猜想、Zero-Weight k-Clique 猜想等多个核心复杂度假设。

核心突破来自一个通用的 thin matrix product 新算法：对 D ≤ N^(1/18) 的矩阵，只需 O(N²/D^0.063) 次运算即可计算指定位置的乘积项，且多项式级地少于逐项内积计算的开销。算法改造了基于 Schönhage 十乘恒等式构建的 Coppersmith 矩形矩阵乘法变体。这是算法复杂度领域的里程碑式结果，对整个细粒度复杂度理论体系冲击巨大。