Claude 自主发现 2^o(n) 时间 3-SAT 算法，动摇指数时间假说

rickasaurus · x · 2026-10-27

Hexagon 平台发布一篇标注「主要由 AI 生成」的论文：Anthropic 内部研究模型在无人类输入、1400 万输出 token 的条件下，自主发现一个确定性 3-SAT 算法，运行时间 2^{o(n)}，并进一步解决了更难的 #3-SAT（统计可满足赋值数量）——这直接反驳了计算复杂性理论的核心假设 Exponential Time Hypothesis (ETH)。全部结果已在 Lean 4 中形式化验证。论文 10 月 16 日由模型发现，Anthropic 研究者随后协助改写表述；OpenAI 内部模型也声称同期独立证明了类似结果。转发者 rickasaurus 感慨：现在他更倾向于认为「人类只是之前真的不擅长这个」。