3SUM 与 APSP 首获多项式级突破,传 Claude 参与发现

Josh Alman 与 Virginia Vassilevska Williams 发布 arXiv 预印本《Truly Subquadratic 3SUM and Truly Subcubic APSP via Triangles in Sparse Lopsided Graphs》,对两个教科书级经典问题给出历史首次的多项式级改进:对 n 个多项式大小整数,3SUM 可在确定性 O(n^1.9992) 时间内求解;整数权重的全源最短路径(APSP)可在 O(n^2.9995) 时间内求解。这突破了长期被视为下界的 n² 与 n³ 界,实质推翻 3SUM 假设与 APSP 假设,重塑细粒度复杂度理论格局。社交媒体同时流传 Anthropic 的 Claude 参与发现核心算法的消息,目前尚无论文正文或 Anthropic 官方的直接说明。

已确认

尚未确认

为什么重要

2026-10-06 ~ 2026-10-08 · 13 条相关

事件全程(共 4 集)→

一手来源

另有 2 条近重复转述:ctjlewis · aran_nayebi