Anthropic 内部模型独立发现算法,首次突破 3SUM 与 APSP 平方/立方下界
AMBNNJ · reddit · 2026-10-06
一篇新预印本论文给出确定性 O(n^1.9992) 的 3SUM 算法和整数权重的 O(n^2.9995) APSP 算法——这是对教科书级 n² 和 n³ 界的首次多项式级改进,分别推翻了 3SUM 假设和 APSP 假设。
- 核心是一种新的 thin matrix product(薄矩阵乘)算法,借助已知的归约,它还带来 Exact Triangle、零权 k-Clique、树编辑距离等一系列问题的加速
- SETH 与 Orthogonal Vectors 假设不受影响
- 论文明确指出,Anthropic 的一台研究模型自行找到了核心算法,且主要定理已用 Lean 形式化验证
如果属实,这是「AI 做出真正算法理论突破」的标志性事件,而非仅在竞赛或评测中刷分。
所属事件:3SUM 与 APSP 首获多项式级突破,传 Claude 参与发现(13 条相关)→
「漫话AGI」频道最新
- Hugging Face 工程师:刷屏 demo 经济学正在吞噬游戏级工程 — cocktailpeanut · 2026-11-22
- Gary Marcus 警告:黎曼猜想突破不代表 Anthropic 能力可泛化 — GaryMarcus · 2026-11-22
- 回顾 2010 年代主流 AI 安全路线:寄望单体 AI 集权推翻政府防线 — jessi_cata · 2026-11-22
- Benjamin Bratton 讽刺《大西洋月刊》AI 报道是「AI 止痛剂」 — bratton · 2026-11-22
- 菲尔兹奖得主吴宝珠评 AI 证明黎曼猜想:把 AI 输出当作待审视的自然数据 — Dr_Atoosa · 2026-11-22
- 从 Hassabis 到 Tao:年初还被泼冷水的 AI 解数学千年难题,如今接连告破 — haider1 · 2026-11-22