精选论文
88AI 评分(两次独立评分的平均)

哥伦比亚大学与 MIT 论文:Claude 找到的算法突破 3SUM 与全源最短路径速度上限

原标题:New Columbia and MIT paper shows that an algorithm Claude found beats the long-standing speed limits for 3SUM and all-pairs shortest paths.

Rohan Paul@rohanpaul_ai发布时间 (北京时间)

AI 速览

根据原文整理 · 原文约 1 分钟

哥伦比亚大学与 MIT 研究者报告,Claude 找到的矩阵乘法算法改进了 3SUM 和全源最短路径的时间复杂度。

3SUM 时间
O(n^1.9992)
最短路径
O(n^2.9995)
Claude 搜索
1 次会话
形式验证
Lean 4
方法
Claude 找到一种计算长窄矩阵乘积部分结果的方法,可跳过经典算法中的部分计算。
结果
已知归约将矩阵乘法改进转化为 3SUM、全源最短路径等问题的速度提升。
影响
这些复杂度改进虽小,仍足以否定 3SUM 和 APSP 假设。
验证
研究者使用 Lean 4 对 AI 找到的证明进行了形式化验证。
搜索
Claude 在没有人工输入的一次会话中找到该方法,使用了 1600 万输出 token。

为什么值得看研究者可将传统算法速度上限视为 AI 搜索目标,并用形式化工具核验结果。

由 AI 阅读原文后整理,可能有疏漏,细节以原文为准。

New Columbia and MIT paper shows that an algorithm Claude found beats the long-standing speed limits for 3SUM and all-pairs shortest paths.

3SUM asks whether 3 numbers in a list sum to 0, and all-pairs shortest paths asks for every distance in a graph. For decades, nobody beat textbook quadratic and cubic time by more than tiny factors, and many assumed nobody could.

Claude found a faster way to compute selected entries of a product of 2 long, thin matrices, skipping work a classic method does. Known reductions then turn this into speedups for 3SUM, shortest paths, and many related problems.

3SUM now runs in O(n^1.9992) time and shortest paths in O(n^2.9995), tiny gains that still refute the 3SUM and APSP hypotheses. Claude found the method in 1 session using 16M output tokens with no human input.

Treat "known hard" algorithm limits as open targets for AI search, and check AI-found proofs formally, as this paper did with Lean 4.

Anthropic / Claude推理能力数据与训练论文研究#论文/研究#推理#数据/训练#Anthropic