一文理解NP完全理论，NP问题，NPC问题

在以往的算法中，所接触到的大都是多项式时间内可完成的算法，比如O(n),O(nlogn),O(n^2)…，但仍存在一些算法的时间复杂度为：O(n^logn),O(2^n),O(n!)是非多项式时间算法，当此类程序规模一旦过大，便成为目前的计算机解决不了的难题。因此尝试用NP完全理论进行理解。

NP问题—基本概念、规约

基本概念：P问题

定义P类问题（polynominal）：在多项式时间内可以解决的问题。

P类问题通常被认为是比较容易解决的问题，它的时间复杂度通常为多项式时间，如O(n)，O(nlogn)，O(

n^{3}

)等等。数据结构与算法中学习的搜索、排序、小数背包问题等都是P类问题。

基本概念：NP问题

定义NP类问题（Nondeterministic Polynominal）：给定一个证书（certificate）也可以理解为一个解或结果，可以在多项式时间内验证此证书是否是问题的一个解的问题。比如，在哈密顿回路中，我们给出一个所有节点的序列，即证书，可以很容易在多项式时间内验证这个证书是否是一个哈密顿回路。 

简单来说，一个问题是P问题，则其也一定是NP问题，反之一个问题是NP问题，则并不一定是P问题。一个问题是NP问题要证明其一定是P问题，也就P=NP，这还属于一个未解难题，因此通常认为P≠NP。

基本概念：NPC问题

定义NPC问题（NP完全问题）是NP类问题中最难的问题，包含两个条件：

1. 1.是一个NP问题（其实是首先限定了一个问题的难度范围，不能太难，至少可验证解）
2. 2.所有的NP问题都可以‘转换’成此问题（确切的定义是：所有的NP问题都可以归约（reducibility）成此问题，此处为了方便理解，用‘转换’来代替）

补充：也有一类问题叫NP Hard问题，相较于NPC问题，它没有要求一个NP问题这个条件，也就是意味着其甚至在多项时间解都不可验证。

基本概念：P、NP、NPC问题的关系

目前普遍认为P≠NP，虽然还没有得到确切证明。

基本概念：判断一个问题是否为NP问题

• >也就是给出一个证书（解），可否在多项式时间内判断它是否为原问题的一个解
• >最优化问题需要转化为判断性问题

比如给一你一个数组排序结果，判断其是否降序排列，很容易验证。而如果是著名的旅行商问题，也就是在在一个完全图中，找到一个最短回路。现在给你一个完全图，和一个回路，可以验证其是否为回路，但却很难验证是否为最短回路，也就是旅行商问题的一个解。旅行商问题便是最优化问题，那么可以考虑转化：

旅行商问题转化为：

• >此图中是否存在总权重为1的回路？
• >此图中是否存在总权重为2的回路？
• …
• >此图中是否存在总权重为n的回路？

转化为这样的问题，便可以从第一个问题开始判断，直到判断出已存在的权重最小的回路，便是旅行商问题的最优解。同理，一个优化问题可分解为多个判定性问题如果能够证明一个判定性问题为NP难时，显然原问题也是NP难的

基本概念：归约性

通俗的讲，一个问题（如Q1）可以规约为另外一个问题（如Q2）是指问题Q1可以转换为问题Q2，之后可以通过求解Q2的方法来求解Q1

如：求解一元一次方程（问题Q1）可归为求解一元二次方程（问题Q2）：一元二次方程的二次项系数为0即可，之后可以通过求解一元二次方程的方法来求解一元一次方程

准确定义（归约）

一个问题（Q1）可以规约为另外一个问题（Q2），需满足以下两个条件：

1. 1.实例对应性：Q1的任意一个实例Ф，通过函数f都可转化成Q2的一个实例f(Ф)，且这个转化函数f(Ф)必须为多项式时间；
2. 2.输出一致性：规约后的输出和原来的输出一致，即，如algo1是Q1的算法，algo2是Q2的算法，则在相同的输入下，algo1（Q1）=algo2（Q2）。

规约特点

• 1.归约具有传递性
• 2.如果问题A可归约为问题B，问题B可归约为问题C，则问题A一定可归约为问题C。

基本概念：归约证明

怎么去证明一个问题转换到另一个问题，这是一种规约呢？可按如下几点，分别证明实例的对应性和输出的一致性。

•     1.Q1问题的任意一个实例都可以转化为Q2问题的一个实例。
•     2.这个转化过程是多项式时间内可以完成的，或者说转化函数f是个多项式函数。
•     3.Q1问题的任意一个实例，如果其输出为真，则对应Q2问题实例的输出也一定为真。
•     4.Q2问题的任意一个实例，如果其输出为真，则对应Q1问题实例的输出也一定为真

