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 参与发现(5 条相关)→
「漫话AGI」频道最新
- AI 宣称证明千年数学难题后，数学家该书作者：这是数学的文艺复兴 — BachFrancis · 2026-10-06
- 库兹韦尔放话：AGI 或提前到来，2030 年代人类将实现「不老不死」 — tomchapin · 2026-10-06
- 学者署名争议引热议：AGI 前夜，功劳与 merits 已不再重要？ — BlackHC · 2026-10-06
- 连续谱意识观:从 12 神经元海洋生物到人类主观体验 — ctjlewis · 2026-10-06
- Frontiers 长文综述意识科学现状:AI 加速下该走向何方 — coherence · 2026-10-06
- Sam Altman：「超级智能」比人工智能更准确地描述当下 — 4KTV · 2026-10-06