您的位置首页 >科技要闻 >

论文称Claude发现突破3SUM速度极限的新算法

一篇 arXiv 预印本论文指出,Anthropic 的 Claude 模型自主发现了 3SUM 问题的新确定性算法,打破了细粒度复杂度领域沿用多年的 3SUM 猜想,证明整数版本 3SUM 可以做到真次二次时间 O (n¹・⁹⁹⁹²),同时配套的全对最短路径 APSP 算法达到 O (n²・⁹⁹⁹⁵),推翻 APSP 猜想。3SUM 问题是给定一组数字,寻找三个数相加等于 0,过去学界长期猜想它不存在 O (n²⁻ᵉ) 复杂度的算法,大量复杂度证明、难度规约都建立在这个假设之上;Claude 在一次 1600 万 token 的无人值守会话里产出核心算法思路,之后由 Josh Alman、Virginia Vassilevska Williams 整理、简化、拓展,并用 Lean4 形式化工具完成机器校验。该成果属于理论计算机突破,目前只是预印本,还没有完成同行评审,短期几乎没有工程落地收益,更多是改写细粒度复杂度的底层假设,连带精确三角形、奇数 k-SUM 等一批相关猜想同步被证伪。

核心成果参数表

项目详情
论文标题Truly Subquadratic 3SUM and Truly Subcubic APSP via Triangles in Sparse Lopsided Graphs
发布平台arXiv 预印本,2026-10-05
核心主体Claude(Anthropic 内部研究模型)发现算法核心,人类学者整理完善
3SUM 新复杂度O (n¹・⁹⁹⁹²) 确定性算法(多项式大小整数)
配套 APSP 复杂度O(n²·⁹⁹⁹⁵)
关键结论证伪 3SUM 猜想、APSP 猜想、精确三角形猜想
验证方式Lean4 形式化证明校验
状态预印本,尚未同行评审
技术根基稀疏不平衡图三角形、选择性矩阵乘法子例程

成果要点清单

  • 猜想边界被打破:3SUM 猜想认为 3SUM 最坏情况无法低于二次 O (n²),本次证明存在指数小于 2 的确定性算法
  • 连锁影响:依靠 3SUM 难度规约的一大批算法下界结论,都需要重新评估
  • 发现过程特殊:不是人设计,是大模型在无人工干预长会话中找到核心构造;人类负责理解、补全、形式化验证
  • 实用性有限:指数只是从 2 降到 1.9992,差距极小,现实数据集上速度提升微乎其微,属于理论突破,不适合拿来直接写代码提速
  • 衍生方向:后续已有跟进论文,给出不用矩阵乘法、更简单的随机版本,还推翻所有奇数 k 的 k-SUM 猜想

成果验证流程步骤

  1. Claude 输出核心算法构造:在长上下文无人值守会话中给出稀疏图三角形 + 选择性矩阵乘法方案
  2. 人类学者梳理逻辑:Alman 与 Williams 拆解、简化算法,补齐边界条件、证明细节
  3. Lean4 形式化校验:用交互式定理证明器逐条核验证明,排除手写证明漏洞
  4. 上传 arXiv 预印本公开,社区开展独立复现、质疑、拓展
  5. 等待同行评审,确认结论是否被学界正式接纳

【相关 FAQ】

问题 1:论文称 Claude 发现突破 3SUM 速度极限的新算法,3SUM 到底是什么问题?

回答 1:3SUM 就是给定一串数字,找出其中三个数字之和等于 0;它是细粒度复杂度理论的标杆问题,过去几十年学界默认它无法做到 O (n²⁻ᵉ),很多算法难度证明都依赖这个猜想。

问题 2:论文称 Claude 发现突破 3SUM 速度极限的新算法,是不是意味着现在 3SUM 可以跑得飞快?

回答 2:不是,Claude 给出的新复杂度是 O (n¹・⁹⁹⁹²),仅仅比 O (n²) 在指数上微小下降,实际工程场景几乎感受不到提速,价值集中在理论计算机,不是实用算法优化。

问题 3:论文称 Claude 发现突破 3SUM 速度极限的新算法,成果有没有经过严谨验证?

回答 3:论文配套 Lean4 形式化机器校验,证明步骤可以被定理证明器核验;但目前只是 arXiv 预印本,还没有正式同行评审,学界还在独立复核结论。

问题 4:论文称 Claude 发现突破 3SUM 速度极限的新算法,这个成果对其他算法有什么连带影响?

回答 4:3SUM 是很多问题的难度基准,这个猜想被推翻后,精确三角形、APSP 全对最短路径、奇数 k-SUM 等一系列依赖 3SUM 规约的复杂度猜想,同步失效,整个细粒度复杂度分支要重新梳理下界。

【参考资料】

[2026-10-05](Truly Subquadratic 3SUM and Truly Subcubic APSP via Triangles in Sparse Lopsided Graphs)arXiv

[2026-10-30](3SUM Made Simpler (Without Matrix Multiplication))arXiv

[2026-11-22](Claude's 3SUM and APSP Algorithm: What the Paper Proves)CellCog

[2026-10-06](3SUM Breakthrough: Why Claude’s 1.9992 Algorithm Matters)Binary Verse AI

[2026-10-25](3SUM 维基条目更新)Wikipedia

【免责声明】

本文信息基于 arXiv 预印本与第三方解读整理,Claude 发现算法的结论以论文致谢表述为准;该成果尚未完成同行评议,学界仍存在讨论空间;算法复杂度为渐近理论上界,不代表现实代码可以获得显著加速;本文仅为学术资讯科普,不构成学术结论背书。

今日大家都在搜的词: