Columbia 与 MIT 的新论文显示,Claude 发现的算法在 3SUM 和全对最短路径问题上突破了长期存在的速度限制。3SUM 现在可在 O(n^1.9992) 时间内运行,最短路径为 O(n^2.9995),这些微小改进仍否定了 3SUM 和 APSP 假设。
论文给出 3SUM 与 APSP 的次二次、次三次算法,并说明算法由 Claude 发现、经 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 · x.com