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 猜想也被宣布证明。
所属事件:Alman 与 Williams 推翻 3SUM 与 APSP 假设，传 Claude 参与发现(8 条相关)→
「研究」频道最新
- 作者演示用蛋白质语言模型自由「书写」蛋白质序列 — CatAstro_Piyush · 2026-10-07
- 希尔伯特第12问题与SIC-POVM猜想宣称解决，引LLM证明争议 — littmath · 2026-10-07
- 11 个正方形装箱最优性获证明：Astra 与 Claude 协助在 Lean 中形式化 — ctjlewis · 2026-10-07
- COLM 2026 现场：研究员探索通用一次性 Agent 与演化知识库的 RSI 新范式 — yisongyue · 2026-10-07
- 数学家 John Urschel 证明高斯消元增长因子约为 n^1/2,破解 Trefethen 长期猜想 — ctjlewis · 2026-10-07
- 记忆到底存在哪：RNN、Transformer 与 SSM 的工作记忆对比 — Pretty_Upstairs9035 · 2026-10-07