稀疏化引理

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

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

若稀疏 $k$-SAT 能在 $2^{o(n)}$ 时间求解，给定任意常数 $\eta >0$，先以 $\epsilon =\eta /2$ 稀疏化，再对至多 $2^{\epsilon n}$ 个分支运行足够快的稀疏算法，总时间仍可压到 $2^{\eta n}$ 量级。让 $\eta$ 任意小，得到的是：每个固定正指数都有相应算法，故一般 $k$-SAT 的指数率下确界为零。这已足以反驳相应的正指数率假设；若另称存在一份 $2^{o(n)}$ 时间程序，还需说明如何统一这些随 $\eta$ 变化的算法。

这个推导依赖 $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$ 的选择顺序。

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

SAT到正交向量的完整归约理路SAT分半到正交向量SAT to Orthogonal Vectors · Split-and-list SAT reduction · SAT到OV归约把每个子句编码为两侧都尚未满足的坐标，以整数点积验证SAT，并追踪SETH下的规模和稀疏化指数预算。展示一个可核算的用途：线性子句数变成相对于列表长度的对数维度。若目标每次调用带来 $\epsilon /2$ 的SAT指数改进，稀疏化参数必须取 $\eta <\epsilon /2$，最终只剩 $\epsilon /2-\eta$；取 $\eta =\epsilon /4$ 得到统一的四分之一预算。