Anthropic 公开内部 Claude 研究模型发现的 3-SAT 亚指数算法：论文与 Lean 4 证明称推翻指数时间假设（ETH）

核心背景与行业痛点

指数时间假设（ETH）是复杂性理论的常用前提：它假设 3-SAT 不能在 2^o(n) 时间内求解，大量细粒度复杂度下界都建立在它之上。10 月 26 日 OpenAI 刚公布其内部模型对 ETH 的反驳；10 月 27 日，Anthropic 在官方 GitHub 仓库 anthropics/formal-math 的 eth 目录发布了另一份结果：论文《A 2^o(n) Time Algorithm for 3-SAT》，署名为 Claude（Anthropic）。X 简介显示在 Anthropic 工作的数学家 Levent Alpöge（@__alpoge__）在 X 上发帖称，核心算法由一个内部 Claude 研究模型于 10 月 16 日找到，用了 1400 万输出 token、无人工输入，随后 Anthropic 研究员与 Claude 一起改进了论文的表述。

架构亮点与底层机制

按仓库 README：确定性算法可在 2^o(n) 时间内判定 n 个变量的 3-SAT，从而推翻 ETH；它实际上能在 2^O(n log log n / √log n) 时间内求解更难的 #3-SAT（数满足赋值的个数）。README 给出的浓缩思路涉及完全图上的张量网络收缩、把 SWAP 按单重态个数分解成低秩算子，再按行或列合并节点并平衡分组，递归降低指数。README 还称 Claude Opus 5.5 在高推理强度下能根据这段浓缩描述重新推出「对任意 δ>0 可在 O(2^{δn}) 时间判定 3-SAT」，但推不出论文更精确的界。

权威 Benchmark 与实测跑分对比

这不是跑分类结果，关键在可验证性：Lean 4 形式化由 AI 模型编写，MainResults.lean 只依赖 Mathlib，陈述 ETH 为假（ETHIsFalse）和主定理；README 称证明只依赖 Lean 三条标准公理（propext、Classical.choice、Quot.sound），仓库 CI 还用 Comparator 比对定理陈述并用第二个独立内核 nanoda 复核。README 也提醒：机器不检查这份陈述是否与论文一致，需要读者自行核对。结果纯属渐近意义，对实际求解 SAT 实例没有帮助，仍待数学界独立审阅。

开发者实战落地与开箱指南

想自己验证：安装 elan 后进入 eth 目录，依次运行 lake exe cache get、lake build、lake env lean scripts/PrintAxioms.lean。官方说明构建在 24 个虚拟 CPU 上约 8 分钟，最大进程约用 7 GB 内存。仓库以 Apache 2.0 发布，属研究存档，不维护也不接受贡献。对开发者来说，更值得关注的是「模型长时间自主推理 + Lean 机器验证」这套流程正被两家头部实验室同时用于前沿数学。