如果问题Q1可以归约为问题Q2，则记为Q1

\leq _{p}

Q2，表示Q1小于Q2的难度不会超过一个多项式时间因子（但通常我们可以根据小于等于号≤来通俗的认为Q1的难度要小于等于Q2）。Q1

\leq _{p}

Q2，可以推出：

• 如果Q1是NPC问题，则Q2必然是NPC问题（因Q2不比Q1容易）；
• 如果Q2是P问题，则Q1必然是P问题（因Q1不比Q2难）；

其实很容易理解，NPC问题代表是较难的问题，Q1都属于NPC，那么比Q1还难的Q2自然也是NPC问题；P问题代表是简单的问题，如果Q2属于P问题，那比Q2还简单的Q1自然也是P问题。

NP问题—P问题的证明 

根据概念，已知能够设计一个算法，在多项式时间内解决一个问题，那这个问题就是属于P问题。而如果目前的问题找不到这样一个算法去直接解答，就需要采用证明的方式去验证其是P问题。即如果一个问题Q1能够规约到Q2，且已知Q2是P问题，那么Q1也必然是P问题。

2合取范式（CNF）的可满足性问题（SAT）

定义（2CNF-SAT）2CNF是一个布尔表达式，其由子句（clause）的‘与’组成，而每个子句都由2个文字（literal，文字为一个变量或者变量的‘否’）的‘或’组成。如

(\neg x\vee y)\wedge (\neg y\vee z)\wedge (x\vee \neg z)\wedge (z\vee y)

，

其中共有x，y，z三个变量，这些变量及其’否’为文字，两个文字构成了一个子句。2CNF的可满足性问题是指是否存在一个赋值，使得2CNF为真。

2合取范式（CNF）到图的转换

设2CNF-SAT有n个变量，m个子句，构造图G=(V,E)，图中共2n个节点，代表n个变量及每个变量的‘否’。对于2CNF中的每个子句，如

(x\vee y)

，则图中同时存在从节点

\neg x

到节点y的有向边，和从

\neg y

到x的有向边。 

如下图，3个变量对应图中有6个节点，4个子句对应图中有8条边，当且仅当2CNF中存在子句

(x\vee y)

，图G中存在边

\neg x\rightarrow y

和边

\neg y\rightarrow x

也就可顺势推出结论

1. 如图G中存在边

x\rightarrow y

，则必然会同时存在边

\neg y\rightarrow \neg x

。

1. 如图中包含一条x到y的路径，则必然也包含一条从

\neg x

到

\neg y

的路径。

定理：2CNF是不可满足的，当且仅当存在变量x，使得在图G中同时存在

• 一条x到¬x的路径
• 一条¬x到x的路径

可用反证法来证明以上定理，也就是2CNF是可满足的，且同时又存在上面两条路径。(具体证明有需要可以之后补上)。这就将2CNF的可满足性问题(

Q_{2CNF}

)转换到图中是否存在x→¬x和¬x→x的路径的问题(

Q_{G}

)，这也是一个规约的过程，

Q_{2CNF}

\leq _{p}

Q_{G}

 要证明以上这个规约的结论，就看其是否满足上面提到的证明规约的4个点：

• 1.实例的对应性：构造图的实例就是按照2CNF问题的实例来转的；并且是顶点和边的数量是对应的变量和子句的2倍，也是在多项式时间内可完成的转化。
• 2.输出的一致性：由以上定理证明了一组2CNF的赋值会固定对应图中存在的路径情况；而对于图问题中的实例的路径，也会对应到2CNF的值为真或假。

已证明这是个规约过程，接下来要试图验证推理：

在以上方法得出的图G=(V,E)中，可以在多项式时间内验证是否同时存在x→¬x和¬x→x路径

(x\in V)

，也就是问题

Q_{G}

是P问题。

这其实很简单，只需要对于图G中的任意节点，通过广度优先（或者深度优先）算法(复杂度为O(m))得出到其他节点的路径，遍历所有的节点就可以验证图G是否同时存在x→¬x和¬x→x的路径。复杂度为O(mn)，所以问题

Q_{G}

是P问题。再结合之前的结合定理和推论，得出2CNF可满足性问题是P问题。

NP问题—NPC问题的证明 

这是最重要的一部分，其实也与上面类似，就是规约问题的证明。

回顾NPC问题的定义为：

• 此问题是一个NP问题
• 所有的NP问题都可以归约为此问题

第一点还比较容易，第二点就比较复杂，但可以利用规约的传递性，所有的问题NP都能归约到一个已知的NPC问题，也就能归约到要求的问题Q，所以需证：

