NP与计算的难解性

在计算模型中，假设问题X可以在多项式时间内求解。如果有一个解决问题X的“黑盒子”，假设通过多项式次调用解问题X的黑盒子，可以解决问题Y，则说明问题X有足够的能力解决问题Y，称作“Y多项式时间可以归约到X”。
记作： $Y \leq_p X$ ，读作“Y多项式时间可以归约到X”或者“X至少像Y一样难。”
则，我们可以得到以下定理：
定理1.假设 $Y \leq_p X$ ，如果可以在多项式时间内求解，则也可以在多项式时间内求解。
定理2.设 $Y \leq_p X$ ，如果不能在多项式时间内解决，则X也不能在多项式时间内解决。

1.3 独立集与顶点覆盖之间的归约

【独立集问题（Independent set）】
一个独立集（也称为稳定集）是一个图中一些两两不相邻的顶点所形成的集合。即顶点集合的任意两个点之间没有边。如图1，红色的点集合都是独立集，任意两个红色的顶点没有边。
NP与计算的难解性
图1 独立集（红色）
【顶点覆盖问题】
图的顶点覆盖也是一个点的集合。图中每一条边都至少有一个顶点在点集合中。如图2，黑色的点集合都是顶点覆盖集合，图的每一条边都至少有一个顶点在点集合中。
NP与计算的难解性
图2 顶点覆盖集（黑色）
【独立集与顶点覆盖之间的归约】
独立集问题：给定图G和数k，问G包含大小至少为k的独立集吗？
顶点覆盖问题：给定图G和数k，G是否包含大小为k的顶点覆盖？
证明两个问题的难度是等价的。
定理3：设 $G=(V,E)$ 是一个图， $S\subseteq V$ ，则S是一个独立集当且仅当它的补图V-S是一个顶点覆盖。
证明：
设S是一个独立集，考虑任意的一条边，因为S是独立集，则u和v不可能都在S中，因此u和v必有一个在V-S中。则每一条至少有一个端点在V-S中，即V-S是一个点覆盖集合。
反过来，假设V-S是一个顶点覆盖。考虑S中的任意两个顶点u和v，如果它们之间有一条边e，则e的两个端点都不在V-S中，则与假设V-S是一个顶点覆盖矛盾。因此，S中的任何两个顶点之间都没有边，则S是一个独立集。
【独立集 $\leq_p$ 顶点覆盖】
证明：如果有一个解顶点覆盖的黑盒子，则通过问黑盒子G是否有大小至多为n-k的顶点覆盖，可以确定G是否有大小至少为k的独立集。
【顶点覆盖 $\leq_p$ 独立集】
证明：如果有一个解独立集的黑盒子，则通过问黑盒子G是否有大小至多为n-k的独立集，就能够确定G是否有大小至少为k的独立集。

1.4 顶点覆盖到集合覆盖的归约

