[2610.06783v1] 通过稀疏歪边图中的三角形实现真正的亚二次3SUM和真正亚三次APSP 最近看到 Josh Alman 和 Virginia Vassilevska Williams 的新论文《Truly Subquadratic 3SUM and Truly Subcubic APSP via Triangles in Sparse Lopsided Graphs》。 这篇工作给出了目前第一个真正意义上突破经典复杂度的 3SUM 和 APSP 算法：在多项式有界整数的条件下，将 3SUM 从经典的O(n^2)降到了O(n^{1.9992})，将整数权重 APSP 从O(n^3)降到了O(n^{2.9995})。其核心并不是直接对传统 3SUM 算法做优化，而是提出一种新的 thin matrix product 算法，再通过稀疏的 lopsided triangle 等一系列归约，将这一改进传递到 3SUM、APSP 等问题上。 比较有意思的是，这项工作的核心算法据报道最初由 Anthropic 的模型发现，之后由研究人员进行分析、形式化和论文整理。 我的问题是： 应该如何评价这次对 3SUM hypothesis 的“反例”？ 更具体一点，我比较好奇：从算法理论的角度看，O(n^{1.9992})相对于O(n^2)虽然只是非常小的指数下降，但为什么足以构成对 3SUM hypothesis 的严格否定？这项工作的真正核心贡献应该理解为3SUM 算法本身的突破，还是thin matrix multiplication / sparse lopsided triangle 算法的突破？论文中的归约链条是如何把一个看起来与 3SUM 不太直接相关的矩阵乘法改进，最终转化为 3SUM 的亚二次算法的？如果这个结果成立，那么过去大量建立在 3SUM hypothesis 上的 fine-grained complexity 下界应该如何重新理解？哪些结论会受到影响，哪些不会？最后，从 AI for Math 的角度看，如果核心算法确实是由模型首先发现，而人类研究者负责验证、理解和整理，那么这种工作应该如何评价其“数学创造性”——是算法发现、证明、形式化验证三者中的哪一部分最值得关注？ 尤其想听听做

  • 情报分类：技术学习与提效
  • 分类依据：内容涉及技术、AI、软件工具或工程实践
  • 信息来源：资讯 / 知乎热榜
  • 发布时间：2026/10/6 21:42:06