NPC (NP-complete) 问题指在NP问题中最困难的一类问题。现在一般认为$NP\neq P$, 也即 NP-complete 问题不存在多项式时间的算法。本文总结了几类典型的 NPC 问题，在遇到一个新问题时，如果能将某个 NP-complete 问题规约到新问题上，则可以证明它是一个 NPC 问题，而不再去寻找多项式时间的算法。（如果你证明了它是一个 NP-complete 问题同时得到了一个多项式时间算法，那么恭喜你（x
主要参考 《Algorithm Design》Jon Kleinberg / Éva Tardos 第八章
这篇文章已知电路可满足性问题，SAT问题和 3-SAT问题是NPC (NP-Complete) 问题。（有空再写一篇
问题分类
包装问题
包装问题有这样的结构：给定对象的集合，从中至少选择 k 个，但是对象之间存在一些冲突使得不能同时选择某些对象。
- 独立集问题：给定图 $G$ 和数 $k$， 问 $G$ 是否有大小至少为 $k$ 的独立集。
- 集合包装问题：给定 $n$ 个元素的集合 $U$， $U$ 的子集 $S_1,…,S_m$ 和数 $k$， 问这些子集中是否至少有 $k$ 个两两不相交。
覆盖问题
覆盖问题是包装问题的反问题。给定对象的集合，要选择一个子集合起来达到一定的目标，但只能选择 k 个对象。
- 顶点覆盖: 给定图 $G$ 和数 $k$， 问 $G$ 是否有大小不超过 $k$ 的顶点覆盖。
- 集合覆盖：给定 $n$ 个元素的集合 $U$， $U$ 的子集 $S_1,…,S_m$ 和数 $k$， 问这些子集中是否有不超过 $k$ 个子集的并等于整个 $U$。
划分问题
搜索把对象集合分成不同子集的所有方式，要求每一个对象恰好出现在一个子集中。
三维匹配问题: 要同时解决覆盖问题和包装问题，即选择某些集合使得它们互不相交并且完全覆盖集合
- 三维匹配问题：给定不相交的集合 $X,Y,Z$ 及有序三元组集合 $T\subseteq X\times Y\times Z$，其中 $X,Y,Z$ 的大小均为 $n$ ，问 $T$ 中是否有 $n$ 个三元组使得 $X\cup Y\cup Z$ 中的每一个元素恰好包括在其中一个三元组中。
图着色问题: 尝试在存在冲突的情况下划分对象，冲突对象不能放入同一个集合。
- 图着色问题：给定图 $G$ 和数 $k$， 问 $G$ 是否有 $k$ - 着色。
排序问题
在对象的所有排列上进行搜索。
哈密顿圈和哈密顿路径，要求排列 n 个对象的次序，有一些限制不让把某些对象放在某些对象之后
- 哈密顿圈：给定有向图 $G$ ，问 $G$ 是否有哈密顿圈
- 哈密顿路径：给定有向图 $G$ ，问 $G$ 是否有哈密顿路径
巡回售货员问题，将某些对象放在某些对象之后的限制软化为付出一定的代价
- 巡回售货员：将某些对象放在某些对象之后的限制软化为付出一定的代价
数值问题
子集和问题是背包问题的特殊情况。给带权重的对象集合，目标是选择子集满足机组总权重的限制。
- 子集和问题：给定自然数 $w_1,…,w_n$ 和目标值 $W$ ，问 ${w_1,…,w_n}$ 是否有一个子集加起来恰好等于 $W$
约束满足问题
- 电路可满足性问题
- SAT 问题
- 3-SAT 问题： 给定变量集 $X={x_1,…,x_n}$ 上的一组子句 $C_1,…,C_k$， 每一个子句的长度为 3，问是否存在满足条件的赋值。
有两种看待 3-SAT 问题实例的方式
- 搜索变量的赋值的所有可能，要求所有子句必须满足
- 搜索从每一个子句中选择一项使子句满足的选择方式，要求不能从不同的子句中选择冲突的项
独立集问题 & 顶点覆盖问题
独立集问题 & 顶点覆盖问题
设 $G =(V,E)$ 是一个图，$S\subseteq V$ ，$S$ 是一个独立集当且仅当它的补集 $V-S$ 是一个顶点覆盖。
- 独立集问题 $\le _p$ 顶点覆盖问题
- 顶点覆盖问题 $\le _p$ 独立集问题
顶点覆盖是集合覆盖的特殊情况。对于顶点覆盖问题的实例 $G=(V,E)$ 和数 $k$。构造集合覆盖的实例： $U = E$， $S_i $ 为所有与顶点 $i$ 关联的边。可以验证 $U$ 能被集合 $S_1, S_2,…,S_n$ 中的至多 $k$ 个覆盖 当且仅当 $G$ 有大小至多为 $k$ 的顶点覆盖。对独立集问题与集合包装问题同理。
- 顶点覆盖问题 $\le _p$ 集合覆盖问题
- 独立集问题 $\le _p$ 集合包装问题
3-SAT $\le _p$ 独立集问题
这里用到了上面讨论的看待 3-SAT 问题的第二种方式。
3-SAT问题的实例为 变量集 $X={x_1,…,x_n}$ 和子句 $C_1,…,C_k$
构造独立集问题的实例 $G=(V,E)$, 由分成 $k$ 个三角形的 $3k$ 个顶点组成：对 $i = 1,2,…,k$ 构造三个顶点 $v_{i1},v_{i2},v_{i3}$ 彼此之间用边连接， $v_{ij}$ 表示 3-SAT实例中子句 $C_i$ 的第 $j$ 项。在不同子句中表示冲突的项的顶点之间添加一条边：即在变量 $x_i, \bar x_i$ 之间添加一条边。
可以验证，3-SAT 实例是可满足的 当且仅当 $G$ 有大小至少为 $k$ 的独立集
排序问题
3-SAT $\le _p$ 哈密顿圈问题
这里用到了上面讨论的看待 3-SAT 问题的第一种方式。
3-SAT问题的实例为 变量集 $X={x_1,…,x_n}$ 和子句 $C_1,…,C_k$。
构造 $n$ 个环 $P_1,P_2,…,P_n$ 对应 $n$ 个变量， 哈密顿圈从左往右通过第 $i$ 个环表示第 $i$ 个变量取 1，反之取 0。每个环由 $b=3k+3$ 个顶点组成。对于子句 $C_1 = x_1\vee \overline x_2 \vee x_3 $, 可以表示为：或者从左到右通过 $P_1$， 或者从右往左通过 $P_2$，或者从左到右通过 $P_3$。因此，对子句 $C_j$ 定义一个顶点 $c_j$，如果 $C_j$包含 $x_i$, 则添加边 $(v_{i,3j},c_j),(c_j,v_{i,3j+1})$；如果 $C_j$包含 $\overline x_i$, 则添加边 $(v_{i,3j+1},c_j),(c_j,v_{i,3j})$。
可以验证图中有哈密顿圈 当且仅当 3-SAT 实例是可满足的
哈密顿圈问题 $\le _p$ 巡回售货员问题
哈密顿圈的实例为有向图 $G=(V,E)$ 。
构造巡回售货员问题实例：对 G 中的每一个顶点 $v_i$，有一个城市 $v_i’$， 如果在 $G$ 中有边 $(v_i,v_j)$，则规定 $d(v_i’,v_j’) = 1$，否则 $d(v_i’,v_j’) = 2$
可以验证， 图中有哈密顿圈 当且仅当 新图中有长度不超过 $n$ 的巡回路线
哈密顿圈问题 $\le _p$ 哈密顿路径问题
哈密顿圈的实例为有向图 $G=(V,E)$ 。
构造哈密顿路径问题实例图 $G’$，在 $G$ 中任取一个顶点 $v$，把它替换为两个新的顶点$v’,v’’$，在 $G$ 中所有从 $v$ 出发的边从 $v’$ 出发，进入 $v$ 的边进入 $v’’$
可以验证， $G$ 中有哈密顿圈 当且仅当 $G’$ 中有哈密顿路径
划分问题
三维匹配问题
三维匹配问题是集合覆盖问题和集合包装问题的特殊情况。
我们企图用给定子集合中最多 $n$ 个覆盖整个集合 $X\cup Y\cup Z$ ，因此可以看作集合覆盖问题的特殊形式。另一方面，我们在寻找集合 $X\cup Y\cup Z$ 的 $n$ 个不相交的子集，因此可以看作集合包装问题的特殊形式。
- 三维匹配问题 $\le _p$ 集合覆盖问题
- 三维匹配问题 $\le _p$ 集合包装问题
3-SAT $\le _p$ 三维匹配问题
这里用到了上面讨论的看待 3-SAT 问题的第一种方式。这个好难 QAQ
3-SAT问题的实例为 变量集 $X={x_1,…,x_n}$ 和子句 $C_1,…,C_k$。
对每个变量 $x_i$，定义一个基本零件：$2k$ 个顶点 ${a_{i1},…,a_{i,2k}}$ 构成核心，$2k$ 个顶点 ${b_i1,…,b_{i,2k}}$ 构成边梢。每两个核心顶点与一个边梢顶点后才一个三元组 $t_{ij} = {a_{ij}, a_{i,j+1}, b_{ij}}$ (模 $2k$ 加)，如果 $j$ 是偶数则称三元组 $t_{ij}$ 是偶的，同时有边梢 $b_{ij}$ 是偶的。
首先分析这个零件：将所有 $j$ 为偶数的核心顶点 $a_{ij}$ 放入集合 $X$ 中， $j$ 为奇数的核心顶点 $a_{ij}$ 放入集合 $Y$ 中，所有边梢顶点 $ b_{ij}$ 放入集合 $Z$ 中。
核心顶点不会出现在其他三元组中。因此，要得到一种三维匹配，对每个零件，或者取得所有的偶三元组，或者取得所有的奇三元组。（否则会出现核心顶点重叠或者未取到的情况）
这样，就可以根据零件取得是偶三元组还是奇三元组给变量赋值。使用偶三元组的元素取 0（此时奇数的边梢顶点未被覆盖），使用奇三元组的元素取 1（此时偶数的边梢顶点未被覆盖）
接着考虑 3-SAT问题中的子句。对于子句 $C_m = x_i\vee \overline x_j \vee x_k $, 可以表示为：或者第 $i$ 个零件的偶数边梢顶点未被覆盖，或者第 $j$ 个零件的奇数边梢顶点未被覆盖，或者第 $k$ 个零件的偶数边梢顶点未被覆盖。我们添加两个元素 $P_m = {p_m,p_m’}$ 和三个包含他们的三元组：${p_m,p_m’,b_{i,2m}}$, ${p_m,p_m’,b_{j,2m-1}}$, ${p_m,p_m’,b_{k,2m}}$。
为了覆盖这两个元素，至少需要有其中一个零件对应的边梢顶点未被覆盖。对不同的子句，会使用不同的边梢顶点，从而避免子句零件之间互相竞争。
到这里基本解决了子句满足的问题，但是要得到一个三维匹配，现在选择的三元组有：对每个变量，选择所有的偶三元组或所有的奇三元组；对每个子句，选择一个满足条件三元组。这些三元组覆盖了 所有的核心顶点，所有的子句顶点，但只覆盖了 $nk+k$ 个边梢顶点。还有 $(n-1)k$ 个边梢顶点需要覆盖。
为此，我们添加 $(n-1)k$ 个清除零件。对每个清除零件，定义两个顶点 $Q_i = {q_i,q_i’}$，定义 $2nk$ 个三元组：对每个变量中的每个边梢顶点，都有一个三元组 ${q_i, q_i’, b_{jk}}$。（也就是说，这里添加了 $2(n-1)k$ 个顶点和 $(n-1)k\times 2nk$ 个三元组。
在选择完零件的三元组和子句的三元组后，任意未被覆盖的边梢顶点都可以找到一个清楚三元组。
将所有 $p_j, q_i$ 顶点加入 $X$ 中，将所有 $p_j’, q_i’$ 顶点加入 $Y$ 中。此时 $X, Y,Z$ 中均有 $2nk$ 个元素。
可以验证，3-SAT 实例是可满足的 当且仅当 当前实例有三维匹配。
图着色问题
二着色问题
一个图是可二着色当且仅当它是二部图
3-SAT $\le _p$ 三着色问题
这里用到了上面讨论的看待 3-SAT 问题的第一种方式。我们构造一个图使得任何一种三着色方案确定给定 3-SAT 实例中的一种变量赋值方法。
3-SAT问题的实例为 变量集 $X={x_1,…,x_n}$ 和子句 $C_1,…,C_k$。
首先，定义一个基础图 $G$：定义三个特殊节点：真结点，假结点，基点；对每个变量和它的否定，定义两个节点。按下图的方式连接：
对 $G$ 进行三着色，可以得到：
- 节点 $v_i,\overline{v_i}$ 有不同的颜色，且与基点颜色不同
- 真结点，假结点，基点为三种不同颜色
于是，可以将变量的真与假用颜色表示。当 $v_i$ 与真结点颜色相同时，变量 $x_i $ 取值 1；反之取 0
接着，需要使得着色满足子句的条件。对子句 $C_1 = x_i\vee \overline x_2 \vee x_3 $, 可以表示为结点 $v_1, \overline v_2, v_3$ 中至少有一个与真结点颜色相同。因此，可以在 $G$ 中插入一个子图，使得只有这三个顶点中至少有一个与真结点颜色相同，才能完成三着色问题。下图展示了一种画法：如果三个结点均为假结点颜色，则顶端结点无法进行着色。
对每个子句，都在 $G$ 中插入一个子图，得到三着色问题的实例 $G’$
可以验证， 3-SAT 实例是可满足的 当且仅当 $G’$有一种三着色方案
三着色问题 $\le _p$ $k$ 着色问题
对于三着色问题的实例图 $G$ ，添加 $k-3$ 个新的节点，新的节点相互连接且与 $G$ 中每一个节点连接。
可以验证，所得到的图是 $k$ 可着色的 当且仅当 原图 $G$ 满足三着色。
数值问题
三维匹配问题 $\le _p$ 子集和问题
我们要找一个基于 恰好 满足限制的组合问题，自然地选择了三维匹配问题。
对三维匹配问题的实例：集合 $X,Y,Z$ 及有序三元组集合 $T\subseteq X\times Y\times Z$, $\vert T\vert = m$， $X,Y,Z$ 的大小均为 $n$
定义一个子集和问题：（为了避免仅为带来地问题，）以 $m+1$ 为底
- 对每一个有序三元组 $t = (x_i,y_j,z_k)\in T$，构造一个 $3n$ 位的数 $w_t$ 在第 $i,n+j,2n+k$ 位为1，其他地方为 0, 即 $w = (m+1)^i + (m+1)^{n+j}+(m+1)^{2n+k}$
- $W$ 是一个 $3n$ 位每一位都为 1 的数，即 $W = \sum_{i=0}^{3n-1} (m+1)^i$
原问题存在三维匹配 当且仅当 当前子集和问题有解。即每一位上都取到一个 1
子集和问题 $\le _p$ 带起止时间的调度问题
带起止时间的调度问题: 有 n 个任务在一台机器上完成，每个任务 $i$ 有一个开放时间 $r_i$， 截止时间 $d_i$，加工时间$t_i$。任务 $i$ 必须安排在 $[r_i,d_i]$ 中连续的 $t_i$ 个时间单位内完成。问是否能制定任务时间表使得所有任务在截止时间之前完成。
（变个魔法
对子集和问题的实例：自然数 $w_1,…,w_n$ 和目标值 $W$
令 $S = \sum_{i=1}^n w_i$，定义 $n$ 个任务，第 $i$ 个任务开放时间为 $0$， 截止时间为 $S+1$，加工时间为 $w_i$。对于这些任务，可以随便安排他们。
接着，限制安排任务的唯一方式是有某些加工时间加起来等于 $W$ 的任务放在一起完成。 定义第 $n+1$ 个任务，它的开放时间为$W$，截止时间为 $W+1$，加工时间为 1
可以验证，子集和问题有解 当且仅当 能够制定任务时间表使得所有任务在截止时间之前完成
有多项式解析的子集和问题
对于子集和问题的特殊情况，自然数 $w_1,…,w_n$ 和目标值 $W$ ，如果 $W$ 不超过 $n$ 的多项式大小，在 $N\neq NP$ 的假设下，这个问题不是 NPC的.
可以用动态规划在 $O(nW)$ 时间内解决。
