强指数时间假设 SETH

形式陈述 ​

对固定 $k\ge 3$，令

$$s_k=inf\{\delta >0:k\text{-SAT 可在 }{O}^{\ast }(2^{\delta n})\text{ 时间求解}\},$$

其中 $n$ 是变量数，$O^{\ast }$ 隐去多项式因子。强指数时间假设断言

$$\underset{k\to \mathrm{\infty }}{lim}{s}_k=1.$$

等价的常用量词形式是：对每个 $\epsilon >0$，存在某个固定子句宽度 $k$，使 $k$-SAT 不存在 $O^{\ast }((2-\epsilon {)}^n)$ 时间算法。量词顺序是“每个改进幅度对应某个足够大的 $k$”，并非每个固定 $k$ 都需要接近 $2^n$。

SETH 蕴含ETH公理库指数时间假设 ETHExponential Time Hypothesis · ETH假设以变量数 n 衡量的 3-SAT 不存在 2^{o(n)} 乘多项式因子的算法。，但目前不知道 ETH 能否推出 SETH。两者都是未证明复杂度假设，本页以 axiom 表示其作为条件下界前提的角色。

直觉 ​

固定宽度 SAT 可以利用子句结构取得底数低于 $2$ 的精确算法；SETH 认为宽度不断增大时，不存在一个统一远离 $2$ 的底数覆盖所有 $k$。它比“SAT 没有次指数算法”更精细，能把很小的指数或多项式改进转化成矛盾。

假设关心的是所有输入上的最坏时间，不是现有算法是否看起来接近穷举。即使某个 $k$ 已有 ${1.3}^n$ 算法，也只约束该 $s_k$，不会单独否定极限陈述。

例子与边界 ​

若有人给出一个固定 $\epsilon =0.1$，并证明对每个 $k$ 都能在 $O^{\ast }({1.9}^n)$ 时间解决 $k$-SAT，就直接否定 SETH。相反，只为 3-SAT 找到 ${1.2}^n$ 算法与 SETH 相容，因为假设允许小宽度拥有显著更低底数。

SETH 不声称 SAT 必须逐一检查全部 $2^n$ 个赋值，也不排除 $2^n/n^{100}$、${1.999}^n$ 只适用于部分宽度或随机实例的改进。要否定它，需要同一低于二的底数对所有固定宽度成立。

把 $n$ 改成子句数或编码长度会改变指数常数；引用下界时必须追踪归约对变量数的膨胀。随机化 SETH、非确定 SETH 等变体还改变算法模型，不能由本页的确定性版本自动推出。

推论与应用 ​

SETH 是细粒度复杂度中编辑距离、正交向量、动态规划状态数等条件下界的常见起点。有效归约必须定量说明：目标算法的改进如何变成对某个 $k$-SAT 的统一 $(2-\epsilon {)}^n$ 算法。

与 ETH 只排除次指数不同，SETH 对指数底数作极限约束，因此可排除看似很小但固定的改进。结论越精细，规模计算越不能省略。

参考资料

• Russell Impagliazzo and Ramamohan Paturi, “On the Complexity of k-SAT,” Journal of Computer and System Sciences 62(2), 2001, pp. 367–375.
• Virginia Vassilevska Williams, “On Some Fine-Grained Questions in Algorithms and Complexity,” Proceedings of the ICM 2018, Vol. 3, pp. 3447–3487.