计算理论导引 · 第 3 章：NP 完全性问题的归约证明

概述

本章整理 Karp（1972）提出的 21 个 NP 完全问题，并选取以 SAT 或 3-SAT 为规约起点的典型问题展开。

SAT问题是第一个被证明是NP 完全的问题。3SAT到SAT的规约十分简单，只要修改SAT的子句变量数（通过补充无用变量或将多个变量合并为辅助变量）即可实现。在后面的证明中，因为3SAT的形式极为规整，所以我们经常规约到3SAT上。

证明一个NP 完全问题，首先证明是NP的，即多项式时间可验证的（通常不难）；然后要将问题规约到SAT（或其他已知的NP 完全问题上），那么如何思考构造规约呢？通常可以进行以下思考：

（1）将布尔变量和子句表示成规约目标中的元素（如节点、边）

（2）构造变量选择器：模拟对一个布尔变量的0/1 赋值选择。（例如在图中添加表示变量 0/1 取值的边）

（3）构建子句验证器：保证一个子句中至少一个变量赋值为真。

（4）避免冲突：避免同时选取同一个变量的正反。

下文依次展示这些构造思想在不同问题中的运用。

由 3-SAT 出发的 NP 完全性证明

1. 0-1 线性规划

0-1 整数规划问题是一类特殊的整数规划问题，其中所有决策变量的取值只能为0或1，使得目标函数达到最优。

属于 NP

给定一个向量x，可以在多项式时间内验证是否满足约束 $Ax\leq b$ 以及计算目标函数 c^Tx 。这些步骤包括矩阵运算和向量比较，用非确定性图灵机猜测后验证可在多项式时间内完成。

多项式时间归约

1）对于每个布尔变量 x_i 转换成一个0-1变量 y_i ，将每个子句转换为线性不等式。例如：

$(x_1 \vee \neg x_2 \vee x_3)$ 可以转化为线性不等式 $y_1+(1-y_2)+y_3\geq1$ $\neg x_i$

2）每个不等式对应一个子句，解不等式可以通过赋值比较进行；对于目标函数可简单取c=0，因为这与规约无关。

2. Set Packing

给定一个集合的集合U，以及一系列子集 S1, S2, …, Sn，其中每个 Si都是 U 的子集。Set Packing 问题的目标是找到这些子集的一个子集（称为“packing”），使得 packing 中的任何两个子集都不相交（即它们的交集为空集）。

属于 NP

给定一个子集集合 S1, S2, …, Sn和一个可能的 packing P（即 P 是 {S1, S2, …, Sn} 的一个子集），验证 P 是否是一个有效的 packing 可以通过检查 P 中任意两个子集 Si和 Sj（其中 i ≠ j）的交集是否为空集来完成。这可以在多项式时间内完成，因为子集的数量是有限的，且检查集合交集可在多项式时间内完成。

多项式时间归约

假设我们有一个 3SAT 问题的实例，其中包含 m 个子句和 n 个变量 x1, x2, …, xn。

对于每个变量 x_i ，我们创建两个集合 $X_i, X_{ni}$ ，每个子句创建一个包含三个元素的集合 C_j 。如果 x_i 在某个子句出现，将对应子句的所有元素加入 X_i 中，如果 $\neg x_i$ 出现，将对应子句的所有元素加入到 $X_{ni}$ 中。

我们需要找到一个packing，它包含 $X_i, X_{ni}$ ，恰好与每个 C_j 相交。这对应于3-SAT问题中一个使结果为真的指派。变量和子句的个数都不高于多项式个，故可以在多项式时间内完成规约。

3. Exact Cover

在给定的集合系统中找出一些集合，使得这些集合的并集恰好包含所有元素，且每个元素只在一个集合中出现。

属于 NP

非确定性图灵机猜测精确覆盖问题的一个候选解（即一组集合），我们可以很容易地验证这组集合的并集是否包含所有元素且只出现一次。这个验证过程可以在多项式时间内完成，因为我们只需要遍历所有元素和集合。

多项式时间归约

给定一个3-SAT问题的实例，我们可以构造一个精确覆盖问题的实例：对于每个子句，我们创建一个集合，该集合包含代表该子句中文字（或它们的否定）的元素。然后，目标是在这些集合中找到一个子集，其并集恰好包含所有元素（即每个子句恰好被一个集合覆盖）。

如果存在一个满足的布尔赋值，则存在一个精确覆盖集（因为每个满足的子句都会有一个对应的集合）。反之亦然。

由于子句和变量数都是多项式的，所以规约构造可以在多项式时间内完成。

4. 3-Dimensional Matching

三维匹配问题（3DMatching Problem）是一种组合优化问题，它涉及三个等大小的集合X，Y，Z，以及一个三

元组集合T，其中每个三元组(x, y, z)包含来自X，Y，Z的一个元素。目标是找到T的一个子集M，使得M中的

每个三元组都是两两不相交的（即没有两个三元组共享同一个X，Y或Z集合中的元素），且M的大小最大化。

属于 NP

非确定性图灵机猜测候选解，遍历所有的(x, y ,z)，先判定是否在T中。维护一个记录表记录三个集合已使用元素的编号（多项式时间内），检查遍历的三元组中的元素是否使用过。如果条件都满足就接受，并计算M的大小。

