新论文推翻 3SUM 与 APSP 猜想,传 Claude 参与发现次二次算法
burny_tech · x · 2026-10-06
arXiv 新论文《Truly Subquadratic 3SUM and Truly Subcubic APSP via Triangles in Sparse Lopsided Graphs》(作者 Josh Alman、Virginia Vassilevska Williams)给出首个对教科书级算法的多项式改进:
- 3SUM 可在对数大小的整数上以 O(n^1.9992) 时间确定性地求解,APSP 可在多项式整数权重图上以 O(n^2.9995) 时间求解,直接推翻了 3SUM 与 APSP 猜想。
- 借助已知归约,实数版 3SUM/APSP 猜想、Exact Triangle 猜想、Zero-Weight k-Clique 猜想及三个 Online Matrix-Vector 猜想也被一并推翻,并对一系列其他问题带来多项式加速。
- 核心是细矩阵乘的新算法:对 N×D 与 D×N 的整数矩阵(D≤N^{1/18}),只需计算指定 N²/√D 个位置时,可用 O(N²/D^0.063) 次操作完成,做法是改造基于 Schönhage 十乘恒等式的 Coppersmith 矩形矩阵乘算法,只执行必要运算。
Mira Murati 转发并称「Claude found a subquadratic 3SUM algorithm」,暗示 Claude 在该结果中发现/参与,引发热议。
所属事件: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