AI 热点

哥伦比亚大学与 MIT 论文称 Claude 算法突破 3SUM 和全对最短路径长期速度界限

Rohan Paul更新于 11月22日 03:38

New Columbia and MIT paper shows that an algorithm Claude found beats the long-standing speed limits for 3SUM and all-pairs shortest paths.

AI 导读

哥伦比亚大学与 MIT 的论文称,Claude 找到的算法将 3SUM 和全对最短路径的时间复杂度分别降至 O(n^1.9992) 和 O(n^2.9995)。该方法通过减少两个细长矩阵乘积中特定条目的计算工作获得加速,并可借助已知归约用于相关问题。Claude 在 1 次会话中使用 16M 输出 token、无人类输入完成方法发现,论文以 Lean 4 检查了相关论证。

推荐理由

精选AI 评分 83

论文展示了 AI 搜索理论算法改进的具体路径,并用 Lean 4 形式化检查所得论证。

主题

标签

正文 · AI 翻译

哥伦比亚大学和 MIT 的新论文表明,Claude 找到的一种算法突破了 3SUM 和全对最短路径长期以来的速度界限。

3SUM 问题旨在判断一个列表中是否有 3 个数之和为 0,而全对最短路径问题则要求求出图中每对顶点之间的距离。几十年来,始终无人能将教科书中的二次和三次时间复杂度降低超过极小的幅度,许多人甚至认为这不可能实现。

Claude 找到了一种更快的方法,用于计算两个细长矩阵乘积中的特定条目,省去了经典方法所做的部分计算。随后,利用已知的归约方法,可以将其转化为对 3SUM、最短路径及许多相关问题的加速。

3SUM 现在可以在 O(n^1.9992) 时间内运行,最短路径则可在 O(n^2.9995) 时间内运行。这些提升虽然很小,但仍然推翻了 3SUM 假设和 APSP 假设。Claude 在 1 次会话中使用 16M 输出 token 找到了这一方法,全程没有人类输入。

应将“已知很难突破”的算法界限视为可供 AI 搜索攻克的开放目标,并对 AI 找到的证明进行形式化检验,就像这篇论文使用 Lean 4 所做的那样。

来源

Rohan Paul