3SUM 与 APSP 猜想被推翻:首次真次二次算法问世
ctjlewis · x · 2026-10-06
Josh Alman 与 Virginia Vassilevska Williams 发布论文,给出 3SUM 和全对最短路径(APSP)教科书算法的首个多项式级改进:3SUM 可在 O(n^1.9992) 时间内确定性求解,APSP 可在 O(n^2.9995) 时间内求解。这直接推翻了 3SUM 与 APSP 猜想,并连带推翻实数版本、Exact Triangle 猜想、Zero-Weight k-Clique 猜想等多个核心复杂度假设。
核心突破来自一个通用的 thin matrix product 新算法:对 D ≤ N^(1/18) 的矩阵,只需 O(N²/D^0.063) 次运算即可计算指定位置的乘积项,且多项式级地少于逐项内积计算的开销。算法改造了基于 Schönhage 十乘恒等式构建的 Coppersmith 矩形矩阵乘法变体。这是算法复杂度领域的里程碑式结果,对整个细粒度复杂度理论体系冲击巨大。
所属事件:3SUM 与 APSP 首获多项式级突破,传 Claude 参与发现(13 条相关)→
「研究」频道最新
- 斯坦福 CS312 深度学习炼金术课开课,作者建议用课程测验做合成数据种子 — jasondeanlee · 2026-11-22
- John Langford 评 FBT 笔记:定点迭代收敛与量化隐状态缓存 — JohnCLangford · 2026-11-22
- 菲尔兹奖得主吴宝珠评 AI 证明黎曼猜想:把 AI 输出当作待审视的自然数据 — Dr_Atoosa · 2026-11-22
- GPT-6 写出六页证明 Deligne 界,仅用 Cauchy–Schwarz 不等式 — Singularitarian · 2026-11-22
- 从 Hassabis 到 Tao:年初还被泼冷水的 AI 解数学千年难题,如今接连告破 — haider1 · 2026-11-22
- UT Austin 系统 Darmok 全对解出 7 道题,领先人类冠军 3 分 13 秒夺 cryptic 填字冠军 — rohanpaul_ai · 2026-11-22