稀疏化引理

形式陈述 ​

对每个固定 $k\ge 2$ 和任意 $\epsilon >0$，存在常数 $C=C(k,\epsilon )$ 与算法，把含 $n$ 个变量的 $k$-CNF 公式 $F$ 在 $2^{\epsilon n}\mathrm{poly}(n)$ 时间内写成

$$F\equiv \underset{i=1}{\overset{T}{\bigvee }}{F}_i,T\le 2^{\epsilon n},$$

其中每个 $F_i$ 仍是同一变量集上的 $k$-CNF，子句数至多 $Cn$，并可保证每个变量出现次数受只依赖 $k,\epsilon$ 的常数界。因而 $F$ 可满足当且仅当至少一个 $F_i$ 可满足。这里的 $k$ 和 $\epsilon$ 在分析中固定，$C$ 可以随二者急剧增长。

算法反复寻找导致高出现次数的 sunflower 型子句结构，并分支：一支令公共 core 被满足，另一支令 core 文字取反后保留 petals 的剩余约束。每次分支减少某个复杂度度量，最终每个叶公式稀疏；分支数通过选择阈值控制在 $2^{\epsilon n}$ 内。完整证明的重点是该度量与分支计数，而非简单删除重复子句。

直觉 ​

稠密公式看似有远多于线性的局部约束，稀疏化引理说明这些约束可以被少量“指数但指数率任意小”的分支吸收。每个分支内部只剩线性规模、受界出现次数的核心，原公式的困难性没有因稠密编码被夸大。

分解不是一个多项式大小压缩：$T$ 通常仍是指数。它的用途是精细抵消指数时间——先付 $2^{\epsilon n}$ 的任意小指数率，再在每个稀疏实例上运行假设的更快算法。

例子与边界 ​

若稀疏 $k$-SAT 能在 $2^{o(n)}$ 时间求解，给定任意常数 $\eta >0$，先以 $\epsilon =\eta /2$ 稀疏化，再对至多 $2^{\epsilon n}$ 个分支运行足够快的稀疏算法，总时间仍可压到 $2^{\eta n}$ 量级。让 $\eta$ 任意小，就得到一般 $k$-SAT 的次指数算法。

这个推导依赖 $k$ 固定。若 $k$ 随 $n$ 增长，常数 $C(k,\epsilon )$ 和分支分析不再给同一结论。分支数也不是多项式；把 $2^{\epsilon n}$ 写成“少量实例”而省略指数，会误报算法复杂度。

引理只产生等价稀疏分解，不直接决定哪个分支可满足，也不是 SAT 求解器本身。线性子句数不表示问题容易：3-SAT公理库3-SAT3-SAT · Three-satisfiability每个子句恰含三个文字的合取范式可满足性问题。 的困难性在稀疏实例上仍可保留。

推论与应用 ​

稀疏化引理连接以变量数和子句数表达的 ETH 下界，并让归约从线性规模 SAT 实例出发控制目标实例大小。与SETH公理库强指数时间假设 SETHStrong Exponential Time Hypothesis · SETH假设随着子句宽度增长，k-SAT 的最优指数底数不能被某个统一小于 2 的常数界定。结合时，仍需固定宽度并正确排列 $\epsilon$ 与 $k$ 的选择顺序。

它也解释了为何大量重复或高度重叠子句不应人为放大输入困难度：这些密集局部结构可以通过受控分支拆解，真正的指数障碍集中在稀疏核心。

参考资料

• 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.
• Marek Cygan et al., Parameterized Algorithms, Springer, 2015, Ch. 14, ETH and the sparsification lemma.