Columbia 与 MIT 论文:Claude 发现的算法打破 3SUM 与最短路径长期速度极限
Claude 自己在理论计算机科学里挖出了几十年来没人找到的更快算法,还把两个经典猜想干翻了。想搞算法研究、或者好奇 AI 能不能做数学的,这篇都值得看,重点看他们怎么用 Lean 4 验证 AI 给的证明。
Columbia 和 MIT 的一篇新论文显示,Claude 找到的算法突破了 3SUM 和全对最短路径(APSP)问题的长期速度极限。3SUM 问的是列表中是否存在三个数之和为 0,全对最短路径要求计算图中所有点对的距离,几十年来没有算法能超越教科书级的平方和立方时间复杂度。
Claude 的做法是找到一种更快计算两个长瘦矩阵乘积中选定条目的方法,跳过了经典方法会做的一部分计算,再通过已知归约转化为 3SUM 和最短路径的加速。结果是 3SUM 达到 O(n^1.9992),最短路径达到 O(n^2.9995),增益虽小,但足以推翻 3SUM 和 APSP 两个著名猜想。整个过程在一次会话内完成,使用 16M 输出 token,没有人工干预。
论文用 Lean 4 对 AI 找到的证明做了形式化验证,这说明 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.
本条情报归属 AITOP「论文」核心栏目,重点聚焦北美前沿实验室与硅谷科技巨头。在跨区域产业观察坐标中,该动态直接关联「AI 开发者工具链、Coding Agent 与工程化实践」研究主线,反映出当前技术演进与商业落地的最新风向。涉及核心实体与技术议题包括:Claude、Lean 4、APSP、算法研究,读者可通过下方标签进入对应专题页查阅历史脉络与关联对比。
信源核验说明:本文原始线索采编自「rohanpaul_ai」(@rohanpaul_ai),经 AITOP 多维评分管线结构化提炼。