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

研究帖称 Claude 找到更快求解 3SUM 与最短路径的方法

AI 导读

一则介绍哥伦比亚大学与 MIT 论文的帖子称,Claude 找到一种计算两张细长矩阵乘积中指定元素的方法,可跳过传统方法的部分计算。帖子给出的 3SUM 和全点对最短路径时间复杂度分别为 O(n^1.9992) 和 O(n^2.9995);改进幅度很小。

原帖引用 · 原文

@rohanpaul_ai

– https://arxiv.org/abs/2610.06783

Title: "Truly Subquadratic 3SUM and Truly Subcubic APSP via Triangles in Sparse Lopsided Graphs"

回复Rohan Paul@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.
在 X 查看这条帖子 ↗

来源:Rohan Paul · x.com

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