指数时间假设 ETH

形式陈述 ​

令 $n$ 表示公式中的变量数。指数时间假设（ETH）断言：3-SAT公理库3-SAT3-SAT · Three-satisfiability每个子句恰含三个文字的合取范式可满足性问题。 不存在运行时间

$$2^{o(n)}\mathrm{poly}(|\phi |)$$

的确定性算法。等价地，可令 $s_3$ 表示使 3-SAT 能在 $O^{\ast }(2^{\delta n})$ 时间内求解的指数常数 $\delta$ 的下确界，并写成 $s_3>0$；$O^{\ast }$ 隐去输入长度的多项式因子。这里的等价表述固定了算法模型、确定性和变量数参数，不能把 $n$ 无声换成子句数或编码 bit 长度。

ETH 是复杂度假设而非已证明定理。本库以 axiom 标记其在条件下界论证中的前提角色；任何由它推出的结论都必须保留“若 ETH 成立”这一条件。稀疏化引理可以把固定宽度 CNF 拆为受控数量的稀疏实例，从而连接变量数与子句数版本，但那是额外定理，不属于假设的定义。

直觉 ​

P 与 NP公理库复杂度类 NPNP · Nondeterministic polynomial time由正实例拥有多项式长度、可在多项式时间内验证的证书所刻画的语言类。 问题只问是否存在某个多项式时间算法；ETH 进一步猜测 SAT 的指数部分不能压缩到次指数。它为“困难到什么量级”提供刻度：一个归约若把 SAT 的 $n$ 个变量变成目标问题的参数 $k=O(n)$，目标上的 $2^{o(k)}$ 算法就会反推出被 ETH 排除的 3-SAT 算法。

这个假设不指定最佳指数底数，也不声称所有 NP 困难问题都恰需 $2^n$。它只保留一个正的指数常数下界，让归约能够排除次指数依赖。

例子与边界 ​

穷举全部布尔赋值在 $O^{\ast }(2^n)$ 时间内求解 3-SAT，与 ETH 完全相容；即使发现 $O^{\ast }({1.3}^n)$ 算法，也仍是 $2^{\mathrm{\Theta }(n)}$，不会否定假设。相反，$2^{\sqrt{n}}\mathrm{poly}(|\phi |)$ 或 $n^{\log n}$ 都是 $2^{o(n)}$，若能解决所有 3-SAT 实例便会直接推翻 ETH。

这一区分展示的不是“把 2 换成 1.3”的伪例，而是指数级与次指数级的边界：前者仍有线性指数，后者的指数除以 $n$ 后趋于零。条件下界必须证明目标算法会跨过这条边界，而不能只说它“比暴力快”。

若以公式总长度 $N$ 计，变量很少但含大量重复子句的输入会使 $2^{o(N)}$ 与 $2^{o(n)}$ 表达不同主张。把 3-SAT 改成 2-SAT 也不成立，因为 2-SAT 有多项式时间算法。ETH 更不排除 $2^{0.01n}$；它断言的是某个正指数常数不可消失，而非常数至少等于 $1$。

推论与应用 ​

ETH 通过规模保持归约给图算法、参数化算法和精确算法提供条件下界，例如排除某些 $2^{o(k)}$ 或 $n^{o(k)}$ 时间形式。每条结论都要核对归约后的规模关系：若目标参数增长为 $k=\mathrm{\Theta }(n^2)$，一个 $2^{o(k)}$ 算法未必转化成 $2^{o(n)}$，不能只凭“大 O”口号传递假设。

比 ETH 更强的假设会约束所有 $k$-SAT 的最佳指数常数并在 $k$ 增大时逼近穷举底数；二者不能互称等价。ETH 页面只建立 3-SAT 的次指数禁区，并为后续稀疏化、SETH 与细粒度归约提供明确基线。

参考资料

• Russell Impagliazzo and Ramamohan Paturi, “On the Complexity of k-SAT,” Journal of Computer and System Sciences 62(2), 2001, pp. 367–375.
• Russell Impagliazzo, Ramamohan Paturi, and Francis Zane, “Which Problems Have Strongly Exponential Complexity?” Journal of Computer and System Sciences 63(4), 2001, pp. 512–530.