3-SAT · gadget · Karp 链

归约：把难度搬到新问题上

判定问题与 NP-complete §5 停在一块砖上：SAT 是 NP-complete，而后续问题的难度证明都不必再回到定义。本页讲那个「不必」是怎么兑现的——归约是一件很小的工具，小到只有一个方向需要记，偏偏那个方向天天被记反。

1 · 归约的方向

定义 1.1（多项式时间归约） 记 $A \le_p B$ ，若存在一个多项式时间可计算的函数 $f$ ，把 $A$ 的任意实例 $x$ 映成 $B$ 的实例 $f(x)$ ，且 $x$ 是 $A$ 的「是」实例当且仅当 $f(x)$ 是 $B$ 的「是」实例。

符号 $\le_p$ 读作「不比……难」： $A \le_p B$ 说的是 $A$ 的难度不超过 $B$ 。这一点决定了它的两种用法。

定理 1.2 若 $A \le_p B$ ，则： $B$ 有多项式算法蕴含 $A$ 有多项式算法； $A$ 没有多项式算法蕴含 $B$ 也没有。

证明前半句：给 $A$ 的实例 $x$ ，先花多项式时间算出 $f(x)$ ，再调用 $B$ 的多项式算法。两段都是多项式，合起来仍是多项式，且答案按定义 1.1 一致。后半句是前半句的逆否命题。∎

两个用法由此分开。想给新问题 $B$ 找算法，就把 $B$ 归约到一个已经会解的问题，箭头从 $B$ 出发；想证明新问题 $B$ 难，就把一个已知难的问题 $A$ 归约到 $B$ ，箭头指向 $B$ 。方向搞反的后果不是结论弱一点，而是什么都没证到：把 $B$ 归约到 SAT 只说明 $B$ 不比 SAT 难，NP 里每个问题都满足这一条。

警示 · 检查方向的土办法是问一句：构造出来的实例是谁的？证明难度时，构造出来的是目标问题（也就是那个新问题）的实例，输入才是老问题的实例。若发现自己在把新问题的实例翻译成 SAT 公式，方向已经反了。

2 · SAT 到 3-SAT

Cook–Levin 交出的 SAT 实例，clause 长度不受限。大量归约构造要求每个 clause 恰好三个 literal，归约链的第一步是把 clause 长度削平。

长度不足 $3$ 的 clause 靠重复某个 literal 补齐，重复不改变它的取值。长度 $k > 3$ 的 clause 拆成一条链： $(l_1 \vee l_2 \vee y_1)$ 、 $(\lnot y_1 \vee l_3 \vee y_2)$ 、……、 $(\lnot y_{k-3} \vee l_{k-1} \vee l_k)$ ，其中 $y_i$ 是新变量。链变量记的是「前面那截已经满足了吗」：若原 clause 中某个 $l_i$ 为真，把它之前的 $y$ 全部置真、之后的全部置假即可满足整条链；反之若原 clause 全假，链上每一条都要靠 $y$ 撑着，而 $y_i$ 与 $\lnot y_i$ 不能同时为真，链必然断在某处。

一条长 $k$ 的 clause 换来 $k-2$ 条新 clause 与 $k-3$ 个新变量，总规模的增长是线性的，满足定义 1.1 对 $f$ 的多项式要求。可满足性两侧一致，是 §1 里那个「当且仅当」的具体兑现。

3 · 3-SAT 到 independent set

这一步是整条链里唯一需要发明东西的地方。要把「变量取值」这种逻辑对象，翻译成「点与边」这种图论对象，靠的是两类gadget。

每个 clause 造一个三角形，三个点分别代表它的三个 literal。三角形内部两两连边，一个独立集在每个 clause 里就至多取到一个点。目标独立集大小定为 clause 数 $m$ ，「至多一个」就被逼成了「恰好一个」——每个 clause 都必须出一个代表。

跨 clause 的边负责一致性：literal $x_i$ 与 $\lnot x_i$ 之间连一条边。取了 $x_i$ 就不能再取 $\lnot x_i$ ，被选中的 $m$ 个 literal 之间不会自相矛盾，把它们统统置真是一份合法的 assignment，而它按构造满足每个 clause。

