ETH 猜想出现反例：若最终获确认，会改变什么？

OpenAI 与 Anthropic 几乎同日公布研究结果，称各自的 AI 系统给出了指数时间假设 ETH 的反例证明。 这里的 ETH 是“指数时间假设”（Exponential Time Hypothesis），不是以太坊区块链，也不是苏黎世联邦理工学院的英文缩写 ETH Zurich。

我的判断是：这项结果若最终获得确认，首先改变的是算法研究使用复杂性假设的方式，而不是让现实程序立刻提速。目前公开材料虽包含 Lean 形式化验证，但外部专家的独立同行评审尚未完成，因此目前的“证伪”仍是一项有待学术共同体确认的成果。

ETH 指什么？

ETH 由 Impagliazco、Paturi 和 Zane 于 1999 年提出，针对的是布尔可满足性问题，尤其是 3-SAT。对于一个包含 (n) 个布尔变量的 3-SAT 公式，暴力方法需要检查最多 (2^n) 种赋值；ETH 断言，不存在真正次指数时间的通用算法，即不能把这类问题的指数级计算压缩到 (2^{o(n)}) 的增长量级。

报道提出的反例是一种针对固定 (k) 的 k-CNF 公式解集进行精确计数的算法。如果它确实能在次指数时间内完成计数，并可覆盖 3-SAT 对应的情形，就足以否定 ETH。 因此，否定一个复杂性猜想通常不需要解决整个 SAT 问题：找到一个足够强的反例算法即可。

以太坊是区块链网络，ETH Zurich 则是一所大学；两者与这项计算复杂性研究没有直接关系。 报道据此判断，比特币和以太坊的钱包安全不会因这项结果受到直接威胁。

AI 如何给出 ETH 反例？

这项反例证明涉及三个环节：构造算法、建立形式化证明、接受外部复核。AI 的核心工作是给出针对固定 (k) 的 k-CNF 精确计数算法，并分析其运行时间；OpenAI 与 Anthropic 独立产出了近乎一致的结果。

随后，OpenAI 使用 Lean 对相关证明进行形式化验证，并公开自然语言证明与形式化材料。Lean 的作用是检查每一步推导是否满足形式系统，而不是替代人工评估研究结论。 此次结果发布后，ETH 原始提出者及 Ryan Williams 等复杂性理论专家受邀参与验证和解释，但参与审查并不意味着已经为结论背书。

因此，形式化验证与独立结果分别回答“推导是否可靠”和“不同路线是否得到相同结论”两个问题；算法复杂度分析是否准确、成果是否构成有效反例，仍需学界继续复核。

哪些研究会先受影响，哪些暂时不会？

最先受到影响的是依赖 ETH 推导计算下界的论文，涵盖图论、计算生物学、数据库和计算几何等领域。 这些论文的结论不会因此全部失效，但作者需要重新检查：原有结论究竟需要完整的 ETH，还是只依赖更弱、仍然成立的假设。这也可能推动研究人员重新审视 SAT、计数算法及相关任务中是否存在此前被理论下界排除的改进空间。

这不等于 P=NP 已经被解决。P=NP 要求 NP 完备问题存在多项式时间算法，而 ETH 被否定至多表明特定 3-SAT 问题存在次指数算法，两者在时间复杂度上仍有明显距离。

现实程序的性能同样不会立刻改变。按报道中的测算，新算法在变量数低于 1000 万时没有性能优势；要让其渐进效率超过穷举，甚至需要 (10^{10000}) 量级的变量规模。 对日常软件、数据库和加密货币钱包而言，这仍属于理论突破远多于工程收益的阶段。

如果结果最终通过同行评审，复杂性证明将不能继续把 ETH 当作无需重审的前提；现实程序也不会因此立即提速。