AI 发现新算法，首次突破 3SUM 与 APSP 复杂度下界

FrnkNlsn · x · 2026-10-06

arXiv 论文（Alman & Virginia Vassilevska Williams）给出多项式级的复杂度突破：3SUM 可在 O(n^1.9992) 内确定性求解，有向图全源最短路径（APSP）达 O(n^2.9995)，首次推翻 3SUM 与 APSP 猜想，并连带推翻精确三角、零权 k-团等多个经典猜想。核心是一个新的细矩阵乘积算法，改造 Coppersmith 型矩形矩阵乘法。据 carlfeynman 转述，该算法由 AI 发现：Anthropic 有人在让 Claude 解决另一问题时偶然得到，再交由两位外部研究者写成论文并资助研究——流程颇为罕见。评论称论文写作异常清晰，是多项式复杂度领域的重大进展，接下来大量工作将围绕进一步压低指数展开。