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 猜想之上的一系列复杂度结论。