哥伦比亚大学和麻省理工学院的新论文表明,Claude 发现的一种算法打破了 3SUM 和全对最短路径长期以来的速度极限。
3SUM 问的是列表中是否有 3 个数之和为 0,全对最短路径则要求出图中每一对节点之间的距离。几十年来,没有人能把教科书式的二次和三次时间复杂度改进超过极小的常数因子,许多人认为不可能做到。
Claude 找到了一种更快的方法来计算两个长而窄的矩阵乘积中的选定元素,跳过了经典方法所做的一些工作。已知的归约随后将其转化为 3SUM、最短路径以及许多相关问题的加速。
3SUM 现在的运行时间为 O(n^1.9992),最短路径为 O(n^2.9995),这些微小的改进仍然否定了 3SUM 和 APSP 猜想。Claude 在一次会话中找到了该方法,使用了 1600 万输出 token,没有人类输入。
把“已知困难”的算法极限视为 AI 搜索的开放目标,并像这篇论文用 Lean 4 所做的那样,对 AI 发现的证明进行形式化验证。


暂无评论