精选论文
88
AI 评分(两次独立评分的平均)哥伦比亚大学与 MIT 论文:Claude 找到的算法突破 3SUM 与全源最短路径速度上限
原标题: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 速览
根据原文整理 · 原文约 1 分钟
哥伦比亚大学与 MIT 研究者报告,Claude 找到的矩阵乘法算法改进了 3SUM 和全源最短路径的时间复杂度。
- 3SUM 时间
- O(n^1.9992)
- 最短路径
- O(n^2.9995)
- Claude 搜索
- 1 次会话
- 形式验证
- Lean 4
- 方法
- Claude 找到一种计算长窄矩阵乘积部分结果的方法,可跳过经典算法中的部分计算。
- 结果
- 已知归约将矩阵乘法改进转化为 3SUM、全源最短路径等问题的速度提升。
- 影响
- 这些复杂度改进虽小,仍足以否定 3SUM 和 APSP 假设。
- 验证
- 研究者使用 Lean 4 对 AI 找到的证明进行了形式化验证。
- 搜索
- Claude 在没有人工输入的一次会话中找到该方法,使用了 1600 万输出 token。
为什么值得看研究者可将传统算法速度上限视为 AI 搜索目标,并用形式化工具核验结果。
由 AI 阅读原文后整理,可能有疏漏,细节以原文为准。
哥伦比亚大学和麻省理工学院的新论文表明,Claude 发现的一种算法打破了 3SUM 和全对最短路径长期以来的速度极限。
3SUM 问的是列表中是否有 3 个数之和为 0,全对最短路径则要求给出图中每一对节点之间的距离。几十年来,没有人能把教科书式的二次和三次时间复杂度改进超过微小的常数因子,许多人认为不可能做到。
Claude 找到了一种更快的方法来计算两个长而窄的矩阵乘积中的选定元素,跳过了经典方法所做的一些工作。已知的归约随后将其转化为 3SUM、最短路径以及许多相关问题的加速。
3SUM 现在的运行时间为 O(n^1.9992),最短路径为 O(n^2.9995),这些微小的改进仍然反驳了 3SUM 和 APSP 猜想。Claude 在一次会话中、使用 1600 万输出 token、在无人类输入的情况下找到了该方法。
把“已知困难”的算法极限视为 AI 搜索的开放目标,并像这篇论文用 Lean 4 所做的那样,对 AI 发现的证明进行形式化验证。