多项式时间归约

构造三个集合，每个集合中的元素与 3-SAT 公式中的变量一一对应。具体来说，对于每个变量，我们在中分别添加表示、 $\neg v$ （的反面）和另一个新变量的元素。
对于 3-SAT 公式中的每个子句 $(l_1 \lor l_2 \lor l_3)$ （其中是文字），我们构造一个三元组，其中分别对应于所代表的变量或变量的反面。注意，如果某个文字是正面（即不是反面），则我们使用或中的相应元素；如果是反面，则使用或中的相应元素（交换和是为了确保每个变量和它的反面不会出现在同一个三元组中）。对于，我们使用与都不同的新变量。
将所有构造的三元组添加到集合中。

现在，我们可以观察到，如果存在一个满足所有子句的变量赋值，则我们可以构造一个三维匹配问题的解（即的一个子集），其中每个三元组都对应于一个被满足的子句。反过来，如果三维匹配问题有一个解，则我们可以从中提取出一个满足所有子句的变量赋值。

5. Feedback Node Set

给定一个无向图G = (V, E)，一个反馈节点集F是V的一个子集，使得从V - F（即F的补集）中删除所有顶点后，剩余的图（如果有的话）是无环的（即是一个森林）。Feedback Node Set问题的目标是找到小于给定个数k的反馈节点集F，使得G - F是无环的。

属于 NP

非确定性图灵机猜测一个顶点集F作为候选的反馈节点集，验证其是否有效（即是否使得G - F成为无环图）可以通过深度优先搜索（DFS）或广度优先搜索（BFS）遍历G - F中的所有顶点来完成。这个验证过程的时间复杂度是多项式的，因为图的顶点数和边数都是有限的。

多项式时间归约

对于3-SAT问题中的每个变量 x_i ，创建两个顶点 v_i , $v_{i}^{'}$ 分别代表变量为真假；对于每个子句 C_j 创建一个顶点 c_j ；对于 C_j 中的每个文字，如果文字是正面的（ x_i ），则添加边( c_j, v_i )，反之添加( $c_j, v_{i}^{'}$ )；对每个变量添加边( $v_i, v_{i}^{'}$ )。由于顶点和边的个数是多项式内的，所以构造可在多项式时间内完成。

如果3-SAT问题有一个解（即一个变量的赋值使得公式为真），那么在这个赋值下，对于每个子句 C_j ，至少有一个文字为真。选择所有真值指派包含的v结点和所有子句结点作为F。由于每个子句中至少有一个为真变量的赋值，所以C，V两个部分的子集不再相连，G-F中没有回路。

反之，如果Feedback Node Set问题有一个解（即一个最小的反馈节点集F），那么我们可以根据F中的顶点来为每个变量 x_i 分配一个值。由于G - F是无环的，因此每个子句顶点 c_j 都至少与F中的一个顶点相连，这意味着在3-SAT问题中，每个子句都至少有一个文字为真。

6. Clique

分团问题（Clique Problem）是一个图论问题，给定一个无向图G = (V, E)，其中V是顶点集，E是边集。分团（Clique）是图中的一个顶点子集，其中的任意两个顶点之间都有边相连。分团问题通常指的是寻找图中最大的分团（即包含顶点数最多的分团），这被称为最大分团问题（Maximum Clique Problem）。

属于 NP

给定一个顶点子集C，验证它是否是一个分团是容易的。我们只需要检查C中的任意两个顶点之间是否都存在边。这可以通过遍历C中所有顶点对并检查它们是否在边集E中来完成，这是一个多项式时间操作。

多项式时间归约

创建顶点：对公式 $\phi$ 中的每个子句，为其包含的每一个文字（如或 $\neg x_j$ ）创建一个顶点。例如，子句 $(x_1 \lor \neg x_2 \lor x_3)$ 会生成三个顶点： $(x_1, 1), (\neg x_2, 1), (x_3, 1)$ 。
创建边：

同子句内无边：来自同一个子句的任意两个顶点之间不连接。
跨子句有边：来自不同子句的两个顶点当且仅当它们的文字不冲突时才连接。所谓“不冲突”，指它们不是互为否定的关系。例如：

和 → 可连边。
和 $(\neg x_1, 2)$ → 不可连边（冲突）。

3.设定参数：令 k = m （即公式中子句的总数）。

(⇒) 如果 $\phi$ 可满足，则有大小为的团。

假设存在一个赋值使 $\phi$ 为真。那么每个子句 C_r 至少有一个文字为真。我们从每个子句中选一个为真的文字，并取其对应的顶点。这样得到m 个顶点。
由于这些顶点来自不同子句，且它们代表的文字都为真（因此不可能互相矛盾），根据建图规则，它们两两相连，构成一个大小为m的团。

(⇐) 如果有大小为的团，则 $\phi$ 可满足。

一个大小为的团必须包含个顶点。由于同一子句内的顶点无边，团中每个顶点必须来自不同的子句。我们定义一个赋值：让所有被选中的文字为真。这个赋值是合法的，因为如果两个被选中的文字冲突（如 x_i 和 $\neg x_i$ ），它们对应的顶点就不会相连，无法形成团。同时，每个子句都有一个被选中的文字为真，所以 $\phi$ 被满足。