论文称Claude发现突破3SUM速度极限的新算法
IT时代网11月22日消息,哥伦比亚大学与麻省理工学院的研究人员在新论文中展示,Claude找到的算法打破了3SUM与全对最短路径两个经典问题的长期速度极限。
3SUM问题要求判断一组数中是否存在三个数之和为零,全对最短路径则要求算出图中每一对节点之间的最短距离。几十年来,学界普遍认为这两个问题的二次与三次时间复杂度难以实质改进。
Claude在新方法中找到了更快计算两个长而窄矩阵乘积中特定元素的办法,跳过了经典算法的部分步骤,再借助已知归约转化为上述问题及相关问题的加速。3SUM的新运行时间为O(n^1.9992),最短路径为O(n^2.9995),改进幅度虽然很小,但足以否定此前长期成立的猜想。
研究团队称,Claude在一次会话中完成了这一发现,使用了约1600万输出token,全程没有人类输入,相关证明已用Lean 4完成形式化验证。
论文提出,可以把这类已知极限视为AI搜索的开放目标,并对AI给出的证明做形式化校验,让算法发现过程可核可查。
注:本文配图由AI生成,文中包含AI辅助创作的内容。

编辑:林一舟
THE END