本文是作者的原创文章，转载请注明出处 from Eric_Lai

reference：Introduction to Algorithm

几个相关的定义

P：多项式时间(polynomial time)内可以解决的一类问题，复杂度为O($n^c$)，其中c是一个常数，n为输入的规模。

NP：多项式时间内可以验证(verify)的问题，但是不能在多项式时间内找到答案。

很显然，$P \in NP$，但是P是否等于NP，目前还没人能给出证明，但是大多数的计算机科学家认为它们是不等的。

NP-complete problem (NPC)：如果一个问题A属于NP并且它是NP当中一个最难的问题，那么这个问题A就叫做NPC问题。

下图，给出了几个和NP有关的定义的非严格示意图：

证明一个问题是NPC

考虑如下的情况：某天你的老板让你做某个需求，并且给出了苛刻的要求，你查遍各种“典籍”都没能找到一个好办法。你开始考虑这是一个NP问题，但是你需要怎么向你的老板证明这是一个NP问题呢。如果你能证明，这个问题不仅你解决不了，世界上那么多的计算机科学家都解决不了，如果你的老板还有“人性”的话应该不会怪你。下面三幅漫画是1979年在Garey and Johnson上发表的，充分说明了上述的情况。

归约法(Reduction)

归约法，是用来证明一个问题是NPC问题的通用方法。假设，我们有一个可以在多项式时间内解决的判定性 (decision problem， 区别于optimal problem)的问题A (判定性问题，答案要么yes，要么no)。我们把对于某一个问题的输入称为这个问题的实例(Instance)。现在，在假设我们已经知道了对于问题B的一个多项式时间解法。最后，假设我们有一个转换的方法可以将问题A转化成问题B，并且这个转化符合如下的规定：

1. 问题A转换成问题B可以在多项式的时间内完成；
2. 这两个问题的答案是一样的，问题A的答案为yes，当且仅当问题B的答案也为yes；

上图所示的步骤，我们就把它称为一次多项式时间归约算法(polynomial time reduction algorithm)，它为我们提供了一个多项式内解决问题A的方法。总结一下，可以得到一下的标准步骤：

1. 对于给定的问题A的实例$\alpha​$，通过归约法，将其转换称为问题B的实例$\beta​$;
2. 对问题B的实例$\beta​$，执行已知的多项式解法；
3. 将问题B的答案推及到问题A；

证明的方法论

上文一直在说B是多项式时间内可解的，但是我们想做的事情是，证明一个问题是NPC，也就是多项式内不可解的。有了归约法，这个也不难，反过来想即可。如果一个问题A，可以通过某个多项时间内的转换方法转换到问题B，然而我们已经知道问题B是一个NPC问题，那么我们可以说问题A也是多项式时间内无解的(NPC)。

对于一个问题A，下面给出它是NP-complete的定义：

• A $\in$ NP；
• 对于所有的A‘ $\in$ NP，都有一个多项式的归约算法可以将A’归约到A

对于一个问题A，下面给出证明它是NPC的步骤：

1. 证明 A $\in$ NP，也就是证明问题A可以在多项式时间内被验证；
2. 选择一个已知的NP问题作为问题B；
3. 描述如何在多项式的时间内从问题A归约到问题B；

第一个NPC问题

上面给出的步骤又引出了一个问题，仔细思考第二步，“选择一个已知的NP问题”。但是NP问题需要通过一个已知的NP问题来证明，这就成了“先有鸡还是先有蛋”的问题了。幸运的是，已经有科学家证明了第一个NPC问题。目前公认的第一个被证明的NPC问题是SAT问题(Boolean Formula Satisfiability)由University of Toronto的Stephen A. Cook教授，在1971年发表的论文“The Complexity of Theorem-Proving Procedures”当中证明的。

一个SAT的实例是一个有n个布尔变量的布尔表达式。通常情况下，我们假设这些变量通过Conjuctive Normal Form (CNF，中文好奇葩叫做“合取范式”)的形式给出。如下图所示，(下面的一整个式子就是CNF形式的公式，全出来的是各个部分的名称)：

CNF：简单的来说就是，clause内部的literals之间关系全部都是OR，clauses之间的关系全部都是AND。

这里，还需要给一个可满足性赋值(satisfying assignment)的定义：如果有一种赋值方式(或者称为一个SAT实例)，可以使一个有n个布尔变量的布尔表达式的值为真，那么这种赋值方式就是该布尔表示式的一种可满足性赋值。

到这里，SAT问题就可以简单的定义为：

给一个布尔类型表达式，问它是否有一个可满足性赋值

Note：这个问题已经被证明为NPC问题，具体的证明，请参考Cook教授的论文，想看懂需要一定的数学背景。后文，SAT问题将默认已经被证明，可以直接使用。

例子

比较著名的NPC问题有以下这些(包括但不局限)，下文并且给出其中部分问题的证明(这些问题来自算法界经典名著CLRS)：

• 团问题(clique problem)

• 3 SAT问题
• 子集和问题(subset sum problem)
• 顶点覆盖问题(vertex-cover problem)
• 旅行商问题(TSP)

想要证明它们，可以按照CLRS当中给出的一张图来进行归约：

团问题

无向图G=(V, E)中的团是一个顶点的子集V‘ $\subseteq$ V，其中每一对顶点之间都有E中的一条边连接。团的规模是指它所包含的顶点数目。团问题是关于寻找图中最大子图的优化问题。但是作为判定性问题，只需考虑图中是否存在一个给定规模为k的团。

证明：团问题是一个NPC问题。

