Claude 自主发现算法突破 3SUM 与全源最短路极限

原标题:New Columbia and MIT paper shows that an algorithm Claude found beats the long-standing speed limits...
88AI 研判分

哥伦比亚大学与 MIT 的论文显示,Claude 在无人工干预下自主发现了一种更快的长瘦矩阵乘积部分元素计算方法,并借助经典归约将其转化为 3SUM 与全源最短路径的算法加速。3SUM 复杂度降至 O(n^1.9992)、APSP 降至 O(n^2.9995,虽提升幅度极小,却首次实质性反驳了长期被视为不可突破的 3SUM 与 APSP 猜想。该结果由 AI 单次会话、1600 万输出 token 完成,并经 Lean 4 形式化验证。

报道正文

Rohan Paul (@rohanpaul_ai) · 2026-11-21 18

哥伦比亚大学和麻省理工学院的一篇新论文表明,Claude 发现的一种算法打破了 3SUM 和全对最短路径问题长期以来的速度极限。

3SUM 问题问的是列表中是否存在三个数之和为 0,全对最短路径问题则要求给出图中所有点对之间的距离。几十年来,没有人能把教科书式的二次和三次时间复杂度改进超过微小的常数因子,许多人认为这不可能做到。

Claude 找到了一种更快的方法,用于计算两个长而窄的矩阵乘积中的选定元素,跳过了经典方法所做的部分工作。借助已知的归约,这一方法进而为 3SUM、最短路径以及许多相关问题带来了加速。

3SUM 现在的运行时间为 O(n^1.9992),最短路径为 O(n^2.9995),这些微小的改进仍然否定了 3SUM 猜想和 APSP 猜想。Claude 在一次会话中、使用 1600 万输出 token、在没有任何人工输入的情况下找到了该方法。

把“已知困难”的算法极限视为 AI 搜索的开放目标,并对 AI 发现的证明进行形式化验证,正如这篇论文用 Lean 4 所做的那样。

推文配图