反过来，一份满足的 assignment 在每个 clause 里挑一个为真的 literal，这 $m$ 个点两两不相邻：同 clause 的不会同时被挑（每个 clause 只挑一个），跨 clause 的若相邻就意味着一个变量同时取了真和假。

图 3-1 · 左侧的 3-CNF 可就地改写，右侧的 independent set 实例随之重画。单击 literal 循环取值，切换 assignment 观察对应的独立集，或直接在图上挑点看它搬回去是哪一族 assignment。

教科书讲这一步时通常说「解一一对应」。把两侧都枚举出来会发现不是。本页那个三 clause 的默认实例上，满足的 assignment 有 $5$ 份，大小为 $3$ 的独立集有 $12$ 个。两个方向各有一处多对一：同一份 assignment 若在某个 clause 里让两个 literal 同时为真，就能挑出不止一个独立集；而一个独立集只钉住它提到的那几个变量，其余变量取什么都行。归约用到的只有一条更弱的性质——两侧同时有解或同时无解，这条在测试里逐个实例核对过。

4 · 同一张图的三重身份

链的后两步不再需要发明，只需换一副眼镜看同一张图。

点集 $S$ 是独立集，当且仅当补集 $V \setminus S$ 是 vertex cover。理由一行：任一条边的两端不可能都落在 $S$ 里，所以至少有一端落在补集里；反之若补集盖住了每条边， $S$ 内部就不可能剩下边。于是「有大小 $k$ 的独立集」与「有大小 $n - k$ 的 vertex cover」是同一句话， $n$ 是点数。

再取补图：原图里两两不相邻，在补图里就是两两相邻。「 $S$ 是 $G$ 的独立集」与「 $S$ 是 $\bar{G}$ 的 clique」同样是同一句话。三个问题共用一个解，差别只在读法。

图 4-1 · 整条归约链的五个阶段，绿色点是从上一阶段搬运过来的解。可单步推进，结论条给出每一步的解怎么翻译，以及实例规模的变化。

Karp 在 1972 年用这种方式一口气证明了 $21$ 个问题 NP-complete [1]，本页走的这条链是其中一段。链的价值在于它是可扩展的：任何一个能把 3-SAT 或 vertex cover 归约进去的新问题，立刻继承整条链的结论。

5 · 一个数字的分界

3-SAT 是 NP-complete，2-SAT 却在 P 里，而两者的差别只是每个 clause 少一个 literal。

原因在于长度 $2$ 的 clause $(a \vee b)$ 等价于两条蕴含 $\lnot a \to b$ 与 $\lnot b \to a$ 。整个公式因此变成一张蕴含图，可满足性等价于「没有哪个变量与它的否定落在同一个 SCC 里」，一遍 SCC 分解就能判完。长度 $3$ 的 clause 没有这种改写： $(a \vee b \vee c)$ 拆不成固定的蕴含对，一个 literal 为假只把选择范围缩到两个，仍是选择而非推导。站内的做法见 2-SAT 与蕴含图。

同样的悬崖在别处反复出现：图着色的 $2$ 色等价于 bipartite 判定， $3$ 色是 NP-complete；最短路径在 P 里，最长简单路径是 NP-hard。参数只挪一格，问题就从一侧掉到另一侧。

6 · 反方向的同一件事

站内还有一页整页在做归约，方向恰好相反。建模与归约：把问题翻译成网络流把多源多汇、点容量、DAG 最小路径覆盖、最大权闭合子图逐个翻译成流网络，得到的结论是它们都有多项式算法。

两者的构造动作没有区别：都是造实例、都要证明「原实例有解当且仅当新实例有解」。区别只在目标问题落在哪一侧。翻译到 max-flow，目标在 P 里，箭头从新问题指向老问题，得到算法；翻译到 3-SAT 的构造里，目标是 NP-complete 的，箭头从老问题指向新问题，得到难度下界。同一件工具，方向一反，结论就反。

拿到难度下界之后还剩什么可做，见近似算法与不可近似性。

7 · 参考文献

Karp, R. M. (1972). Reducibility among combinatorial problems. In R. E. Miller & J. W. Thatcher (Eds.), Complexity of Computer Computations, 85–103. Plenum Press.
Aspvall, B., Plass, M. F., & Tarjan, R. E. (1979). A linear-time algorithm for testing the truth of certain quantified boolean formulas. Information Processing Letters, 8(3), 121–123.
Garey, M. R., & Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman.