《算法设计与分析基础》（Python语言描述） 课件 第9章NP完全问题

第9章最难问题—NP完全问题9.1P类和NP类9.2多项式时间变换和NP完全问题CONTENTS提纲1/442/44算法呈现不同的时间复杂度，有的属于多项式级时间复杂度算法，有的属于指数级时间复杂度算法，指数函数是典型的非多项式函数。通常将存在多项式时间算法的问题看作是易解问题，不存在多项式时间算法的问题看作是难解问题。9.1.1易解问题和难解问题9.1P类和NP类3/44通常把多项式时间复杂性作为易解问题与难解问题的分界线。问题规模n

多项式函数指数函数log2n

nnlog2n

n2

n32nn!1010.01121103.31033.2100100010243628800204.32086.4400800010483762.4E18505.650282.225001250001.0E153.0E641006.6100664.41000010000001.3E309.3E1574/44

定义9.1设A是求解问题Ⅱ（可以是任意问题）的算法，在用A求解问题Ⅱ的实例Ⅰ时，首先要把I编码成二进制的字符串作为A的输入，称I的二进制编码的长度为I的规模，记为|I|，如果存在函数f：N→N（N为自然数集合）使得对于任意规模为n的实例I，A对I的运算在f(n)步内停止，则称算法A的时间复杂度为f(n)。

以多项式为时间复杂度的算法称为多项式时间算法。有多项式时间的问题称为易解问题，不存在多项式时间算法的问题称为难解问题。输入带a1a2…ai…anBB……读写头有限状态控制器5/44采用动态规划算法求解0/1背包问题的时间复杂度为O(nW)。表面上看起来这是n的多项式，实际上这里|I|是n和W的二进制位数和，当W很大时，仍然是一个非多项式时间的算法。TSP和0/1背包问题等在内的一大批问题既没有找到它们的多项式时间算法，又没能证明它们是难解问题。6/449.1.2判定问题如果一个问题很容易重述为它的解只有两个结论即yes和no，称为判定问题Ⅱ。与此对照，最优化问题Ⅱ'是关心某个量的最大化或者最小化的问题。例如，前面讨论的TSP问题属于最优化问题Ⅱ'，对应的TSP判定问题Ⅱ是这样的，假设有一个货郎担要拜访n个城市，城市图采用邻接矩阵表示，给定一个正整数D，问有一条每个城市恰好经过一次最后回到出发城市并且路径长度不超过D的路径吗？7/44那么TSP最优化问题会不会比TSP判定问题容易呢？如果TSP最优化问题有多项式时间算法A，则可以按如下方式构造TSP判定问题的算法B：对于任意一个实例I，应用算法A求出最短路径长度d，如果d≤D，则算法B输出yes，否则输出no。显然算法B也是多项式时间算法。于是，这同样表明如果TSP判定问题是难解问题，则TSP最优化问题也是难解问题，这样说明TSP最优化问题不会比TSP判定问题容易。8/44一般地，如果一个问题的可行解是多项式时间算法可求的，那么如果其判定问题Ⅱ是难解问题，则对应的最优化问题Ⅱ'也是难解问题。可以证明反过来也是对的，如果最优化问题Ⅱ'是难解问题，则对应的判定问题Ⅱ也是难解问题。判定问题Ⅱ和对应的最优化问题Ⅱ'具有相同的难度。9/449.1.3P类定义9.2设A是求解问题Ⅱ的一个算法，如果对于任意一个实例I在整个执行过程中每一步都只有一种选择，则称A为确定性算法。因此对于同样的输入确定性算法的输出是相同的。前面所有讨论的算法均为确定性算法，实际上是指算法的确定性，是算法的重要特性之一。10/44定义9.3判定问题的P类由这样的判定问题组成，它们的yes/no解可以用确定性算法在运行多项式时间内得到。简单地说所有多项式时间可解的判定问题类称为P类。一个判定问题是易解问题当且仅当它属于P类。11/44【例9-1】证明求最长公共子序列问题是易解问题。证明：求最长公共子序列原问题是给定两个序列a=（a0,a1,…,am-1），b=（b0,b1,…,bn-1），求它们的最长公共子序列的长度d。对应的判定问题：给定一个正整数D，问存在a和b的长度不小于D的公共子序列吗？可以设计这样的算法B，先利用8.5.1节求最长公共子序列长度的算法LCSlength()求出d，其时间复杂度为O(mn)，属于多项式时间算法，如果d≤D，则输出yes，否则输出no。显然算法B也是多项式时间算法，所以LCS属于P类即是易解问题。12/449.1.4NP类对于输入x，一个不确定性算法由下列两个阶段组成。猜测阶段。在这个阶段产生一个任意字符串y，它可能对应于输入实例的一个解，也可以不对应解。事实上，它甚至可能不是所求解的合适形式，它可能在不确定性算法的不同次运行中不同。它仅仅要求在多项式步数内产生这个串，即时间为O(ni)，这里n=|x|，i是非负整数。对于许多问题，这一阶段可以在线性时间内完成。13/44②

