术语slug: all-pairs-shortest-paths

全源最短路径

All-Pairs Shortest Paths

计算图中所有节点对之间最短距离的经典问题,长期被视为立方时间下界代表

收录情报动态

共 1 篇 · 第 1/1 页
Rohan Paul (@rohanpaul_ai)T2·基座大模型
88 分
Claude 自主发现算法突破 3SUM 与全源最短路极限

哥伦比亚大学与 MIT 的论文显示,Claude 在无人工干预下自主发现了一种更快的长瘦矩阵乘积部分元素计算方法,并借助经典归约将其转化为 3SUM 与全源最短路径的算法加速。3SUM 复杂度降至 O(n^1.9992)、APSP 降至 O(n^2.9995,虽提升幅度极小,却首次实质性反驳了长期被视为不可突破的 3SUM 与 APSP 猜想。该结果由 AI 单次会话、1600 万输出 token 完成,并经 Lean 4 形式化验证。