AI 热点

哥伦比亚大学与 MIT 论文称 Claude 算法突破 3SUM 和全对最短路径长期速度界限

Rohan Paul更新于 11月22日 03:38

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 导读

哥伦比亚大学与 MIT 的论文称,Claude 找到的算法将 3SUM 和全对最短路径的时间复杂度分别降至 O(n^1.9992) 和 O(n^2.9995)。该方法通过减少两个细长矩阵乘积中特定条目的计算工作获得加速,并可借助已知归约用于相关问题。Claude 在 1 次会话中使用 16M 输出 token、无人类输入完成方法发现,论文以 Lean 4 检查了相关论证。

推荐理由

精选AI 评分 83

论文展示了 AI 搜索理论算法改进的具体路径,并用 Lean 4 形式化检查所得论证。

主题

标签

正文

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.

来源

Rohan Paul