17.5
额外的 NP-完全问题
NP-完全现象普遍存在。NP-完全问题出现在许多领域。由于人们不完全了解的原因，大多数自然出现的 NP 问题要么已知属于 P 类，要么属于 NP-完全类。如果你正在为新的 NP 问题寻找多项式时间算法，那么投入部分精力尝试证明它属于 NP-完全是明智的，因为这样做可以防止你为寻找一个不存在的多项式时间算法而徒劳。
在本节中，我们介绍额外的定理，表明各种语言是 NP-完全的。这些定理提供了这类证明中使用的技术的例子。我们的通用策略是展示从 3SAT 到相关语言的多项式时间归约，尽管为了方便，我们有时会从其他 NP-完全语言进行归约。
在构建从 3SAT 到某种语言的多项式时间归约时，我们寻找该语言中可以模拟布尔公式中的变量和子句的结构。这些结构有时被称为小工具（gadgets）。例如，在从 3SAT 到 CLIQUE 的归约中（定理 7.32），单个节点模拟变量，三元组节点模拟子句。单个节点可以属于或不属于团，对应于变量可以为真或为假。每个子句必须包含一个被赋值为真的文字。相应地，每个三元组必须包含一个团中的节点（以便达到目标大小）。定理 7.32 的以下推论表明 CLIQUE 是 NP-完全的。
推论 7.43
CLIQUE 是 NP-完全的。
子句的小工具（gadgets）稍微复杂一些。每个子句小工具是一个三元组节点，它们用子句的三个文字进行标记。这三个节点相互连接，并连接到变量小工具中具有相同标记的节点。因此，$G$ 中出现的节点总数为 $2m+3l$，其中 $\phi$ 有 $m$ 个变量和 $l$ 个子句。令 $k$ 为 $m+2l$。
例如，如果 $\phi=\left(x_{1} \vee x_{1} \vee x_{2}\right) \wedge\left(\overline{x_{1}} \vee \overline{x_{2}} \vee \overline{x_{2}}\right) \wedge\left(\overline{x_{1}} \vee x_{2} \vee x_{2}\right)$，则归约从 $\phi$ 产生 $\langle G, k\rangle$，其中 $k=8$，且 $G$ 采用下图所示的形式。
图 7.45
由 $\phi=\left(x_{1} \vee x_{1} \vee x_{2}\right) \wedge\left(\overline{x_{1}} \vee \overline{x_{2}} \vee \overline{x_{2}}\right) \wedge\left(\overline{x_{1}} \vee x_{2} \vee x_{2}\right)$ 产生的图 $G$
为了证明这个归约是有效的，我们需要证明 $\phi$ 是可满足的当且仅当 $G$ 具有 $k$ 个节点的顶点覆盖。我们从一个满足赋值开始。我们首先将变量小工具中与赋值中真文字对应的节点放入顶点覆盖中。然后，我们选择每个子句中的一个真文字，并将每个子句小工具中剩余的两个节点放入顶点覆盖中。现在我们总共有 $k$ 个节点。它们覆盖了所有边，因为每个变量小工具的边都已明确覆盖，每个子句小工具内部的所有三条边都已覆盖，并且变量小工具和子句小工具之间的所有边也都已覆盖。因此 $G$ 具有 $k$ 个节点的顶点覆盖。
其次，如果 $G$ 具有 $k$ 个节点的顶点覆盖，我们通过构造满足赋值来证明 $\phi$ 是可满足的。顶点覆盖必须包含每个变量小工具中的一个节点和每个子句小工具中的两个节点，以覆盖变量小工具的边和子句小工具内部的三条边。这占据了所有节点，因此没有节点剩余。我们取顶点覆盖中变量小工具的节点，并将相应的文字赋值为 TRUE。这个赋值满足 $\phi$，因为连接变量小工具和每个子句小工具的三条边中的每一条都已覆盖，并且子句小工具中只有两个节点在顶点覆盖中。因此，其中一条边必须由来自变量小工具的节点覆盖，因此该赋值满足相应的子句。
哈密顿路径问题
回想一下 哈密顿路径问题 询问输入图是否包含一条从 $s$ 到 $t$ 且经过每个节点恰好一次的路径。
定理 7.46
HAMPATH 是 NP-完全的。
证明思路 我们在 7.3 节中证明了 HAMPATH 属于 NP。为了证明每个 NP 问题都可以多项式时间归约到 HAMPATH，我们证明 3SAT 可以多项式时间归约到 HAMPATH。我们给出一种将 3 cnf-公式转换为图的方法，其中哈密顿路径对应于公式的满足赋值。图包含模拟变量和子句的小工具（gadgets）。变量小工具是一个菱形结构，可以通过两种方式遍历，对应于两种真值设置。子句小工具是一个节点。确保路径经过每个子句小工具对应于确保满足赋值中每个子句都得到满足。
证明 我们之前已证明 HAMPATH 属于 NP，因此剩下要做的就是证明 3SAT $\leq_{\mathrm{P}}$ HAMPATH。对于每个 3 cnf-公式 $\phi$，我们展示如何构造一个有向图 $G$，其中包含两个节点 $s$ 和 $t$，当且仅当 $\phi$ 是可满足的时，存在一条从 $s$ 到 $t$ 的哈密顿路径。
我们从包含 $k$ 个子句的 3 cnf-公式 $\phi$ 开始，
其中每个 $a, b$ 和 $c$ 是文字 $x_{i}$ 或 $\overline{x_{i}}$。令 $x_{1}, \ldots, x_{l}$ 为 $\phi$ 的 $l$ 个变量。
现在我们展示如何将 $\phi$ 转换为图 $G$。我们构造的图 $G$ 包含用于表示 $\phi$ 中出现的变量和子句的各个部分。
我们用一个包含一行水平节点的菱形结构来表示每个变量 $x_{i}$，如下图所示。稍后我们将指定水平行中出现的节点数量。
图 7.47
将变量 $x_{i}$ 表示为菱形结构
我们用一个节点来表示 $\phi$ 的每个子句，如下所示。
图 7.48
将子句 $c_{j}$ 表示为节点
下图描绘了 $G$ 的全局结构。它显示了 $G$ 的所有元素及其关系，除了表示变量与包含它们的子句之间关系的边。
图 7.49
$G$ 的高层结构
接下来，我们展示如何将表示变量的菱形连接到表示子句的节点。每个菱形结构都包含一行水平节点，这些节点由双向边连接。水平行除了菱形两端的两个节点外，还包含 $3k+1$ 个节点。这些节点被分组为相邻对，每个子句一对，并在每对旁边附加分隔节点，如下图所示。
图 7.50
菱形结构中的水平节点
如果变量 $x_{i}$ 出现在子句 $c_{j}$ 中，我们从第 $i$ 个菱形中的第 $j$ 对向第 $j$ 个子句节点添加以下两条边。
图 7.51
当子句 $c_{j}$ 包含 $x_{i}$ 时附加的边
如果 $\overline{x_{i}}$ 出现在子句 $c_{j}$ 中，我们从第 $i$ 个菱形中的第 $j$ 对向第 $j$ 个子句节点添加两条边，如图 7.52 所示。
在我们添加完与每个 $x_{i}$ 或 $\overline{x_{i}}$ 在每个子句中出现的对应边后，$G$ 的构造就完成了。为了证明这个构造是有效的，我们论证如果 $\phi$ 是可满足的，则存在从 $s$ 到 $t$ 的哈密顿路径；反之，如果存在这样的路径，则 $\phi$ 是可满足的。
图 7.52
当子句 $c_{j}$ 包含 $\overline{x_{i}}$ 时附加的边
假设 $\phi$ 是可满足的。为了演示一条从 $s$ 到 $t$ 的哈密顿路径，我们首先忽略子句节点。路径从 $s$ 开始，依次经过每个菱形，并最终到达 $t$。要经过菱形中的水平节点，路径要么从左到右之字形行进，要么从右到左之字形行进；$\phi$ 的满足赋值决定了哪种方式。如果 $x_{i}$ 被赋值为真，路径之字形穿过相应的菱形。如果 $x_{i}$ 被赋值为假，路径反之字形行进。我们将在下图中展示两种可能性。
图 7.53
由满足赋值决定的菱形之字形和反之字形遍历
到目前为止，这条路径覆盖了 $G$ 中除了子句节点外的所有节点。我们可以通过在水平节点处增加绕行轻松地包含它们。在每个子句中，我们选择一个通过满足赋值被赋值为 TRUE 的文字。
如果我们在子句 $c_{j}$ 中选择了 $x_{i}$，我们可以在第 $i$ 个菱形中的第 $j$ 对处绕行。这样做是可能的，因为 $x_{i}$ 必须为 TRUE，所以路径以之字形从左到右穿过相应的菱形。因此，通往 $c_{j}$ 节点的边顺序正确，允许绕行并返回。
类似地，如果我们在子句 $c_{j}$ 中选择了 $\overline{x_{i}}$，我们可以在第 $i$ 个菱形中的第 $j$ 对处绕行，因为 $x_{i}$ 必须为 FALSE，所以路径以反之字形从右到左穿过相应的菱形。因此，通往 $c_{j}$ 节点的边同样
顺序正确，允许绕行并返回。（请注意，子句中的每个真文字都提供了绕行以到达子句节点的一个选项。因此，如果一个子句中有多个文字为真，则只进行一次绕行。）因此，我们构造了所需的哈密顿路径。
对于反方向，如果 $G$ 有一条从 $s$ 到 $t$ 的哈密顿路径，我们演示 $\phi$ 的一个满足赋值。如果哈密顿路径是正常的——即，除了到子句节点的绕行之外，它按顺序从上到下穿过菱形——我们可以很容易地获得满足赋值。如果路径之字形穿过菱形，我们将相应的变量赋值为 TRUE；如果它反之字形穿过，我们赋值为 FALSE。因为每个子句节点都出现在路径上，通过观察它是如何绕行到达的，我们可以确定相应子句中的哪个文字为真。
剩下的就是证明哈密顿路径必须是正常的。非正常情况只可能发生：路径从一个菱形进入一个子句节点，但返回到另一个菱形，如下图所示。
图 7.54
这种情况不可能发生
路径从节点 $a_{1}$ 到 $c$；但它不是返回到同一菱形中的 $a_{2}$，而是返回到不同菱形中的 $b_{2}$。如果发生这种情况，$a_{2}$ 或 $a_{3}$ 必须是分隔节点。如果 $a_{2}$ 是分隔节点，那么进入 $a_{2}$ 的唯一边将来自 $a_{1}$ 和 $a_{3}$。如果 $a_{3}$ 是分隔节点，$a_{1}$ 和 $a_{2}$ 将在同一子句对中，因此进入 $a_{2}$ 的唯一边将来自 $a_{1}$、$a_{3}$ 和 $c$。在任何一种情况下，路径都不能包含节点 $a_{2}$。路径不能从 $c$ 或 $a_{1}$ 进入 $a_{2}$，因为路径从这些节点去往别处。路径不能从 $a_{3}$ 进入 $a_{2}$，因为 $a_{3}$ 是 $a_{2}$ 指向的唯一可用节点，所以路径必须通过 $a_{3}$ 离开 $a_{2}$。因此，哈密顿路径必须是正常的。这个归约显然在多项式时间内完成，证明完毕。
接下来，我们考虑 哈密顿路径问题 的无向版本，称为 UHAMPATH。为了证明 UHAMPATH 是 NP-完全的，我们给出从该问题的有向版本到它的多项式时间归约。
定理 7.55
UHAMPATH 是 NP-完全的。
证明 归约接受一个带有节点 $s$ 和 $t$ 的有向图 $G$，并构造一个带有节点 $s^{\prime}$ 和 $t^{\prime}$ 的无向图 $G^{\prime}$。图 $G$ 具有从 $s$ 到 $t$ 的哈密顿路径当且仅当 $G^{\prime}$ 具有从 $s^{\prime}$ 到 $t^{\prime}$ 的哈密顿路径。我们描述 $G^{\prime}$ 如下。
$G$ 的每个节点 $u$，除了 $s$ 和 $t$，都被 $G^{\prime}$ 中的三元组节点 $u^{\text {in }}$、$u^{\text {mid }}$ 和 $u^{\text {out }}$ 替换。$G$ 中的节点 $s$ 和 $t$ 被 $G^{\prime}$ 中的节点 $s^{\text {out }}=s^{\prime}$ 和 $t^{\text {in }}=t^{\prime}$ 替换。$G^{\prime}$ 中出现两种类型的边。首先，边连接 $u^{\text {mid }}$ 与 $u^{\text {in }}$ 和 $u^{\text {out }}$。其次，如果 $G$ 中有从 $u$ 到 $v$ 的边，则边连接 $u^{\text {out }}$ 与 $v^{\text {in }}$。这样就完成了 $G^{\prime}$ 的构造。
我们可以通过证明 $G$ 具有从 $s$ 到 $t$ 的哈密顿路径当且仅当 $G^{\prime}$ 具有从 $s^{\text {out }}$ 到 $t^{\text {in }}$ 的哈密顿路径来证明这个构造是有效的。为了证明一个方向，我们观察到 $G$ 中的哈密顿路径 $P$，
在 $G^{\prime}$ 中有相应的哈密顿路径 $P^{\prime}$，
为了证明另一个方向，我们声称 $G^{\prime}$ 中从 $s^{\text{out}}$ 到 $t^{\text{in}}$ 的任何哈密顿路径必须从一个三元组节点到另一个三元组节点，除了起点和终点，就像我们刚刚描述的路径 $P^{\prime}$ 一样。这将完成证明，因为任何这样的路径在 $G$ 中都有相应的哈密顿路径。我们通过从节点 $s^{\text{out}}$ 开始跟踪路径来证明这个论断。观察到路径中的下一个节点必须是某个 $i$ 的 $u_{i}^{\text{in}}$，因为只有这些节点与 $s^{\text{out}}$ 连接。下一个节点必须是 $u_{i}^{\text{mid}}$，因为没有其他方式可以将 $u_{i}^{\text{mid}}$ 包含在哈密顿路径中。在 $u_{i}^{\text{mid}}$ 之后是 $u_{i}^{\text{out}}$，因为这是 $u_{i}^{\text{mid}}$ 连接的唯一其他节点。下一个节点必须是某个 $j$ 的 $u_{j}^{\text{in}}$，因为没有其他可用节点连接到 $u_{i}^{\text{out}}$。论证然后重复直到到达 $t^{\text{in}}$。
子集和问题
回想一下第 297 页定义的 子集和问题。在该问题中，我们给定一组数字 $x_{1}, \ldots, x_{k}$ 以及一个目标数字 $t$，并要求确定该集合是否包含一个子集合，其元素之和为 $t$。现在我们证明这个问题是 NP-完全的。
定理 7.56
SUBSET-SUM 是 NP-完全的。
证明思路 我们已在定理 7.25 中证明了 SUBSET-SUM 属于 NP。我们通过将 NP-完全语言 3SAT 归约到 SUBSET-SUM 来证明 NP 中的所有语言都可以多项式时间归约到 SUBSET-SUM。给定一个 3 cnf-公式 $\phi$，我们构造一个 SUBSET-SUM 问题的实例，该实例包含一个子集合，其元素之和为 $t$，当且仅当 $\phi$ 是可满足的。称此子集合为 $T$。
为了实现这个归约，我们寻找 SUBSET-SUM 问题的结构来表示变量和子句。我们构造的 SUBSET-SUM 问题实例包含以十进制表示的大数字。我们用成对的数字表示变量，用十进制表示中的某些位置表示子句。
我们用两个数字 $y_{i}$ 和 $z_{i}$ 来表示变量 $x_{i}$。我们证明对于每个 $i$，要么 $y_{i}$ 要么 $z_{i}$ 必须在 $T$ 中，这建立了满足赋值中 $x_{i}$ 真值的编码。
每个子句位置在目标 $t$ 中包含一个特定值，这给子集 $T$ 施加了一个要求。我们证明这个要求与相应子句中的要求相同——即该子句中的一个文字被赋值为真。
证明 我们已经知道 SUBSET-SUM $\in \mathrm{NP}$，所以我们现在证明 3SAT $\leq_{\mathrm{P}}$ SUBSET-SUM。
令 $\phi$ 为一个布尔公式，变量为 $x_{1}, \ldots, x_{l}$，子句为 $c_{1}, \ldots, c_{k}$。归约将 $\phi$ 转换为 SUBSET-SUM 问题的实例 $\langle S, t\rangle$，其中 $S$ 的元素和数字 $t$ 是图 7.57 中表格的行，以普通十进制表示。双线以上的行被标记为
并构成 $S$ 的元素。双线以下的行是 $t$。
因此，$S$ 为 $\phi$ 中的每个变量 $x_{i}$ 包含一对数字 $y_{i}, z_{i}$。这些数字的十进制表示分为两部分，如表中所示。左侧部分由一个 1 后面跟着 $l-i$ 个 0 组成。右侧部分为每个子句包含一位数字，其中 $y_{i}$ 在 $c_{j}$ 列中的数字为 1，如果子句 $c_{j}$ 包含文字 $x_{i}$；$z_{i}$ 在 $c_{j}$ 列中的数字为 1，如果子句 $c_{j}$ 包含文字 $\overline{x_{i}}$。未指定为 1 的数字为 0。
该表已部分填充，以说明示例子句 $c_{1}$、$c_{2}$ 和 $c_{k}$：
此外，$S$ 为每个子句 $c_{j}$ 包含一对数字 $g_{j}, h_{j}$。这两个数字相等，由一个 1 后面跟着 $k-j$ 个 0 组成。
最后，目标数字 $t$，即表格的最后一行，由 $l$ 个 1 后面跟着 $k$ 个 3 组成。
| | 12 | … | $c_{1}$ | $c_{2}$ | ⋯ | $c_{k}$ |
| :--- | :--- | :--- | :--- | :--- | :--- | :--- |
| $y_{1}$ | 1 | ⋯ | 1 | 0 | ⋯ | 0 |
| $z_{1}$ | 1 | ... | 0 | 0 | … | 0 |
| $y_{2}$ | 1 | ⋯ | 0 | 1 | … | 0 |
| $z_{2}$ | 1 | ... | 1 | 0 | … | 0 |
| $y_{3}$ | 1 | ⋯ | 1 | 1 | ⋯ | 0 |
| $z_{3}$ | 1 | ⋯ | 0 | 0 | ⋯ | 1 |
| ⋮ | | ⋱ | ⋮ | | ⋮ | ⋮ |
| $y_{l}$ | | 1 | 0 | 0 | ⋯ | 0 |
| $z_{l}$ | | 1 | 0 | 0 | … | 0 |
| $g_{1}$ | | | 1 | 0 | ⋯ | 0 |
| $h_{1}$ | | | 1 | 0 | ⋯ | 0 |
| $g_{2}$ | | | | 1 | ⋯ | 0 |
| $h_{2}$ | | | | 1 | ⋯ | 0 |
| ⋮ | | | | | ⋱ | ⋮ |
| $g_{k}$ | | | | | | 1 |
| $h_{k}$ | | | | | | 1 |
| $t$ | 1 | ⋯ | 3 | 3 | ⋯ | 3 |
图 7.57
将 3SAT 归约到 SUBSET-SUM
接下来，我们展示这个构造为什么有效。我们证明 $\phi$ 是可满足的当且仅当 $S$ 的某个子集之和为 $t$。
假设 $\phi$ 是可满足的。我们构造 $S$ 的一个子集如下。如果在满足赋值中 $x_{i}$ 被赋值为 TRUE，我们选择 $y_{i}$；如果 $x_{i}$ 被赋值为 FALSE，我们选择 $z_{i}$。如果我们把目前选择的加起来，我们会在前 $l$ 位得到一个 1，因为我们为每个 $i$ 选择了一个 $y_{i}$ 或 $z_{i}$。此外，后 $k$ 位中的每一位都是 1 到 3 之间的数字，因为每个子句都得到满足，因此包含 1 到 3 个真文字。我们另外选择足够多的 $g$ 和 $h$ 数字，使后 $k$ 位中的每一位都达到 3，从而达到目标。
假设 $S$ 的一个子集之和为 $t$。我们通过几次观察来构造 $\phi$ 的一个满足赋值。首先，$S$ 成员中的所有数字都是 0 或 1。此外，描述 $S$ 的表格中的每一列最多包含五个 1。因此，当 $S$ 的一个子集相加时，绝不会发生进位到下一列。为了在前 $l$ 列中得到一个 1，该子集必须为每个 $i$ 包含 $y_{i}$ 或 $z_{i}$，但不能两者都包含。
现在我们进行满足赋值。如果子集包含 $y_{i}$，我们将 $x_{i}$ 赋值为 TRUE；否则，我们将其赋值为 FALSE。这个赋值必须满足 $\phi$，因为在最后 $k$ 列中的每一列，和总是 3。在列 $c_{j}$ 中，最多 2 可以来自 $g_{j}$ 和 $h_{j}$，因此该列中至少有 1 必须来自子集中的某个 $y_{i}$ 或 $z_{i}$。如果是 $y_{i}$，则 $x_{i}$ 出现在 $c_{j}$ 中并被赋值为真，因此 $c_{j}$ 得到满足。如果是 $z_{i}$，则 $\overline{x_{i}}$ 出现在 $c_{j}$ 中并且 $x_{i}$ 被赋值为假，因此 $c_{j}$ 得到满足。因此，$\phi$ 得到满足。
最后，我们必须确保归约可以在多项式时间内完成。该表格的大小大约为 $(k+l)^{2}$，并且对于任何 $\phi$，每个条目都可以轻松计算。因此，总时间是 $O\left(n^{2}\right)$ 的简单阶段。
练习
7.1 回答每个部分“真”或“假”。
a. $2 n=O(n)$。
Ad. $n \log n=O\left(n^{2}\right)$。
b. $n^{2}=O(n)$。
e. $3^{n}=2^{O(n)}$。
Ac. $n^{2}=O\left(n \log ^{2} n\right)$。
f. $2^{2^{n}}=O\left(2^{2^{n}}\right)$。
7.2 回答每个部分“真”或“假”。
a. $n=o(2 n)$。
${ }^{\text {A }}$d. $1=o(n)$。
b. $2 n=o\left(n^{2}\right)$。
e. $n=o(\log n)$。
Ac. $2^{n}=o\left(3^{n}\right)$。
f. $1=o(1 / n)$。
7.3 以下哪些数字对是互质的？请展示得出结论的计算过程。
a. 1274 和 10505
b. 7289 和 8029
7.4 填写定理 7.16 中用于 上下文无关语言 识别的多项式时间算法的表格，针对字符串 $w=\mathrm{baba}$ 和 CFG $G$：
7.5 以下公式是否可满足？
7.6 证明 P 在并集、连接和补集下是封闭的。
7.7 证明 NP 在并集和连接下是封闭的。
7.8 令 $CONNECTED=\{\langle G\rangle \mid G \text{ 是一个连通的无向图 }\}$。分析第 185 页给出的算法，证明该语言在 P 中。
7.9 无向图中的三角形是 3-团。证明 $TRIANGLE \in \mathrm{P}$，其中 $TRIANGLE=\{\langle G\rangle \mid G \text{ 包含一个三角形 }\}$。
7.10 证明 $ALL_{\mathrm{DFA}}$ 在 P 中。
7.11 在两部分中，提供你的算法的时间复杂性分析。
a. 证明 $EQ_{\mathrm{DFA}} \in \mathrm{P}$。
b. 称语言 $A$ 是星封闭的，如果 $A=A^{*}$。给出一个多项式时间算法来测试 DFA 是否识别星封闭语言。（注意 $EQ_{\text {NFA }}$ 不已知在 P 中。）
7.12 如果图 $G$ 的节点可以重新排序使其与 $H$ 相同，则称图 $G$ 和 $H$ 同构。令 $ISO=\{\langle G, H\rangle \mid G \text{ 和 } H \text{ 是同构图 }\}$。证明 $ISO \in \mathrm{NP}$。