💻 计算机科学

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

本文通过引入一种用于计算非对称图中矩阵乘积稀疏项的新算法，提出了针对 3SUM 和全对最短路径（APSP）问题超越教科书级算法的首个多项式级改进，从而反驳了 3SUM 和 APSP 假设，并为众多相关问题带来了加速。

原作者： Josh Alman, Virginia Vassilevska Williams

发布于 2026-10-06

📖 1 分钟阅读☕ 轻松阅读

原作者： Josh Alman, Virginia Vassilevska Williams

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

在计算机科学的广袤领域中，存在着一些顽固地抵御改进、数十年来都未能突破的难题，它们就像是阻碍我们更快处理信息的减速带。其中最著名的两个问题是“三数之和”（three-sum）问题和“全对最短路径”（all-pairs shortest paths）问题。第一个问题提出了一个简单的疑问：给定一组数字，能否找到三个相加等于零的数字？长期以来，为处理大型数字列表，解决此问题的最佳方法所需的时间随列表大小的平方而增长。第二个问题则是要求找出网络中每对城市之间的最短距离。已知最快的方法其所需时间始终随城市数量的立方而增长。多年来，计算机科学家们一直认为这些极限是无法逾越的，并形成了一套被称为“假设”的规则，暗示没有任何算法能比这些教科书式的方法显著更快。这些问题不仅仅是抽象的谜题；它们支撑着从地图软件到复杂数据模式检测的一切应用，因此，寻找打破这些速度限制的方法将是计算方式的一次巨大变革。

来自哥伦比亚大学和麻省理工学院的一个研究小组，通过与 Anthropic 开发的人工智能模型合作，现在打破了这些长期持有的信念。他们发现了一种解决这些问题的新方法，其速度确实比以往最好的方法更快。对于“三数之和”问题，该方法不再需要与输入规模的平方成正比的时间，而是以略小于平方的时间完成；同样，对于最短路径问题，他们将所需时间降低到了略小于城市数量的立方。这并非微小的调整或仅适用于特殊情况的小技巧，而是一种适用于广泛输入的根本性改进。通过证明这些问题可以更快地解决，研究人员有效地反驳了那些声称它们无法被更快解决的假设。

这一突破背后的秘密在于一种巧妙的新型矩阵乘法方法，矩阵简单来说就是用于表示数据的数字网格。研究人员专注于一种特定类型的矩阵乘法，即其中的网格是极长且极窄的，而非正方形。他们意识到，如果你只需要知道最终结果中某些特定位置的答案，而不是计算整个网格中的每一个数字，你就可以跳过大量的计算工作。他们设计了一种算法，其作用就像一个高效的过滤器，忽略掉那些会产生无人问津的答案的计算。这种技术是通过修改一个旧的数学恒等式（一套组合数字的规则），使其仅作用于那些真正重要的信息片段。

这项发现的力量源于这些不同计算机问题之间的内在联系。在细粒度复杂度（fine-grained complexity）的世界里，研究人员多年来一直在绘制如何通过解决一个问题来解决另一个问题的图谱。他们发现，如果你能更快地解决“三数之和”问题，你也能更快地解决“最短路径”问题，反之亦然。这个新算法就像一把万能钥匙。通过破解这个特定矩阵乘法问题的代码，研究人员解锁了数十个此前被认为受限于旧速度的问题的更快速解法。这包括在网络中寻找三角形、检查数据中的特定模式，以及优化各种类型的搜索和排序任务。

该团队不仅提供了一个理论上的可能性，还提供了一种每次都能奏效的具体的确定性方法。他们还展示了即使处理的不是整数，而是实数（即大多数现实世界科学计算中所使用的数值），该方法依然有效。研究人员使用强大的人工智能工具辅助验证他们的数学证明，确保了提速背后的逻辑是严密的。这种人类研究员与人工智能之间的协作，凸显了一个新的科学发现时代——在这个时代，机器可以帮助人类揭示深奥的数学真理。

