Claude 突破 3SUM 复杂度下界,给出 O(n^1.9992) 算法附 Lean 证明
thegautamkamath · x · 2026-10-06
理论计算机科学家 Ilya Razenshteyn 透露,Claude 为经典的 3SUM 问题(判断 n 个整数中是否存在三个数之和为零)给出了 O(n^1.9992) 时间的算法,并附带 Lean 形式化证明。此前长期猜想该问题不可能突破 O(n^2),这一硬度假设支撑了大量细粒度复杂度结果。
关键在于可信度:细粒度硬度领域的顶尖专家 Josh Alman 和 Virginia Williams 已对算法进行检查和消化,Razenshteyn 估计正确概率高达 99.99%。他表示「脑子被炸了」。如果坐实,这既是 AI 做数学研究的标志性成果,也可能撼动建立在 3SUM 猜想之上的一系列复杂度结论。
所属事件:3SUM 与 APSP 首获多项式级突破,传 Claude 参与发现(13 条相关)→
「漫话AGI」频道最新
- 从 Hassabis 到 Tao:年初还被泼冷水的 AI 解数学千年难题,如今接连告破 — haider1 · 2026-11-22
- eigenrobot 感慨:2020年谁会想到肥胖难题比黎曼猜想还难解 — eigenrobot · 2026-11-22
- 知名研究者 tszzl:旧金山将迎来「圣经级洪水」,原因不言自明 — tszzl · 2026-11-22
- NYT 长文:互联网毁了品味,AI 会把它彻底毁掉吗? — dreamwieber · 2026-11-22
- 陶哲轩预测黎曼猜想 2050 年才证完,AI 只用了 35 天 — SydSteyerhart · 2026-11-22
- LeCun 引 Piaget 称 LLM 只是记忆:智能在于不知道时如何行动 — ylecun · 2026-11-22