APSP 次立方与 3SUM 次平方算法问世，细粒度复杂度格局生变
thegautamkamath · x · 2026-10-06
- 研究者宣布在细粒度复杂度领域取得两项突破性结果：APSP（全源最短路径）首次实现真正次立方时间，3SUM 实现真正次平方时间。
- 评论者认为这是"真正非凡的结果"，但同时带走了该领域大部分乐趣：经典难度假设（APSP 假设与 3SUM 假设）一直是判定问题内在难度的基准，如今算法突破直接动摇了这些假设。
- 更深远的问题是它如何改变未来研究范式——以这些假设为基础的大量条件性下界结论需要重新审视，该领域的"新问题"是探索未来研究该如何开展。
「研究」频道最新
- tszzl:对齐要成为工程学科,起码得先攻克机制可解释性 — tszzl · 2026-10-06
- 因果决策研究亮相可信 AI 研讨会，录像已公开 — murat_kocaoglu_ · 2026-10-06
- Claude 突破 3SUM 复杂度下界，给出 O(n^1.9992) 算法附 Lean 证明 — thegautamkamath · 2026-10-06
- ReSteer 开源：修复 VLA 执行中途无视新指令的可控性缺陷 — siddkaramcheti · 2026-10-06
- 研究者携「推理模型潜空间策略状态」解读工作参加 COLM — hunarbatra · 2026-10-06
- COLM 2026 论文:推理微调会在 LLM 潜空间中留下持久策略状态 — hunarbatra · 2026-10-06