这项工作的意义远超“三数之和”和“最短路径”这两个具体问题本身。它挑战了“某些计算极限是绝对的”这一观点。几十年来，学术界一直接受某些问题需要特定时间来解决的事实，并认为尝试提速是徒劳的。这篇论文证明了，那些极限并非墙壁，而仅仅是可以通过正确的视角来提高的上限。虽然由于其巨大的隐藏常数，这些新算法目前还太复杂，无法应用于日常软件，但它们存在的证明改变了计算机科学的理论基础。它为未来的研究人员开辟了大门，让他们可以精炼这些方法，从而有望开发出能比以往更高效地处理海量数据集的实用工具。研究人员已经表明，即使是最顽固的问题也能在全新的思维方式下屈服，这证明了计算能力的边界永远值得去测试。

技术摘要：通过稀疏非对称图中的三角形实现真正的次二次方 3SUM 与真正的次三次方 APSP

1. 问题陈述

本文解决了细粒度复杂度理论中两个数十年来未能取得显著进展的基础问题：

3SUM： 给定 $n$ 个多项式大小的整数，判断是否存在三个数之和为零。标准算法的运行时间为 $O(n^2)$ ，而 3SUM 假设认为不存在能在 $O(n^{2-\epsilon})$ 时间内解决该问题的算法（对于任何 $\epsilon > 0$ ）。
全源最短路径 (APSP)： 给定一个具有 $n$ 个顶点且权重为多项式有界整数的有向图，计算所有点对之间的最短路径。标准算法（Floyd-Warshall, Johnson）运行时间为 $O(n^3)$ 。APSP 假设认为不存在能在 $O(n^{3-\epsilon})$ 时间内解决该问题的算法。

本文还针对 精确三角形 (Exact Triangle) 问题（在三部图中寻找总边权为零的三角形）以及 有向无权 APSP 问题，以及在细粒度归约下与它们等价的多种问题（例如 $(\min, +)$ -乘积、树编辑距离、零权 $k$ -团）进行了研究。

2. 方法论

核心贡献在于一种计算两个“薄”矩阵乘积中指定稀疏条目集合的新算法。

2.1 薄矩阵乘积算法

作者开发了一种确定性算法，用于计算两个“薄”矩阵乘积 $XY$ 中的一个条目集合 $W$ ，其中：

$X$ 是一个 $N \times D$ 的整数矩阵。
$Y$ 是一个 $D \times N$ 的整数矩阵。
$D \le N^{1/18}$ （矩阵是“薄”的）。
$W$ 是一个包含至多 $N^2/\sqrt{D}$ 个位置的集合。

关键技术创新：
该算法修改了 Coppersmith 的矩形矩阵乘法算法，该算法本身基于 Schönhage 的十乘法恒等式。

递归结构： 算法递归地应用 Schönhage 恒等式。与计算所有 $N^2$ 个条目的标准矩阵乘法不同，该算法会修剪递归树。
修剪策略： 算法仅访问计算集合 $W$ 所必需的递归树“叶子”。
编码共享： “编码”阶段（输入块的线性组合）仅取决于输入矩阵，而不取决于特定的输出条目。算法为每个输入块计算一次编码，并在所有必需的计算中共享。
叶子分析： 作者分析了递归树中叶子的“阶数”（order）。他们证明了虽然单个输出条目需要许多叶子，但大多数叶子被许多输出条目所共享。通过仔细平衡不同阶数的叶子数量，他们表明对于稀疏集合 $W$ ，所需的总叶子数显著小于计算完整乘积或单独计算各条目的成本。

复杂度：
该算法在 $O(N^2 / D^{0.063})$ 时间内（包含对数因子）计算集合 $W$ 中的条目，这比计算完整乘积所需的 $O(N^2)$ 时间或作为内积单独计算各条目所需的 $O(N^2 \sqrt{D})$ 时间在多项式级别上更快。

2.1 归约至图问题

该矩阵算法被应用于 非对称全边稀疏三角形 (Lopsided All-Edges Sparse Triangle) 问题。在该问题中，目标是确定在三部图（其中部分 $A, B$ 大小为 $n$ ，中间部分 $M$ 大小为 $D \ll n$ ）中，给定的一组边 $(a, b)$ 是否构成三角形。

