AGI Hunt· thegautamkamath·· 1 小时前精选AI 评分79
Claude 突破 3SUM 复杂度下界，给出 O(n^1.9992) 算法附 Lean 证明
AI 导读
理论计算机科学家 Ilya Razenshteyn 透露，Claude 为经典 3SUM 问题给出了 O(n^1.9992) 时间算法，并附带 Lean 形式化证明。
推荐理由
3SUM 一直被假设快不过 O(n^2)，若该算法经同行确认，建立在这一猜想上的细粒度复杂度结论都要重新审视。
来源：AGI Hunt · agihunt.info