验证阶段。在这个阶段一个不确定性算法验证两件事。首先检查产生的解串y是否有合适的形式，如果不是则算法停下并回答no。另一方面，如果y是合适形式，那么算法继续检查它是否是问题实例x的解，如果它确实是实例x的解，那么它停下并且回答yes，否则它停下并回答no。也要求这个阶段在多项式步数内完成。14/44定义9.4设A是求解问题Ⅱ的一个不确定性算法，A接受问题Ⅱ的实例I当且仅当对于输入I存在一个导致yes回答的猜测。换句话说，A接受I当且仅当可能在算法的某次执行上它的验证阶段将回答yes。如果算法回答no，那么这并不意味着A不接受它的输入，因为算法可能猜测了一个不正确解。15/44例如，不确定性算法A的伪码表示如下：1 defA(I):2 s=genCertif() #猜测阶段3 checkOK=verifyA(I,s) #验证阶段4 ifcheckOK:5 output"yes"6 return #checOK为假时不作反应16/44定义9.5判定问题的NP类由这样的判定问题组成，对于它们存在着多项式时间内运行的不确定性算法。简单地说由所有多项式时间可验证的判定问题类称为NP类。要注意的是不确定性算法并不是真正的算法，它仅仅是为了刻画可验证性而提出的验证概念。为了把不确定性多项式时间算法转换为确定性算法，必须搜索整个可能的解空间，注通常需要指数时间。17/44定义9.6NP类的非形式化定义是NP类由这样的判定问题组成，它们存在一个确定性算法，该算法在对问题的一个实例展示一个断言解时，它能够在多项式时间内验证解的正确性，也就是说如果断言解导致答案是yes，就存在一种方法可以在多项式时间内验证这个解。18/44【例9-2】给定一个无向图G=（V，E），用k种颜色对G着色是这样的问题，对于V中的每一个顶点有k种颜色中的一种对它着色，使图中没有两个相邻顶点有相同的颜色。着色问题是判定用预定数目的颜色对一个无向图着色是否可能。证明该问题属于NP问题。19/44证明：对于的判断问题是给定一个无向图G=（V，E）和一个正整数k（k≥1），G可以k着色吗？用两种方法证明上述判断问题COLORING属于NP类问题。方法1：设I是COLORING问题的一个实例，s被宣称为I的解。容易建立一个确定性算法来验证s是否确实是I的解（假设s为着色数目，一定同时求出一个对应的着色方案x，检测x是否为G的一个s颜色的着色方案只需要遍历每一条边即可）。从定义9.6可以得出COLORING属于NP类。20/44方法2：建立不确定性算法.当图G用编码表示后，很容易地构建算法A：首先通过对顶点集合产生一个任意的颜色“猜测”为一个解s，接着A验证这个s是否为有效解，如果它是一个有效解，那么A停下并且回答yes，否则它停下并回答no。A在猜测和验证两个阶段总共花费不多于多项式时间，所以COLORING属于NP类。21/44定理9.1P

