aifollow.news
返回 Rohan Paul
Rohan Paul· @rohanpaul_ai · X· · 原发布时间 精选AI 评分74

哥伦比亚大学与 MIT 论文报告 Claude 找到更快的 3SUM 和最短路径算法

AI 导读

论文称,Claude 找到一种跳过部分矩阵乘法计算的方法,借助已有归约,将 3SUM 的运行时间降至 O(n^1.9992),将所有点对最短路径降至 O(n^2.9995)。改进幅度很小,但论文称其推翻了这两类问题长期使用的复杂度假设,并用 Lean 4 检查了证明。

推荐理由

对关注 AI 科研能力的读者,这项研究的看点是 Claude 找到的算法方法带来了具体但微小的理论加速,且论文用 Lean 4 检查了证明。

原帖引用 · 原文

@rohanpaul_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.

来源:Rohan Paul · x.com

论文
发现内容有误?提交纠错