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);改进幅度很小。

原帖引用 · AI 翻译

@rohanpaul_ai
译文 · 以原文为准

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

标题:“通过稀疏非对称图中的三角形实现真正次二次时间的 3SUM 和真正次三次时间的 APSP”

回复Rohan Paul@rohanpaul_ai
译文
哥伦比亚大学和麻省理工学院的一篇新论文表明,Claude 发现的一种算法突破了 3SUM 和所有点对最短路径问题长期以来的运行时间界限。 3SUM 问的是,一个列表中是否有 3 个数相加等于 0;所有点对最短路径问题要求求出图中每对顶点之间的距离。几十年来,没有人能将教科书中的二次时间和三次时间算法改进到超出微小幅度,许多人认为这根本不可能。 Claude 找到了一种更快的方法,计算 2 个细长矩阵乘积中选定的元素,省去了经典方法会做的部分计算。随后,利用已知的归约方法,可以将其转化为 3SUM、最短路径及许多相关问题的加速算法。 3SUM 现在可以在 O(n^1.9992) 时间内求解,最短路径问题可以在 O(n^2.9995) 时间内求解。这些提升虽然很小,但仍推翻了 3SUM 和 APSP 猜想。Claude 在 1 次会话中使用 16M 个输出 token,在无人类输入的情况下找到了这一方法。 将算法中“已知很难突破”的界限视为 AI 搜索的开放目标,并像这篇论文使用 Lean 4 所做的那样,对 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

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