3-SAT

3-SAT 把一般逻辑约束限制为局部的三元析取，却仍保留 SAT 的全部 NP 困难性，因为许多共享变量的小约束组合起来仍能表达全局选择困难，而困难并不来自某个巨大子句。宽度约束也使归约构件局部而规则，适合作为图、集合和调度问题的起点。把一般长子句拆分时必须引入辅助变量，以保持“存在某个扩展赋值”的等可满足性，而非逐赋值等价。

公式 $(x\vee y\vee z)\wedge (\mathrm{\neg }x\vee y\vee y)$ 是合法实例。3-SAT 不应与 2-SAT 混淆：2-SAT 可在线性时间内求解，而 3-SAT 是 NP-complete。若要求三个互异变量且不允许重复，需要额外的等可满足变换。例如二文字子句 $(a\vee b)$ 可替换为 $(a\vee b\vee u)\wedge (a\vee b\vee \mathrm{\neg }u)$：原子句为假时两项要求 $u$ 与 $\mathrm{\neg }u$ 同时为真，为真时则两项都成立。

四文字子句 $(a\vee b\vee c\vee d)$ 可用新变量 $u$ 替换为

对每个固定的原变量赋值，若 $a\vee b=1$，取 $u=0$ 即可满足两项；若左半为假而 $c\vee d=1$，取 $u=1$ 即可。若四个文字都为假，两项分别强迫 $u=1$ 与 $u=0$，无解。因此成立的是带存在量词的等式 $a\vee b\vee c\vee d\equiv \mathrm{\exists }u,[(a\vee b\vee u)\wedge (\mathrm{\neg }u\vee c\vee d)]$。

对长为 $r\ge 4$ 的子句，串联 $r-3$ 个新的辅助变量，得到 $r-2$ 个三文字子句；不同原子句使用不同新变量，才能独立选择扩展赋值。总规模只线性增加。长度为 $1$ 或 $2$ 的子句可重复文字补齐。原 CNF 若含空子句，直接输出固定矛盾 $(u\vee u\vee u)\wedge (\mathrm{\neg }u\vee \mathrm{\neg }u\vee \mathrm{\neg }u)$，覆盖这个不能靠填充处理的边界。

2-SAT 有线性时间算法，因此“每个子句常数宽”本身不导致 NP 完全；阈值恰在宽度从 $2$ 到 $3$。拆分保持的是整体可满足性，不能要求原变量每个固定赋值下新公式不经选择辅助变量便同值。

3-SAT 建立在命题逻辑理路命题逻辑Propositional logic · Propositional calculus研究命题如何通过逻辑联结词组合以及公式在真值赋值下何时成立。上，并由Cook–Levin 定理理路Cook–Levin 定理Cook–Levin theorem · SAT is NP-complete布尔可满足性问题 SAT 是 NP 完全问题。后的宽度约化得到 NP 完全性；许多图问题归约从三文字子句构造常数规模 gadget。精确时间主线固定 $n$ 为变量数：ETH理路指数时间假设 ETHExponential Time Hypothesis · ETH假设3-SAT以变量数衡量的确定性最优指数率下确界为正，从而排除次指数时间算法。排除 $2^{o(n)}$，稀疏化引理理路稀疏化引理Sparsification lemma · Sparsification lemma for k-SAT将固定宽度 CNF 分解为指数率任意小的线性规模稀疏公式析取，并保持可满足性。把稠密固定宽度公式拆成线性子句分支，SETH理路强指数时间假设 SETHStrong Exponential Time Hypothesis · SETH假设随着子句宽度增长，k-SAT 的最优指数底数不能被某个统一小于 2 的常数界定。则量化所有 $k$-SAT 的指数底数。三者是条件假设或定理，不属于 3-SAT 问题定义。