术语slug: 3sum

3SUM 问题

3SUM

判断列表中是否存在三数之和为零的经典计算问题,长期被视为二次时间下界代表

收录情报动态

共 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 形式化验证。