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_1x_2 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_ix_j 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_ix_2 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)\) 时间内解决。
