Claude 找到算法打破 3SUM 与最短路径数十年速度极限
rohanpaul_ai · x · 2026-11-22
哥伦比亚大学与 MIT 的论文《Truly Subquadratic 3SUM and Truly Subcubic APSP》显示,Anthropic 的 Claude 在一次会话中(约 1600 万输出 token、无人工干预)发现了计算细长矩阵乘积指定元素的新算法,进而推翻了细粒度复杂性理论的 3SUM 与 APSP 两大假设:
- 3SUM 问题首次做到 O(n^1.9992),APSP 做到 O(n^2.9995),是对教科书二次/三次复杂度的首个多项式级改进
- 通过已知归约,同一技术还推翻 Exact Triangle、Zero-Weight k-Clique 等一系列猜想,并加速多个相关问题
- 论文用 Lean 4(Mathlib)形式化验证了主要结果
作者的启示:应把「已知很难」的算法极限当作 AI 搜索的开放目标,并对 AI 给出的证明做形式化检验。
所属事件:Claude 参与发现的算法打破 3SUM 与 APSP 速度极限(2 条相关)→
「研究」频道最新
- Anthropic 开源 FlashProve:为 400B 参数 MoE 推理生成零知识证明 — jiqizhixin · 2026-11-22
- MiniMax 内部模型连破 NIST 候选算法,求解提速上千倍 — teortaxesTex · 2026-11-22
- a16z 访谈:LLM 预测可精确建模,但持续学习才是 AGI 缺口 — vishalmisra · 2026-11-22
- 黎曼假设「人类证明」被指错误,核心章节 §12.3 难以修复 — aran_nayebi · 2026-11-22
- 马斯克称超级智能拿下黎曼证明,去除依赖定理的条件性 — elonmusk · 2026-11-22
- Lean 版黎曼猜想证明:像看 AI 写的《哈姆雷特》 — soumitrashukla9 · 2026-11-22