NP。证明：这是显而易见的。如果某个问题Ⅱ属于P类，则它有一个确定性的求解算法A。很容易由算法A构造出这样的算法B，算法B对该问题的一个实例展示一个断言解时，它一定能够在多项式时间内验证解的正确性，所以问题Ⅱ也属于P类。现在的问题是P=NP?也就是说NP类中有难解问题吗？22/449.2多项式时间变换和NP完全问题9.2.1多项式时间变换定义9.7设判断问题Ⅱ1=<D1，Y1>，其中D1是该问题的实例集合，由Ⅱ1的所有可能的实例组成，Y1

D1由所有回答为yes的实例组成。另外一个判断问题Ⅱ2=<D2，Y2>同样类似的描述。如果函数f：D1→D2满足以下条件：①f是多项式时间可计算的，即存在计算f的多项式时间算法。②对于所有的I∈D1，I∈Y1

f(I)∈Y2。则称f为Ⅱ1到Ⅱ2的多项式时间变换。如果存在Ⅱ1到Ⅱ2的多项式时间变换，则称Ⅱ1可以多项式时间变换到Ⅱ2，记为Ⅱ1≤pⅡ2。23/44【例9-3】哈密尔顿问题是求无向图G=（V，E）中恰好经过每个顶点（城市）一次最后回到出发顶点的回路。

哈密尔顿判断问题：图G中存在恰好经过每个顶点一次最后回到出发顶点的回路吗？

哈密尔顿判断问题表示为HC=<DHC，YHC>，TSP判定问题表示为TSP=<DTSP，YTSP>，证明HC≤pTSP。24/44证明证明HC≤pTSP。多项式时间变换f：对于HC的每一个实例I，I是一个无向图G=（V，E），TSP判定问题对应的实例f(I)定义为G'=（V'，E'），这里V'=V，E'是含|V|个顶点的完全无向图，任意两个不同顶点u和v之间的距离为:d(u,v)=若(u,v)∈E2 否则容易证明G中有一个哈密尔顿回路当且仅当G'中有一条长度为|V|的TSP路径。从而有I∈YHC

f(I)∈YTSP，也就是说HC≤pTSP，示例即证。25/4412211111(a)一个无向图G01342(b)一个带权图G'01342示例26/44定理9.2≤p具有传递性，即若有Ⅱ1≤pⅡ2，Ⅱ2≤pⅡ3，则Ⅱ1≤pⅡ3。27/44定理9.3设Ⅱ1≤pⅡ2，则Ⅱ2∈P类蕴涵Ⅱ1∈P类。由此推出，设Ⅱ1≤pⅡ2，若Ⅱ1是难解问题，则Ⅱ2也是难解问题。这样≤p提供了判定问题之间的难度比较，如果Ⅱ1≤pⅡ2，则相对多项式时间，Ⅱ2不会比Ⅱ1容易，或者反过来说，Ⅱ1不会比Ⅱ2难。28/449.2.2NP完全性及其性质定义9.8如果对所有的Ⅱ'∈NP，Ⅱ'≤pⅡ，则称Ⅱ的NP难的。如果Ⅱ是NP难的并且Ⅱ∈NP类，则称Ⅱ是NP完全问题（NPC）。NP完全问题是NP类的一个子集，NP难的问题不会比NP类中的任何问题容易，因此NP完全问题是NP中最难的问题。29/44定理9.4如果存在NP难的问题Ⅱ∈P类，则P=NP。假设P≠NP，那么如果Ⅱ是NP难的则ⅡP类。虽然“P=NP?”至今没有解决，但人们普遍相信P≠NP，因而NP完全问题成为表明一个问题很可能是难解问题的有力证据。NP完全问题PNP30/44定理9.5如果存在NP难的问题Ⅱ'，使得Ⅱ'≤pⅡ，则Ⅱ是NP难的。该定理提供了证明Ⅱ是NP难的一条捷径，不再需要把NP类中所有的问题多项式时间变换到Ⅱ，而只需要把一个已知的NP难问题多项式时间变换到Ⅱ，这样为了证明Ⅱ是NP完全问题，只需要做两件事：①证明Ⅱ∈NP类。②找到一个已知的NP完全问题Ⅱ'，并证明Ⅱ'≤pⅡ。31/449.2.3第一个NP完全问题在命题逻辑中，给定一个布尔公式F，如果它是子句的合取，称为合取范式（CNF）。一个子句是文字的析取，这里的文字是一个布尔变元或者它的非，例如，以下布尔公式F1就是一个合取范式：

