Alman 与 Williams 突破数十年瓶颈:3SUM 首次达到亚二次复杂度
auto_grad_ · x · 2026-10-06
Josh Alman 与 Virginia Vassilevska Williams 发布新论文,首次对教科书级经典算法给出多项式级改进:对 n 个多项式大小的整数,3SUM 可在 O(n^1.9992) 时间内确定性求解;带多项式界整数权重的有向图 APSP 可在 O(n^2.9995) 时间内求解。这一结果直接推翻了 3SUM 假设与 APSP 假设——这两个假设是细粒度复杂度理论的基石,此前被广泛认为不可攻破。\n\n借助已知归约,论文还推翻了实数版 3SUM/APSP 假设、Exact Triangle 假设、零权 k-Clique 假设等多个重要猜想,并给一系列问题带来多项式加速。核心技术是单一的新「薄矩阵乘」算法:对 N×D 与 D×N 的整数矩阵(D≤N^1/18),只需输出任意 N²/√D 个指定位置时,可在 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