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

哥伦比亚大学与 MIT 论文报告 Claude 找到更快的 3SUM 和最短路径算法

AI 导读

论文称,Claude 找到一种跳过部分矩阵乘法计算的方法,借助已有归约,将 3SUM 的运行时间降至 O(n^1.9992),将所有点对最短路径降至 O(n^2.9995)。改进幅度很小,但论文称其推翻了这两类问题长期使用的复杂度假设,并用 Lean 4 检查了证明。

推荐理由

对关注 AI 科研能力的读者,这项研究的看点是 Claude 找到的算法方法带来了具体但微小的理论加速,且论文用 Lean 4 检查了证明。

原帖引用 · AI 翻译

@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 发现的证明进行形式化检验。

来源:Rohan Paul · x.com

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