3SUM 与 APSP 猜想被推翻,KLS 猜想同日被证明
aran_nayebi · x · 2026-10-06
理论计算机科学罕见的一天:Josh Alman 与 Virginia Vassilevska Williams 的 arXiv 论文首次给出对 3SUM 与全对最短路径(APSP)教科书算法的多项式级改进——3SUM 可在 O(n^1.9992) 内确定性求解,APSP 可达 O(n^2.9995),从而推翻了长期作为复杂性理论基础假定的 3SUM 与 APSP 猜想,并连带推翻精确三角形、零权 k-团等多个相关猜想。核心是通过对 Coppersmith 矩形矩阵乘法算法的改造得到的「thin matrix product」新算法。同日 KLS 猜想也被宣布证明。
所属事件: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