1. 问题Q是一个NP问题
2. 一个已知的NPC可以归约为问题Q

第一个NPC问题

所以需要找第一个NPC问题，才能让越来越多的NP问题进行规约。便是电路可满足性问题：

• 电路可满足性问题问题：给定一个逻辑电路，问是否存在一种输入使输出为True
• 其它的NPC问题都是由这个问题归约而来的。因此，逻辑电路问题是NPC类问题的“鼻祖”
• 有了第一个NPC问题后，一大堆NPC问题就出现了，因为再证明一个新的NPC问题只需要将一个已知的NPC问题归约到它就行了

电路的可满足问题简单来说也就是给你一个电路，试问存不存在一组输入，使得电路的输出为真

有了第一个NPC问题，再来证明公式的可满足性问题，比如给了一个公式，试问存不存在一种赋值使其为真。也可以看出判断一个问题是不是NPC问题，全部都是判断真假的验证性问题。

所以第一个需要证的是：这是一个NP问题，

首先证明SAT∈NP，为此我们只要证明SAT的任意实例Ф，Ф的可满足指派组成的证书（解）可以在多项式时间内验证，验证算法：

• 将公式Ф中的每个变量用相应的值代换；
• 计算所得的表达式。如果表达式的值是1，则公式Ф可满足。

显然上述的验证算法的复杂度是关于n+m的多项式，即O(n+m)。

接下来需要证：这是一个NPC问题，就需要从电路归约到公式可满足性。显而易见的是每个逻辑电路都可以写成一个布尔公式。

• 也就是存在f，使得任何一个实例x属于电路，当且仅当f(x)属于公式
• 但如果直接这么写，因每个电路门输出线扇出为2或者2以上导致布尔公式的规模出现指数增长

每个电路输出线扇出≥2的话，就很像数据结构中的满二叉树或者多叉树，节点数是呈指数型增长的，因此不能按这样的方法来构造。但我们并不需要完全的等价，只需要满足输出一致性就可以。

公式可满足性证明

实例对应性： 我们的目的不是将电路转换为布尔公式，而是证明可满足性，如果电路有可满足指派，则电路每个门输出都由其输入决定，写成表达式如

x_{10}\leftrightarrow (x_{7}\wedge x_{8}\wedge x_{9})

，这样转换的话，逻辑电路和布尔表达式的输出就是一致的。这就证明了实例对应性。

输出一致性：

• 以上转换为多项式时间
• 如果电路有可满足性实例，则电路输出为1，而公式输出也为1
• 如果公式输出为1，则显然逻辑电路输出也为1

3CNF问题

之前证明了2CNF是个P问题，现在来证3CNF形如下面公式的可满足性是NPC问题： 

(x_{1}\vee \neg x_{1}\vee \neg x_{2})\wedge (x_{3}\vee x_{2}\vee x_{4}))\wedge (\neg x_{1}\vee \neg x_{3}\vee \neg x_{4})

需要证明： 

• 这是一个NP问题
• 公式可满足性可以归约到3-CNF（已经证明了公式可满足性是NPC）

需要做的是：

1. 将布尔公式转换为子句的合取式
2. 将子句转换为合取范式
3. 将子句转为3个文字的合取取式

第一步就是建立语法树，把给定的布尔公式的语法树画下来，如下图。

 再将语法树看作逻辑电路，由上面可知，逻辑电路可以转换为合取范式

在转换为合取范式，对上图中的每个子句建立一个真值表，将真值表中为0的项，得到析取范式

 得到的析取范式等价于子句的否，运用德摩根定律，得出合取子句（将析取范式再取否）

而有时我们并不一定能得到如此恰好的每个子句中都有3个文字的情况，比如可能有2个文字，这时候可以随便合取一个变量p或¬p，只是为了满足每个字句必须恰有3各不同的文字的语法要求

 以上的映射都是多项式时间，

• step1：将布尔公式转换为子句的合取式
• ·同布尔电路转换为布尔公式
• step2：将子句转换为合取范式
• ·每个子句至多变为8个子句（至多3个变量）
• step3：将子句转为3个文字的合取取式
• ·至多引入4个子句

整个过程的转变基本都是等价的，所以对布尔公式和3CNF的赋值都会得到固定的真或假，所以这就是一个规约的过程。布尔公式是NPC问题，3CNF就也是NPC问题。

团问题

无向图G=(V,E)中的团（clique）是一个顶点子集V'

\subseteq

V，其中每一对顶点之间都由E中的一条边来连接。换句话说，一个团是G的一个完全子图。团的规模是指它所包含的顶点数。团问题是关于寻找图中规模最大的团的最优化问题。作为判定问题，我们仅仅要考虑的是：在图中是否存在一个给定规模为k的团？其形式定义为：

