Anthropic 内部模型自主发现算法：3SUM 与 APSP 首次获多项式级改进
2026.10.06 · 事件 · 论文 · 论文预印本
新预印本给出确定性 O(n^1.9992) 3SUM 与 O(n^2.9995) 整数权重 APSP 算法。
新预印本给出确定性 O(n^1.9992) 的 3SUM 和 O(n^2.9995) 的整数权重 APSP 算法，这是对教科书 n² 与 n³ 界的首次多项式改进。核心是一种新的 thin matrix product 算法，已知归约可将其转化为 Exact Triangle、Zero-Weight k-Clique、Tree Edit Distance 等的加速。论文称核心算法由 Anthropic 研究模…
- 确定性 O(n^1.9992) 3SUM 算法
- O(n^2.9995) 整数权重 APSP 算法
- 首次多项式改进 n² 与 n³ 教科书界
- 核心为 thin matrix product 新算法
- SETH 与 Orthogonal Vectors 不受影响
为什么值得看
首次多项式改进经典复杂度下界，且算法由 AI 自主发现。
适合谁关注
算法、理论计算机科学与 AI for Science 研究者。