Alman 与 Williams 首破 3SUM 与 APSP 平方/立方下界
Josh Alman 与 Virginia Vassilevska Williams 发布预印本论文《Truly Subquadratic 3SUM and Truly Subcubic APSP via Triangles in Sparse Lopsided Graphs》，对两个教科书级经典问题给出历史首次的多项式级改进：对 n 个多项式大小整数，3SUM 可在确定性 O(n^1.9992) 时间内求解；带多项式权重的 APSP 可在 O(n^2.9995) 时间内求解。这分别突破了长期被视为下界的 n² 与 n³ 界，实质上推翻了 3SUM 假设与 APSP 假设。
已确认
- 论文为确定性算法，是首个对 3SUM 与 APSP 的真正次平方/次立方结果
- 3SUM 算法附有 Lean 形式化证明（据理论计算机科学家 Ilya Razenshteyn 透露）
- 帖子流传 Anthropic 内部模型 Claude 参与发现次二次算法，@AMBNNJ 称其为内部模型的独立发现
为什么重要
- 3SUM 与 APSP 假设是细粒度复杂度理论的支柱，大量条件性下界建立在它们之上；被推翻意味着该领域格局重绘
- @thegautamkamath 转述评论称这是"真正非凡的结果"，但同时"带走了该领域大部分乐趣"——许多经典难度假设随之动摇
- 若 Claude 参与发现属实，将是 AI 在开放性理论研究中取得实质突破的标志性案例
2026-10-06 ~ 2026-10-06 · 6 条相关
一手来源
- Anthropic 内部模型独立发现算法,首次突破 3SUM 与 APSP 平方/立方下界 — AMBNNJ ·
- Alman 与 Williams 突破数十年瓶颈：3SUM 首次达到亚二次复杂度 — auto_grad_ ·
- Claude 突破 3SUM 复杂度下界，给出 O(n^1.9992) 算法附 Lean 证明 — thegautamkamath ·
- APSP 次立方与 3SUM 次平方算法问世，细粒度复杂度格局生变 — thegautamkamath · 2026-10-06
- 【源头】Claude 突破 3SUM 复杂度下界，给出 O(n^1.9992) 算法附 Lean 证明 — thegautamkamath · 2026-10-06
- 【源头】Alman 与 Williams 突破数十年瓶颈：3SUM 首次达到亚二次复杂度 — auto_grad_ · 2026-10-06
- 【源头】Anthropic 内部模型独立发现算法,首次突破 3SUM 与 APSP 平方/立方下界 — AMBNNJ · 2026-10-06
- 新论文推翻 3SUM 与 APSP 猜想，传 Claude 参与发现次二次算法 — burny_tech · 2026-10-06
另有 1 条近重复转述:ctjlewis