CLIQUE={<G,k>:G是一个包含规模为k的团的图}

那么团问题这样的最优化问题，要转换为判断型问题，也要证明其是个NPC问题

证明NP问题

首先证明其是一个NP问题，这相对来说还比较容易，也就是给一个解（证书）对于一个给定的图G来说，通过检查它的边是不是属于图的边集，就可以在多项式的时间内确定其是否为团

3CNF可以规约为团问题

想要构造图可通过

• 一个子句对应一组顶点
• 对于在意两个在不同组的顶点，如果满足“这两个顶点不是‘否’的关系”这一条件，就用一条边连接

如下图可观察到，左边三个点是第一个子句，中间三个点是第二个子句，右边三个点是第三个子句，而一组顶点之间都不存在边，跟其他组的任意一个顶点，只要不是否的关系则都有边连接。

证明其实例对应性与输出一致性

子句数量m对应顶点的个数是3m，一共3m个顶点，最多3m(m-3)条边，因此这是可以在多项式时间内转换的。如果存在一组赋值使得子句为1，所以必然存在一个规模为m的团，那么m个子句都为1，其中必定存在一个文字值为1，比如

(x_{1}\vee \neg x_{2}\vee\neg x_{3} )

值为1，则在3个变量中必定存在一个值为1的，因此图中必定存在一个团且规模为m；相反如果存在规模为m的团，也就是说三个组的节点，必然有一个有一个节点属于这个团，节点对应的文字为真，整个表达式就是真。

上面是一个特殊的图，能说明一般图的团也是NPC问题吗？答案是可以的，普通包含特殊，如果说普通的团是P问题，那么特殊的团自然也是P问题。而团在这种受限的情况下才是NPC，那么在一般的图中必然也是NPC问题。

顶点覆盖

给定一个IVI个点和|E|条边的无向图G(V,E)，找出最小数目的顶点集合S，使得G中的每条边都至少被集合S中的一个顶点覆盖，这就是顶点覆盖问题。如下图所示，点集合{b,e,f}是一个顶点覆盖，顶点覆盖中点的数目k=3，显然，顶点覆盖不是唯一的，如图中{b,d,c}也是顶点覆盖，但顶点覆盖点的数目k是唯一的。

顶点覆盖问题一般要求我们找能覆盖所有边最少的顶点集，这是一个最优化问题，那便可以转化为一个判断型问题，也就是问图中是否存在一个数目为m的顶点覆盖集。

现在要证明其是否为一个NPC问题，仍按照步骤：

首先证明其是个NP问题，即给定一个点集，问其是否为某张图的规模为k的顶点覆盖集，只需要带到图中进行验证即可。那么要用什么问题来规约顶点覆盖问题？便需要引入补图和团，团问题可以规约为顶点覆盖问题。

补图便是与一个已有的图对应的有相同的节点集V，但原图中有的边补图中没有，原图中不存在的边补图中便有，那么一个图中的最大团在补图中便成了一个最大的独立集S，其包含所有节点之间都不存在边，那么图中不包含在S内的节点V-S便包含了图中所有的边，这恰巧符合了顶点覆盖集的定义，所以其便是一个顶点覆盖集。

按照思路，为了证明顶点覆盖问题，需要定义原图G(V,E)的补图G(V,E)，如下图所示，图(b)为图(a)的补图。

首先证明实例对应性 

1. 团问题的任意一个实例可以转化为顶点覆盖问题的一个实例团问题的一个实例为一张无向图，其可以映射一张补图，为顶点覆盖的一个实例，得证。
2. 团问题实例到顶点覆盖问题实例的转换是一个多项式时间补图的顶点数和原图的顶点数是一样的，而补图的边是原图的边的补集，显然这个转化是多项式时间 

接着证明输出一致性

1. 如果G(V,E)的团为S，其规模为k，则G'的顶点覆盖为(V-S)，其规模为|V|一k
2. 如果G'(V,E')的顶点覆盖为S'，其规模为|V|-k，则G的团为(V-S')，其规模为k

第一个也就是证明如果原图G存在大小为S的团，那么补图G'必定存在V-S的顶点覆盖集(V为图的所有点集)。也就是要证明在G'中一条边的两个顶点e1，e2，至少有一个是∈V-S；相当于要证在G'中至少有一个不∈S。对应在原图G中，e1和e2之间不存在边，那边可知至少有一个节点不∈S（如果都属于S则原图便存在边了）便可以推回去证明了。

而第二个问题，也就是要整(V-S')中的任意两节点在原图G中都有边，如果这两个点都不属于S'，那么在G'中必定是没有边，在G中便一定有边。因此得证第二点。