APSP 次立方与 3SUM 次平方算法问世,细粒度复杂度格局生变
thegautamkamath · x · 2026-10-06
- 研究者宣布在细粒度复杂度领域取得两项突破性结果:APSP(全源最短路径)首次实现真正次立方时间,3SUM 实现真正次平方时间。
- 评论者认为这是"真正非凡的结果",但同时带走了该领域大部分乐趣:经典难度假设(APSP 假设与 3SUM 假设)一直是判定问题内在难度的基准,如今算法突破直接动摇了这些假设。
- 更深远的问题是它如何改变未来研究范式——以这些假设为基础的大量条件性下界结论需要重新审视,该领域的"新问题"是探索未来研究该如何开展。
所属事件: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