矩阵解释： 这等价于计算图中两个邻接矩阵乘积在对应于边集 $W$ 的位置上的条目。
确定性归约： 本文提供了一个从 精确三角形（在一般图上）到 非对称全边稀疏三角形 的确定性归约。这涉及将边权对通过确定性选择的素数进行取模哈希，以最小化假阳性，随后进行见证搜索。
归约链： 已知的细粒度归约将 3SUM 和 APSP 与精确三角形联系起来。通过将这些归约与新的非对称全边稀疏三角形算法结合，作者推导出了原问题的更快速算法。

3. 主要贡献与结果

3.1 对假设的反驳

本文展示了对 3SUM 和 APSP 教科书级算法的首次多项式改进，从而反驳了细粒度复杂度中的 3SUM 和 APSP 假设。

3SUM： 以 $O(n^{1.9992})$ 时间确定性地解决（针对多项式大小的整数）。
APSP： 以 $O(n^{2.9995})$ 时间确定性地解决（针对有向图且权重为多项式有界整数）。
精确三角形： 以 $O(n^{2.9983})$ 时间确定性地解决。
有向无权 APSP： 以 $O(n^{2+\mu-\epsilon})$ 时间确定性地解决（其中 $\mu < 0.5275$ ），反驳了 Zwick 算法是最优的假设。这是第一个并非完全源于更快的矩形矩阵乘法边界的改进。

3.2 实值变体

利用由 Chan, Vassilevska Williams 和 Xu 提出的仅依赖比较、加法和减法的归约，作者为实值版本的这些问题提供了 Las Vegas 算法（零误差的随机算法）：

实值 3SUM： 期望时间 $O(n^{1.998})$ 。
实值 APSP： 期望时间 $O(n^{2.998})$ 。

3.3 更广泛的算法影响

通过已知的归约，新算法为一系列其他问题带来了多项式级加速，包括：

矩阵的 $(\min, +)$ -乘积。
树编辑距离（对于多项式有界的整数代价）。
任何常数 $k \ge 3$ 的 零权、最小权和最大权 $k$ -团。
在线矩阵-向量 (OMv) 猜想： 本文通过提供一种可以在 $O(N^2/D^{0.063})$ 时间内预处理矩阵并在相对于内维度的亚线性时间内回答单条目查询的数据结构，反驳了 OMv 猜想的“提示型”（hinted）变体（特别是针对薄提示的情况）。
背包问题与近似子集和问题： 首次实现了非限定背包问题的真正次二次方算法，以及子集和问题的近似方案。

3.4 数据结构版本

作者将矩阵算法扩展为一种数据结构。在 $O(N^2/D^{0.063})$ 时间内预处理 $X$ 和 $Y$ 后，可以 $O(D^{0.437})$ 时间内计算任何单个条目 $(XY)[I, J]$ 。这使得解决那些无法预先知道目标条目的问题成为可能。

4. 重要性与声明

作者认为这项工作是“细粒度复杂度的巨大成功”。

归约为算法： 本文强调，细粒度归约此前主要用于推断条件硬度，但它们也是算法。一种新的技术（薄矩阵乘积算法）可以同时加速广泛的相互关联的问题网络。
反驳现状： 结果表明，3SUM 和 APSP 的“停滞”运行时间并非基本障碍，而是当时可用技术的产物。
局限性与开放问题：
- 作者指出，由于这些问题无法归约到本文解决的特定稀疏三角形实例，因此其技术目前尚未改进 CNF-SAT、正交向量 (Orthogonal Vectors) 或 $k \ge 4$ 的 $k$ -SUM。
- 这些算法是代数性的，目前具有较大的隐藏常数，因此在实际应用中尚不具备即时实用性。
- 平衡情况下的全边稀疏三角形（三个部分的大小均为 $n$ ）仍由该技术未解决，使得该特定情况下的 $m^{4/3}$ 假设依然成立。
- 论文并未声称找到了这些问题的最优指数，并指出通过更好的归约或更精细的代数恒等式，未来可能实现进一步的改进。

5. 关于发现的方法论说明

论文明确承认，核心算法是由 Anthropic 开发的 AI 模型 Claude 发现的。作者（Josh Alman 和 Virginia Vassilevska Williams）致力于理解、简化、加强并扩展该算法，推导其后果并使结果形式化。主要结果已使用 Lean 4 证明辅助工具进行了验证。作者对论文的内容和陈述承担全部责任。