Papers76°

Columbia 与 MIT 论文:Claude 发现的算法打破 3SUM 与最短路径长期速度极限

Why we picked it

Claude 自己在理论计算机科学里挖出了几十年来没人找到的更快算法,还把两个经典猜想干翻了。想搞算法研究、或者好奇 AI 能不能做数学的,这篇都值得看,重点看他们怎么用 Lean 4 验证 AI 给的证明。

Columbia 和 MIT 的一篇新论文显示,Claude 找到的算法突破了 3SUM 和全对最短路径(APSP)问题的长期速度极限。3SUM 问的是列表中是否存在三个数之和为 0,全对最短路径要求计算图中所有点对的距离,几十年来没有算法能超越教科书级的平方和立方时间复杂度。

Body

Claude 的做法是找到一种更快计算两个长瘦矩阵乘积中选定条目的方法,跳过了经典方法会做的一部分计算,再通过已知归约转化为 3SUM 和最短路径的加速。结果是 3SUM 达到 O(n^1.9992),最短路径达到 O(n^2.9995),增益虽小,但足以推翻 3SUM 和 APSP 两个著名猜想。整个过程在一次会话内完成,使用 16M 输出 token,没有人工干预。

论文用 Lean 4 对 AI 找到的证明做了形式化验证,这说明 AI 搜索可以在理论计算机设计的核心难题上产生可验证的突破,开发者可以把这些"已知不可能"的算法极限当作开放目标交给 AI 搜索。

Original · 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.

Industry Coordinates & Source Verification

This report is categorized under AITOP's "Papers" desk, focusing on US frontier AI labs and Silicon Valley technology leaders. Within our cross-regional analytical framework, it directly maps to AI developer toolchains, coding agents, and engineering workflows. Key entities and technical topics under continuous tracking include Claude, Lean 4, APSP, reasoning models.

Source attribution: curated from rohanpaul_ai (@rohanpaul_ai).