88
AI 评分(两次独立评分的平均)哥伦比亚大学与 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.
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.
