Anthropic：Claude 自主发现 3-SAT 亚指数算法，推翻指数时间假设

__alpoge__ · x · 2026-10-27

Anthropic 公开了论文《A 2o(n) Time Algorithm for 3-SAT》及配套代码：一个内部 Claude 研究模型在无人类输入的情况下，用 1400 万输出 token 于 10 月 16 日自主找到了求解 3-SAT 的确定性亚指数时间算法，直接反驳了计算复杂性领域的指数时间假设(ETH)。该算法实际解决更难的 #3-SAT(计数解)问题，时间复杂度为 2O(n log log n / √log n)。

Anthropic 研究者随后与 Claude 协作改进论文表述，Lean 4 形式化证明也由 AI 模型完成。需要注意：这只是渐近意义的结果，对实际求解公式没有实践价值。Anthropic 将其定位为研究产物，不接受社区贡献。