F1=(x1∨x2)∧(

x1∨x3∨x4∨

x5)∧(x1∨

x3∨x4)一个布尔公式的真值赋值是关于布尔变元的一组取值，一个可满足的赋值是一个真值赋值，它使得布尔公式的值为1。如果一个布尔公式具有可满足赋值，则称该公式是可满足的。可满足性判定问题SAT：给定一个布尔公式F（合取范式），F是可满足的吗？例如，上述公式F1，赋值为x1=1，x3=1，其他取0或者1，F1的结果为1，所以F1是可满足的。32/44显然SAT属于NP类问题，因为容易建立一个确定性算法来验证一个赋值s是否确实是SAT的一个可满足的赋值。Cook-Levin证明了SAT是NP完全问题，称为Cook-Levin定理。33/449.2.4其他NP完全问题3CNF指的是布尔公式F中每个子句都精确地有3个不同的文字。例如，以下布尔公式F2就是一个3CNF：F2=(x1∨

x1∨

x2)∧(x3∨x2∨x4)∧(

x1∨

x3∨

x4)3CNF可满足性判定问题3SAT：给定一个3CNF公式F，F是可满足的吗？例如，上述公式F2，赋值为x1=0，x2=1，x3=1，x4=0，F2的结果为1，所以F2是可满足的。34/44定理9.63SAT是NP完全问题。证明：利用定理9.5证明。证明3SAT∈NP类。如同证明SAT属于NP类，很容易建立一个确定性算法来验证一个赋值s是否确实是3SAT的一个可满足的赋值。已知SAT是一个NP完全问题，现在证明SAT≤p3SAT。为此按如下步骤构造多项式时间变换f。35/44F1=(x1∨x2)∧(

x1∨x3∨x4∨

x5)∧(x1∨

x3∨x4)y2∧y1∨x1x2y3∧y4∨y6∨y8∨y5∨y7∨x4

x5

x3x4

x1x3x1第一步，对于任意给定的布尔公式F对应的F1'如下：F1'=y1∧(y1

(y2∨y3))

∧(y2

(x1∨x2))

∧(y3

(y4∧y5))

∧(y4

(

x1∨y6))

∧(y5

(x1∨y7))

∧(y6

(x3∨y8))

∧(y7

(

x3∨x4))

∧(y8

(x4∨

x5))36/44第二步，将F'进一步转换为公式F''，使得F''中的每一个子句精确地有3个不同的文字。为此引入两个辅助变元p和q。对公式F'的子句Ci'做如下转换：

①如果Ci'有3个不同的文字，保持不变。

②如果Ci'有2个不同的文字，例如l1∨l2，将其转换为(l1∨l2∨p)∧(l1∨l2∨

p)

③如果Ci'仅有1个文字l，将其转换为(l∨p∨q)∧(l∨p∨

q))∧(l∨

p∨q))∧(l∨

p∨

q)上述转换均是等价转换，这样得到3SAT的公式F''，显然转换过程是多项式时间，所以SAT≤p3SAT成立。SAT为NP完全问题，所以3SAT也是一个NP完全问题。37/44【例9-4】团集判定问题CLIQUE是给定一个无向图G=（V，E）和一个正整数k，问G中有大小为k的团集吗？无向图G中大小为k的团集是指包含k个顶点的完全子图。

证明CLIQUE是NP完全问题。38/44证明：利用定理9.5证明。①证明CLIQUE∈NP类。如果s被宣称为一个解，则对应一个大小为k的团集V'，只需要看V'中任意两个顶点之间是否有边相连，从而得到了一个确定性验证算法，所以CLIQUE属于NP类。39/44②已知3SAT是一个NP完全问题，现在证明3SAT≤pCLIQUE。对于