强指数时间假设 SETH

形式陈述

对固定 $k\ge3$ ， $k$ -SAT 指每个子句至多含 $k$ 个文字的CNF 可满足性问题。按确定性的最坏运行时间定义

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

其中 $n$ 是变量数，时间指确定性算法的最坏运行时间， $O^*$ 隐去多项式因子。强指数时间假设断言

\lim_{k\to\infty}s_k=1.

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

SETH 蕴含ETH，但目前不知道 ETH 能否推出 SETH。两者都是尚未证明的复杂度假设，用来建立条件下界。

这个蕴含还使用稀疏化，并非仅由极限符号得出。若 $s_3=0$ ，固定任意 $k$ 与目标指数 $\rho>0$ ，先花费至多 $2^{\rho n/2}\operatorname{poly}(|F|)$ 将 $k$ -CNF 拆为线性子句分支。每个分支用标准长子句拆分变成至多 $Bn$ 个变量的3-CNF，其中 $B$ 只依赖固定的 $k,\rho$ 。由 $s_3=0$ 可选指数小于 $\rho/(2B)$ 的3-SAT算法；遍历全部分支后，总指数不超过 $\rho$ 。于是每个固定 $k$ 都有 $s_k=0$ ，与 SETH 的极限为1矛盾。

直觉

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

例子与边界

若有人给出一个固定 $\varepsilon=0.1$ ，并证明对每个 $k$ 都能在 $O^*(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$ 无关的 $\varepsilon>0$ ，使每个固定宽度的 $k$ -SAT 都能在 $O^*((2-\varepsilon)^n)$ 时间内求解。

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

SAT分半到正交向量把每条子句作为一个“这一半尚未满足”的坐标，证明点积精确等于拼接赋值违反的子句数。两个各约 $2^{n/2}$ 的列表使固定的 $N^{2-\varepsilon}$ 改进转成 $2^{(1-\varepsilon/2)n}$ ；若要求对数维度，再用稀疏化支付分支成本并保留正指数余量。

参考资料

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.

形式陈述 ​

反向链接

形式陈述