AI 发现新算法,首次突破 3SUM 与 APSP 复杂度下界
FrnkNlsn · x · 2026-10-06
arXiv 论文(Alman & Virginia Vassilevska Williams)给出多项式级的复杂度突破:3SUM 可在 O(n^1.9992) 内确定性求解,有向图全源最短路径(APSP)达 O(n^2.9995),首次推翻 3SUM 与 APSP 猜想,并连带推翻精确三角、零权 k-团等多个经典猜想。核心是一个新的细矩阵乘积算法,改造 Coppersmith 型矩形矩阵乘法。据 carlfeynman 转述,该算法由 AI 发现:Anthropic 有人在让 Claude 解决另一问题时偶然得到,再交由两位外部研究者写成论文并资助研究——流程颇为罕见。评论称论文写作异常清晰,是多项式复杂度领域的重大进展,接下来大量工作将围绕进一步压低指数展开。
所属事件: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