假设，有一个3SAT问题的实例$\phi=C_1 \wedge C_2 \wedge C_3 \cdot\cdot\cdot C_k$，其中任意一个$C_r$当中有且仅有3个literals，分别是$l_1^r$，$l_2^r$，$l_3^r$。构造一个图，使得$\phi$是可以满足的，当且仅当图中包含一个规模为k的团。构造方法如下，对于$\phi$当中的任意一个$C_r=$$l_1^r \vee l_2^r \vee l_3^r$，把这三个不相同的literals当成三个vertices分别命名为$v_1’,\;\;v_2’,\;\;v_3’$并且把它们组成的三元组放入G.V当中，如果满足下列的条件则在vertex $v_i$和$v_j$之间作一条边：

• $v_i$和$v_j$在不同的三元组当中，即$r \neq s$；
• $l_i^r$不是$l_j^r$的非；

一个例子如下图所示：

当图构建好之后，我们需要证明，从$\phi$到图G是一个归约算法。假设，$\phi$有一个可满足性赋值。如果是这样的话，每一个$C_r$当中，至少会有一个literal是True。我们把这些True的literal拿出来，构成一个有k个元素的集合v’。断言，这个集合v’就是一个团。证明如下：

• 对于集合v’当中的任意两个元素$v_i^r$和$v_j^s$(r $\neq$s)，因为可满足性赋值，它们所代表的literal必定是True。并且它们不可能是互补的，x在集合中的话，非x肯定不在集合当中。所以，根据建图的条件，($v_i^r$, $v_j^s$) $\in$ G.E；
• 如果一个图G有一个规模为k的团。同一元组中的元素之间没有边，并且G中相反的元素之间没有边，所以v’只包含一个元组当中的一个元素。我们可以给其中的literal赋值True，而不用担心True会被同时赋值到两个互补的元素中。由于每个clause都是可以满足的，所以$\phi$也是可以满足的；

上述证明了团问题是一个NP-hard问题，很显然，当给出一个图G和一个数k，我们可以在多项式的时间内检查出该图是否有一个规模为k的团。所以，团问题是一个NPC问题。

3 SAT问题

这个问题可以理解成是SAT问题的一个特例(显然3SAT问题可以被证明为SAT问题，下文省略这部分)，它规定布尔表达式的每个clause里面，有且仅有3个literals。问，是否有一种赋值方式，可以在多项式的时间内确定其可满足性。

证明：不存在一种赋值方式，可以在多项式的时间内确定其可满足性。

我们尝试从SAT问题，归约到这个3SAT问题。也就是说，能否将SAT问题，在多项式的时间内转换成一个3SAT的问题。下面给出一种证明方法，注意这个证明方法不同于CLRS当中的。我们的中心思想是：将每一个clause处理成有且仅有3个literals的形式。假设，布尔表达式当中的第i个式子用$C_i$来表示：

1. 当$|C_i|=1$时：例如$C_i$=(x)，引入两个新的变量y和z，将原来的式子$C_i$替换为，$(x \vee y \vee z)\wedge(x \vee \overline y \vee z)\wedge(x \vee y \vee \overline z)\wedge(x \vee \overline y \vee \overline z)$
2. 当$|C_i|=2$时：例如$C_i$=$(x \vee y)$，引入一个新的变量z，将原来的式子$C_i$替换为，$(x \vee y \vee z)\wedge(x \vee y \vee \overline z)$
3. 当$|C_i|=3$时，我们不需要做任何事情，因为它就是我们需要的形式；
4. 当$|C_i|\ge4$时，例如$C_i$=$(x_1 \vee x_2 \vee x_3 \vee \overline x_4 \cdot\cdot\cdot \vee x_k)$，这个时候我们需要引入k-3个变量，将原来的式子$C_i$替换为，$(x_1 \vee x_2 \vee y_1) \wedge (\overline y_1 \vee x_3 \vee y_2) \wedge (\overline y_2 \vee x_4 \vee y_3) \cdot\cdot\cdot (\overline y_{k-3} \vee x_{k-1} \vee x_k)$;

以上的替换，并非全都是逻辑相等(logic equal)的，也就是说从原来的式子并不能直接推导出替换后的式子 (比如第四点当中的式子)。这么替换的基础是，如果有一种赋值方式可以使原式得到某个结果，那么也会有某种方式也可以使替换后的式子得到相同的结果。换句话说，就是这两个式子的可满足性是相同的，但是并不是等价的。

下面以第四种情况为例，给出一个非严谨的“证明”：

假设k=5， $C_i$=$(x_1 \vee \overline x_2 \vee x_3 \vee \overline x_4 \vee x_5)$

假设，$x_1 = T\;\;, \;x_2 = T\;\;, \; x_3 =F\;\;, \;x_4=T\;\;, \; x_5=F$，那么原式应该为T，因为有一个T则为T。

替换后原式变为：$(x_1 \vee x_2 \vee y_1) \wedge (\overline y_1 \vee x_3 \vee y_2) \wedge (\overline y_2 \vee x_4 \vee x_5)$，这种情况下只需令$y_1=F$，即可使式子的结果和原式相等。理论是，原式因为都是OR，所以只要有一个为真，则都为真。替换后的式子，每个式子当中多了一个或者两个变量。如果其中的x变量为F，那么我们可以让其中的某个y变量为T，观察y变量的出现规律，一个y变量最多只能对替换后的一个clause做出影响。同理，可以证明都为假的情况(都为假更加简单，只需要一个为假即可)。

上述的四步，已经将一个SAT问题 (已知的NPC问题)，归约到了一个3SAT问题，显然，这四个步骤都可以在多项式的时间内完成。另外，如果给出一种特定的赋值方案，很显然可以在多项式的时间内验证它是否是一个可满足性赋值(代入验证即可)，故3SAT问题属于NP。综上所述，3SAT问题是一个NPC问题。

上文列举了问题，证明都可在CLRS当中找到，不再逐一列举。