对于顶点覆盖问题，可以看做是“覆盖问题”，目标是用尽可能少的顶点“覆盖”图中所有的边。
【集合覆盖问题】
集合覆盖问题可以描述为：
给定 n 个元素的集合U,U 的子集 $S_1,…,S_m$ 以及数 k, 问在这些子集中有一组子集，它的并等于整个 U 且至多含有 k 个子集？
如图3为一个集合覆盖问题的实例。
NP与计算的难解性
图3 集合覆盖问题实例
在图3中，有3个子集（即数k为3）{ $S_3,S_4,S_5$ },它的并等于整个 U。
【顶点覆盖 $\leq_p$ 集合覆盖】
顶点覆盖问题可以归约到集合覆盖问题。
即：如果有一个解集合覆盖的黑盒子，通过输入顶点覆盖的一个实例，调用这个黑盒子，能够解决顶点覆盖问题。
可以使用这样的构造方法：对于每一个顶点 $i \in V$ ，设集合 $S_i \subseteq U$ 为 $G$ 中所有与顶点 $i$ 相连的边。则根据此方法，对每一个顶点构建集合。
则 $U$ 能够被 $S_1,S_2,S_3,...,S_n$ 中至多 $k$ 个集合覆盖当且仅当 $G$ 有大小至多为 $k$ 的顶点覆盖。
因为如果 KaTeX parse error: Expected '}', got 'EOF' at end of input: …i_3},...,S_{i_l 是 $l \leq k$ 个覆盖 $U$ 的集合，那么 $G$ 中的每一条边都可以关联到顶点 $i_1,i_2,i_3,...,i_l$ 中的一个，所以 { $i_1,i_2,i_3,...,i_l$ } 是 $G$ 中大小为 $l \leq k$ 的顶点覆盖。
因此，给定顶点覆盖的实例，利用上述构造方法构造集合覆盖的实例，并且将它输入黑盒子，回答yes当且仅当黑盒子回答yes。

1.5 独立集到集合包装的归约

对于独立集问题，可以看做是“包装问题”，它的目的是装入更多的顶点。
【集合包装问题】
集合包装问题可以描述为：
给定 $n$ 个元素的集合 $U$ , $U$ 的子集 $S_1,S_2,...,S_m$ 以及数 $k$ , 问在这些子集中至少含有 $k$ 个集合两两不相交？
【独立集 $\leq_p$ 集合包装】
集合覆盖是顶点覆盖的自然推广，集合包装是独立集的自然推广。使用同样的构造方法和相似的证明方法，能够证明独立集问题可以归约到集合包装问题。

2 可满足性问题

2.1 SAT和3-SAT

【SAT问题】
将布尔可满足性问题（Boolean satisfiability problem）叫做SAT：
给定变量集 $X=$ { ${x_1,x_2,...,x_n}$ } 上的一组子句 $C_1,C_2,...,C_n$ ，问存在满足的真值赋值吗？
例如，设有3个子句： $(x_1 \vee \overline {x_2} ),(\overline {x_1} \vee \overline {x_3} ),(x_2 \vee \overline {x_3} )$ ,那么如果让所有的变量都为1，则不能够满足所有的子句，因为第二个子句的值为0。
【3-SAT问题】
3-SAT问题也叫作三元可满足性问题。因为每个子句恰好包含三个项。
3-SAT问题可以描述为：
给定变量集 $X=$ { ${x_1,x_2,...,x_n}$ } 上的一组子句 $C_1,C_2,...,C_n$ ，每一个子句的长度为3，问存在满足的真值赋值吗？

2.2 3-SAT归约到独立集问题

【3-SAT $\leq_p$ 独立集】
要证明3-SAT问题可以归约到独立集，就需要证明，有一个关于独立集的黑盒子，通过解3-SAT实例，能够解3-SAT问题。
图4为从3-SAT到独立集归约的一个实例。
NP与计算的难解性
图4 从3-SAT到独立集的归约
对于一个子句来说，只要有一项的值为真，则整个子句的值为真。
则，根据子句可以这样构造图：对于每一个子句，创建三个点，将三个点连接成三角形（如上图）。若存在两个子句中有 $x_1$ 和 $\overline x_1$ ,则在这两个节点之间添加一条边（称为冲突变，即这两边不能同时被选到）。
则，存在一个真值赋值，当且仅当在每个子句中拿一个节点，且有一个大小为m（子句个数）的独立集。
例如，在图4中，有大小为3的独立集{ $x_1,x_3, x_4$ },分别取这三个值为1，可以使得所有子句的真值都为1，即子句的合取为1，这组子句是可满足的。

2.3 归约的传递性

归约之间存在传递性。
定理4.如果 $X \leq_p Y, Y \leq_p Z,$ ,则 $X \leq_p Z$ 。
通过上述归约，可以得到：
3-SAT $\leq_p$ 独立集 $\leq_p$ 顶点覆盖 $\leq_p$ 集合覆盖

3 P、NP问题

3.1 P（polynomial time）问题

对于一个计算问题，将其输入编码成有穷的二进制串s。判定问题接收输入串s，并返回“yes”或者“no”。这个返回值记为A(s)。若存在多项式函数p，使得对每一个输入串s，算法A对s的计算至多在O(p(|s|))步终止，则称A有多项式运行时间。P问题就是能在多项式时间内解决的问题。P指Polynomia。

3.2 NP(nondeterministic polynomial time)问题

为了验证一个一个解，需要输入串s以及另外的“证书”串t。如果下述两条性质成立，则称B是问题X的有效验证程序：
（1）B是有两个输入变量s和t的多项式时间算法。
（2）存在多项式p使得对每一个输入串s，A(s)=yes当且仅当存在串t使得|t|≦p(|s|)且B(s,t)=yes。
NP问题就是能在多项式时间验证答案正确与否的问题，即所有存在有效验证程序的问题的集合。

3.3 P问题与NP问题的关系

定理5. $P \subseteq NP$ .
即，所有的P问题都是NP问题。当一个问题是P问题时，我们可以在多项式时间内求出问题的解。若要验证一个解（记为t1）是否正确时，只需使用多项式时间求解出这个问题的解（记为t2），然后将t1和t2做比较即可验证答案是否正确。即，可以利用多项式时间验证答案正确与否。因此，P问题也是NP问题。可以看到，三元可满足性问题（3-SAT）、独立集问题、集合覆盖问题都是NP问题。
【讨论：P=NP?】
对于这个问题，还没有人利用一种有效的方法证明。目前计算机界普遍相信P≠NP。所以P问题是NP问题的真子集。

4 NPC问题（NP完全问题）

在是否P=NP的问题没有进展的情况下，人们转向一个相对的，更加好处理的问题：哪些是NP中最难的问题？

4.1 NPC（NP-Complete）问题

若一个问题X是NP问题，且对于所有的 $Y \in NP,Y \leq_p X$ 。即NP中的每一个问题都可以归约到X，则称问题X是NP完全问题。
✿于是，可以得到，如果NP中有一个问题不是多项式时间内可以解决的，则所有的NP完全问题都不是多项式时间内可以解决的。
并且，如果 $Y$ 是一个 $NP$ 完全问题， $X$ 属于 $NP$ ，且 $Y \leq_p X$ ，则 $X$ 是 $NP$ 完全的。

4.2 电路可满足性问题是NPC问题

【电路可满足性问题】
电路可满足性问题（Circuit satisfiability problem）描述为：给定一个电路，需要确定是否存在对输入的赋值使得输出值为1。如果存在这样的赋值，则称这个电路是可满足的。这个赋值也被称为一个满足的赋值。如图5为电路可满足性问题的一个实例。
NP与计算的难解性
图5 电路可满足性问题
图中的左边，从上到下依次是或门、非门。图中的右边是与门。当1和2输入都为1,3输入为0的时候，输出为1。即这个电路是满足的。
定理6.电路可满足性问题是NPC问题。
电路可满足性问题是NPC。这个定理是Cook和Levin于1971年提出的。
证明电路可满足性问题是NPC的，根据NPC定义，需要证明以下两点：
（1）电路可满足性问题是NP问题。
（2）所有的NP问题都可以归约到电路可满足性问题。
证明：
（1）对于电路的每一个输入，只需要验证其结果是否是1即可。因此能够在多项式时间内验证答案是否正确。即电路可满足性问题是NP问题。
（2）对于一个问题，可以将输入的实例s和证书t，构造一个输入长度为（|s|+|t|）的电路。即有(|s|+|t|)个源结点（输入结点）。很容易看到，一定有办法设计电路，使得电路的输出为1。即电路是可满足的。表明所有的NP问题都可以归约为电路可满足性问题。
因此，电路可满足性问题是NPC问题。

4.3 三元可满足性问题是NPC问题

定理7.如果 $Y$ 是一个 $NP$ 完全问题， $X$ 属于 $NP$ ，且 $Y \leq_p X$ ，则 $X$ 是 $NP$ 完全的。
之前已经证明3-SAT是一个NP问题，可以通过证明电路可满足性 $\leq_P$ 3-SAT，来证明它是NP完全的。
【电路可满足性 $\leq_P$ 3-SAT】
对于一个电路K，对于电路的每一个结点v，关联一个变量 $x_v$ , $x_v$ 表示在该结点的真值。电路K的门计算有3种：与、或、非。
如果某个结点v是非门，则它的唯一进入边来自于结点u，那么必须要有 $x_v= \overline x_u$ ,可以通过添加两个子句( $x_v \vee x_u$ )或( $\overline x_v \vee \overline x_u$ )来保证这一点。
如果某个结点v是或门，则它的2个边分别来自于结点u和w，那么必须要有 $x_v= x_u \vee x_w$ ,可以通过添加三个子句( $x_v \vee \overline x_u$ )、( $x_v \vee \overline x_w$ )或( $\overline x_v \vee x_u \vee x_w$ )来保证这一点。
如果某个结点v是与门，则它的2个边分别来自于结点u和w，那么必须要有 $x_v= x_u \wedge x_w$ ,可以通过添加三个子句( $\overline x_v \vee x_u$ )、( $\overline x_v \vee x_w$ )或( $x_v \vee \overline x_u \vee \overline x_w$ )来保证这一点。
对于源结点，保证其等于规定的值，可以对每个源结点v添加一个只含有一个项 $x_v$ 或 $\overline x_v$ 的子句，强迫其取规定的值。对于输出结点，添加一个单变量子句，让其取1。于是完成了构造。
可以证明构造的SAT实例是等价于与给定的电路可满足性实例的。
由于我们要证明电路可满足性 $\leq_P$ 3-SAT，因此还需要将子句转换为恰好有3个变量的实例。
对于只有一个项t的子句，可以将子句替换成( $t \vee z_1 \vee z_2$ )；
对于有2个项的子句( $t \vee t'$ )，可以替换成( $t \vee t' \vee z_1$ )。
显然，为了保证新构造的子句等价于原来的子句，需要保证 $z_1=z_2=0$ 。
为了保证 $z_1=z_2=0$ ，对于i=1和2，可以添加子句( $\overline z_i \vee z_3 \vee z_4$ )，( $\overline z_i \vee \overline z_3 \vee z_4$ )，( $\overline z_i \vee z_3 \vee \overline z_4$ )，( $\overline z_i \vee \overline z_3 \vee \overline z_4$ )，保证 $z_1=z_2=0$
从而完成了电路K到3-SAT的构造。因此电路可满足性 $\leq_P$ 3-SAT。证毕。
因此，根据3-SAT $\leq_p$ 独立集 $\leq_p$ 顶点覆盖 $\leq_p$ 集合覆盖，可以得到独立集、顶点覆盖、集合包装、集合覆盖问题都是NPC问题。

4.4 证明NPC问题的通用策略

给定一个基本的问题X，证明其是NPC的基本策略是：
（1）证明X是一个NP问题。
（2）选择一个已知的NPC问题Y。
（3）证明 $Y \leq_p X$ 。

5 排序问题

主要介绍哈密顿圈、巡回售货员问题这两个排序问题。

5.1 巡回售货员问题

【巡回售货员问题】
有一位巡回售货员，他必须访问n个城市，分别记作 $v_1,v_2,v_3,...,v_n$ ，售货员从他所居住的城市 $v_1$ 出发，想找一条旅行路径，访问所有的其他城市最后回到家的顺序。目标是整个旅行路径的距离尽可能的小。
对于每一对城市( $v_i,v_j$ )，城市的距离为 $d(v_i,v_j)$ 。并且，距离不是对称的，即 $d(v_i,v_j) \neq d(v_j,v_i)$ 。也不要求距离之间满足三角不等式。因此巡回售货员问题的目标是使得总距离 $\sum_{j=1}^{n-1}d(v_{i_j},v_{i_{j+1}})+d(v_{i_n},v_{i_1})$ 最小。
巡回售货员问题的判定形式为：给定n个城市之间的距离的集合以及界限D，问有长度不超过D的路线吗？

5.2 哈密顿圈问题

【哈密顿圈问题】
对于一个有向图G=(V,E),如果G中的圈C恰好经过每一个顶点一次，则称圈C是一个哈密顿圈。即，哈密顿圈构成一条经过所有的顶点，没有重复的“路线”。如图6是一个含有哈密顿圈的图。
NP与计算的难解性
图6 一个含有哈密顿圈的有向图

5.3 哈密顿圈问题是NP完全的

证明哈密顿圈问题是NPC的，可以通过证明3-SAT $\leq_p$ 哈密顿圈来得到。
【3-SAT $\leq_p$ 哈密顿圈】
构造方法如下:
(1)对于每一个变量 $x_i$ ,创建3m+3个顶点。命名为 $v_{i,1},...,v_{i,3m+3}$ ，并且对相邻的顶点，添加边( $v_{i,j},v_{i,j+1}$ )和( $v_{i,j+1},v_{i,j}$ )。如图中7中红色的点和绿色的边。如果 $x_i$ 为1，则路径 $P_i$ 从左到右。反之，如果 $x_i$ 为0，则路径 $P_i$ 从右到左。
（2）对于每一个变量，添加边 $(v_{i,1},v_{i+1,1})$ , $(v_{i,1},v_{i+1,3m+3})$ , $(v_{i,3m+3},v_{i+1,1})$ , $(v_{i,3m+3},v_{i+1,3m+3})$ 。
（3）添加两个节点s,t。添加边 $(s,v_{1,1})$ , $(s,v_{1,3m+3})$ , $(v_{3m+3,1},t)$ , $(v_{3m+3,3m+3},t)$ 。
（4）添加边 $(t,s)$ 。
构造后的图如图7所示。
NP与计算的难解性
图7 3-SAT到哈密顿圈的归约，第1部分
在图7中，可以看到有哈密顿回路：从t出发到达s，s再经过 $P_{i}$ ，最后到达t，记为A。
之后对子句进行约束。
（5）对于每个子句 $C_a$ ，假设子句为 $C_1=x_1 \vee \overline x_2 \vee x_3$ ，则这个子句表示哈密顿圈首先由左到右通过 $P_1$ ，然后由右向左通过 $P_2$ ，最后由左向右通过 $P_3$ 。如图8所示，添加点和边。
NP与计算的难解性
图8 3-SAT到哈密顿圈的归约，第2部分
可以看到，图中有哈密顿圈当且仅当3-SAT实例有满足的赋值。
证明：假设3-SAT实例有满足的赋值，则给出的哈密顿圈中，如果在满足的赋值中 $x_i$ 为1，则由左到右通过 $P_{i}$ ，反之由右到左通过 $P_{i}$ 。对于每一个子句，因为其是被满足的，所以至少有一条路径是按照与该项相关的“正确”的方向通过的。从而添加的子句顶点在哈密顿圈中能够被通过。反之，假设图G中有一个哈密顿圈，则所有添加的子句顶点（图8添加的点）都会被通过。即所有的子句都被满足。
因此，可以得到3-SAT实例是可满足的当且仅当G有哈密顿圈。证明了3-SAT $\leq_p$ 哈密顿圈。因此哈密顿圈问题是NPC的。

5.4 巡回售货员问题是NP完全的

首先，很容易证明巡回售货员问题是一个NP问题，其验证程序可以多项式时间内验证对应的路线的长度是否超过了给定的界限。
可以通过证明哈密顿圈 $\leq_p$ 巡回售货员，证明巡回售货员问题是NP完全的。
【哈密顿圈 $\leq_p$ 巡回售货员】
对于一个有向图 $G=(V,E)$ ,规定下述巡回售货员问题实例：对于图中的每一个点 $v_i$ ，有一个城市 $v_{i}’$ 。如果在G中有边，则 $d(v_i',v_j')=1$ ，否则 $d(v_i',v_j')=2$ 。
则，G中有哈密顿圈当且仅当这个巡回售货员问题中有长度不超过n的巡回路线。
因此，哈密顿圈 $\leq_p$ 巡回售货员，巡回售货员问题是NPC的。

5.5 哈密顿路径问题

【哈密顿路径问题】
哈密顿路径问题是哈密顿圈问题的变种。如果有向图G中的路径P恰好包含每一个顶点一次，则称为是一条哈密顿路径。

5.6 哈密顿路径问题是NP完全的

证明哈密顿路径是NP完全，可以通过3-SAT归约到哈密顿路径。这与3-SAT归约到哈密顿问题是很相似的（只是没有t到s的边）。

6 划分问题

讨论两个划分问题，一个是三维匹配问题，另一个是图着色问题。对于三维匹配问题，要求搜索把对象集合分成子集的方式。对于图着色问题，要求划分图中的结点。

6.1 三维匹配问题

【三维匹配问题】
给定三个不相交的集合X、Y、Z，三个集合的大小都为n。给定一个三元组集合 $T \subseteq X \times Y \times Z$ ，集合T的大小为m。
问：T中是否存在一个大小为n的子集T’，这个子集恰好包含X,Y,Z每个元素一次。
三维匹配问题其实是集合覆盖和集合包装问题的特例。

6.2 三维匹配问题是NP完全的

首先，很容易证明三维匹配问题是NP问题。只需要判断集合T’的大小是否为n，且包含X,Y,Z中每个元素一次。证明三维匹配问题是NPC的，可以通过3-SAT $\leq_p$ 三维匹配证明。
【3-SAT $\leq_p$ 三维匹配证明】
考虑任意的一个3-SAT实例，有n个变量 $x_1,x_2,...,x_n$ 和k个子句 $C_1,C_2,...,C_n$ 。构造3DM实例X,Y,Z,T。
对于每一个变量，都有一个零件相对应。如图9所示。每个零件有Core（核心）元素、Tip（边梢）元素、Triple元组。每一个零件大大小为2k。k为子句的大小。
则，对于每一个变量 $x_i$ ，建立：
$A_i={a_{i,1},a_{i,2},...,a_{i,2k}}$ 。
$B_i={b_{i,1},b_{i,2},...,b_{i,2k}}$ 。
$t_{i,j}={(a_{i,j},a_{i,j+1},b_{i,j}}$ 。
构造的零件如图9所示。
NP与计算的难解性
图9 三维匹配的零件
对于每一个子句 $C_t$ 加入两个元素 $P_t,P_t'$ ，如果 $C_{t}$ 包含 $x_{j}$ ，则加入三元组 $P=(P_t,P_t',b_{j,2t})$ ，显然一个 $C_i$ 有三个三元组。
如果包含 $\overline x_j$ ，则加入 $P=(P_t,P_t',b_{j，2t-1})$ ；所以每个子句的三元组所包含的tip元组是不冲突的。即 $C_i$ 和 $C_j$ 的三元组中没有相同的b元素。如图10所示。
NP与计算的难解性
图10 从3-SAT到三维匹配的归约，第一部分
定义，如果 $t_{ij}$ 中的j为偶数，则称 $t_{ij}$ 为偶三元组，如果j为奇数，则 $t_{ij}$ 为奇三元组。
如果 $b_{i,j}$ 中的j为偶数，则称 $b_{i,j}$ 为偶tip，如果j为奇数，则称 $b_{i,j}$ 为奇tip。
可以看到，要想core元素都被包含，且不被重复包含，则必须要么选择全部的偶三元组，要么选择全部的奇三元组。定义如果选择了全部的偶三元组，则 $x_{i}=0$ ，否则， $x_i=1$ 。
因此，可以看到，如果一个子句为1，则必然有一项的值为1，即选择该变量的所有奇三元组或所有偶三元组中。如果3-SAT是可满足的，则每个 $C_t$ 的3个三元组中，至少有一个能够被选择。
对于每个没有被选择的tip元素，添加cleanup零件： $Q={q_i,q_i'}$ 。即有 $(n-1)k$ 个tip等待覆盖。并且添加三元组 $(b_{i,j},q_i,q_i')$ 。
如图11完成了3-SAT到三维匹配的归约。
NP与计算的难解性
图11 从3-SAT到三维匹配的归约，第二部分
此时，我们令：
$X=$ { $a_{i,j}(j是偶数)$ } $\vee$ { $p_j$ } $\vee$ { $q_j$ } 。
$Y=$ { $a_{i,j}(j是奇数)$ } $\vee$ { $p_j'$ } $\vee$ { $q_j'$ } 。
$Z=$ { $b_{i,j}$ } 。
$T=$ {所有构造出来的三元组}。
可以看到，X，Y，Z三个集合的大小是相等的。
【对于每一个3-SAT实例】
假设有一个真值赋值，则如果 $x_i=1$ ，则选择 $x_i$ 对应的变量零件的所有奇三元组。若果 $c_j$ 包含 $x_i$ ，则 $c_j$ 为1，则选择 $(p_j,p_j',b_{t,2j})$ ，因为 $b_{t,2j}$ 为偶tip，因此没有被覆盖。如果 $x_i=0$ ，则选择 $x_i$ 对应的变量零件的所有偶三元组。若果 $c_j$ 包含 $\overline x_i$ ，则 $c_j$ 为1，则选择 $(p_j,p_j',b_{t,2j-1})$ ，因为 $b_{t,2j-1}$ 为奇tip，因此没有被覆盖。剩余没有被选中的tip元组被cleanup零件覆盖。
因此最终所有的元素都只被覆盖一次。
因此一个完美的三维匹配为：
$T=$ {变量中选择的三元组} $\vee$ {子句中选择的三元组} $\vee$ {cleanup中的三元组}
【对于一个三维匹配实例】
如果有一个完美三维匹配，则每个子句零件中的3个元组必须有一个被选择，则 $c_j$ 为1。如果被选择的子句三元组中有偶tip，则说明该项的值为1，否则，该项的值为0。即存在一个可满足的真值赋值。此时，已经完成了3-SAT到三维匹配的证明。因此，三维匹配问题是一个NPC问题。

6.3 图着色问题

【图着色问题】
在图着色问题中，试图给图G中的每一个结点分配颜色，使得如果(u,v)是一条边，则边的两个结点的颜色不同。目标是使用很少的几种颜色做到这一点。使用的颜色数量为k。图着色问题可以阐述为：任意给图G和界限k，问G有k-着色吗？

6.4 三着色问题是NP完全的

有一个图G是二可着色的当且仅当它是二部图（这里不对齐进行证明）。对于3种颜色的情况，已经比较复杂了。三着色问题其实是一个NP完全问题。首先很容易证明其是一个NP问题。这里通过证明3-SAT $\leq_p$ 三着色，来证明三着色问题是NPC的。
【3-SAT $\leq_p$ 三着色】
首先对于每一个变量，添加结点 $v_i$ 和 $\overline v_i$ 。添加结点T（真结点）、F（假结点）、B（基点）。用边连接每一对结点 $v_i$ 和 $\overline v_i$ 。再连接这些结点与基点。也将真结点、假结点、基点连接起来。如图12所示。
NP与计算的难解性
图12 三着色问题的归约的开始部分
于是，在G的任何三着色中，结点 $v_i$ 和 $\overline v_i$ 必须着不同的颜色，并且都必须与基点的颜色不同。
在G的任何三着色中，真结点、假结点和基点一定以某种顺序得到全部的3种颜色。可以根据什么结点得到什么颜色原则，使得这3个结点分别得到真色、假色和基色。因此 $v_i$ 和 $\overline v_i$ 中只有一个得到真色，另一个得到假色。
考虑子句 $x_1 \vee \overline x_2 \vee x_3$ ，即这个 $x_1$ , $\overline x_2$ , $x_3$ 三个结点中至少有一个着真色。现在插入一个小子图，使得任何能扩展到该小子图的三着色必须至少给 $x_1$ , $\overline x_2$ , $x_3$ 着一个真色。
这样的子图如图13所示。
NP与计算的难解性
图13 附加的子图
则，必须至少给 $x_1$ , $\overline x_2$ , $x_3$ 着一个真色，才能使得子图实现三着色（否则会出现颜色冲突）。如图14为子图的三着色实例。

图14 子图的三着色方案
可以论证3-SAT实例时可满足的当且仅当子图有三着色方案。即3-SAT $\leq_p$ 三着色，因此三着色问题是NPC的。

7 数值问题

7.1 子集和问题

【子集和问题】
给定自然数 $w_1,w_2,...,w_n$ 和目标值W，问{ $w_1,w_2,...,w_n$ }有一个子集加起来恰好等于W吗？
Ex: { 1, 4, 16, 64, 256, 1040, 1041, 1093, 1284, 1344 }, W = 3754.
Yes. 1 + 16 + 64 + 256 + 1040 + 1093 + 1284 = 3754.

7.2 子集和问题是NP完全的

首先证明子集和问题是NP的。给定自然数和目标W，直接求子集中元素的合，判断是否等于W。因此可以在多项式时间内验证答案是否正确。
可以通过证明三维匹配 $\leq_p$ 子集和，证明子集和问题是一个NPC问题。
【三维匹配 $\leq_p$ 子集和】
对于三维匹配的T中的每一个元素 $t_a=(x_i,y_j,z_k)$ ，新建一个3n（n为自然数的个数）位的d进制串（d=m+1）,3n位对应X、Y、Z的3n个元素。置第i位，第n+j位，第2n+k位为1，其他位为0。用10进制表示，则 $w_n=d_{i-1}+d_{n+j-1}+d_{2n+k-1}$ 。因此 $W=$ { $w_1,w_2,...,w_n$ }。取d进制是为了防止进位。
于是，可以设k=A= $\sum_{i=0}^{3n-1}d_{i}$ 。
归约完成。可以证明有一个完美的三维匹配当且仅当子集和问题中子集存在。
证明：假设有一个完美三维匹配 $T=$ { $t_1',t_2',...,t_n'$ },T的大小为n。在T中的每一个元素 $t_i$ 都在W’中对应一个元素 $w_{t_i}$ 。因为在三维匹配中所有的元素只出现一次，因此W中的所有元素相加得到一个3n位全为1的串，则 $\sum_{w \in W'}w=A$ 。
同时，假设有一个子集 $W' \subseteq W$ ,使得 $\sum_{w \in W'}w=A$ 。对于任意的元素 $w \in W'$ ,转换为d进制后都有3个位为1，对应于T的某一个元素。这些元素构成集合T，T中恰好包含X、Y、Z每个元素一次，因此T是一个完美匹配。

8 难问题的部分分类

8.1 包装问题

包装问题主要有独立集问题和集合包装问题。
（1）独立集问题：给定图G和数k，问G包含大小至少为k的独立集吗？
（2）集合包装问题：给定 $n$ 个元素的集合 $U$ , $U$ 的子集 $S_1,S_2,...,S_m$ 以及数 $k$ , 问在这些子集中至少含有 $k$ 个集合两两不相交？

8.2 覆盖问题

覆盖问题主要有顶点覆盖和集合覆盖问题。
（1）顶点覆盖：给定图G和数k，G是否包含大小为k的顶点覆盖？
（2）集合覆盖：给定 n 个元素的集合U,U 的子集 $S_1,…,S_m$ 以及数 k, 问在这些子集中有一组子集，它的并等于整个 U 且至多含有 k 个子集？

8.3 划分问题

划分问主要是三维匹配问题和图着色问题。
（1）三维匹配问题：给定三个不相交的集合X、Y、Z，三个集合的大小都为n。给定一个三元组集合，集合T的大小为m。问：T中是否存在一个大小为n的子集T’，这个子集恰好包含X,Y,Z每个元素一次。
（2）图着色问题：任意给图G和界限k，问G有k-着色吗？

8.4 排序问题

排序问题主要是巡回售货员问题、哈密顿圈、哈密顿路径问题。
（1）巡回售货员问题：给定n个城市之间的距离的集合以及界限D，问有长度不超过D的路线吗？
（2）哈密顿圈：给定有向图G，问G有哈密顿圈吗？
（3）哈密顿路径：给定有向图G，问G有哈密顿路径吗？

8.5 数值问题

数值问题主要是子集和问题。
（1）子集和：给定自然数 $w_1,w_2,...,w_n$ 和目标值W，问{ $w_1,w_2,...,w_n$ }有一个子集加起来恰好等于W吗？

8.6 约束满足问题

约束满足问题主要是电路可满足性问题、SAT和3-SAT。
（1）电路可满足性：给定一个电路，需要确定是否存在对输入的赋值使得输出值为1。如果存在这样的赋值，则称这个电路是可满足的。这个赋值也被称为一个满足的赋值。
（2）SAT：给定变量集 $X=$ { ${x_1,x_2,...,x_n}$ } 上的一组子句 $C_1,C_2,...,C_n$ ，问存在满足的真值赋值吗？
（3）3-SAT：给定变量集 $X=$ { ${x_1,x_2,...,x_n}$ } 上的一组子句 $C_1,C_2,...,C_n$ ，每一个子句的长度为3，问存在满足的真值赋值吗？

,.♥,.,.♥,.,.♥,.♥,.,.♥,.,.♥,.,.♥,.,.♥,.,.♥,.,.♥,.,.♥♥,.,.♥,.,.♥,.,.♥,.♥,.,.♥,.,.♥,.,.♥,.,.♥,.,.♥,.,.♥,.,.♥
广告时间：
本宝宝开通了一个公众号，记录日常的深度学习和强化学习笔记。希望大家可以共同进步，嘻嘻嘻！求关注，爱你呦！
NP与计算的难解性