1、Algorithms Design Techniques and Analysis第 10章NP完全问题Computability TheoryAlgorithms Design Techniques and Analysis本章内容本章内容Introduction of a class of problems for which no efficient algorithms have been found P类NP类NP完全问题co-NP类NPI类Algorithms Design Techniques and Analysis10.1 引言 设是任意问题，如果对问题存在一个算法，它的时间
2、复杂性是O(nk)，其中是输入大小，k是非负整数，我们说存在着求解问题n的多项式时间算法。这类算法在可以接受的时间内实现问题求解，e.g.,排序、串匹配、矩阵相乘。但是，现实世界中的许多有趣问题并不属于这个范畴，因为求解这些问题所需要的时间量要用指数和超指数函数(如2n和n!）来测度。随着问题规模的增长而快速增长。在计算机科学界已达成这样的共识，认为存在多项式时间算法的问题是易求解的，而对于那些不大可能存在多项式时间算法的问题是难解的。易解问题与难解问题的主要区别 在学术界已达成这样的共识：把多项式时间复杂性作为易解问题与难解问题的分界线，主要原因有：1)多项式函数与指数函数的增长率有本质差别
3、问题规模问题规模n多项式函数多项式函数指数函数指数函数lognnnlognn2n32nn!1010.01121103.31033.2100100010243628800204.32086.4400800010483762.4E18505.650282.225001250001.0E153.0E641006.6100664.41000010000001.3E309.3E157Algorithms Design Techniques and Analysis2)计算机性能的提高对易解问题与难解问题算法的影响 假设求解同一个问题有5个算法A1A5，时间复杂度T(n)如下表，假定计算机C2的速度是计算
4、机C1的10倍。下表给出了在相同时间内不同算法能处理的问题规模情况：T(n)nn变化变化n/n10n100010000n=10n1020n5005000n=10n105nlogn2501842nn10n7.372n270223n3.162n1316n=n+log10n+311010Algorithms Design Techniques and Analysis3)多项式时间复杂性忽略了系数，不影响易解问题与难解问题的划分问题规模问题规模n多项式函数多项式函数指数函数指数函数n8108nn10001.1n20.01n53906255108510001.6111.0351010810910100
5、02.5941.0721001016101010200013780.621000102410111030002.4710411024观察结论：观察结论：n100时，（不自然的）多项式函数值大于指数时，（不自然的）多项式函数值大于指数函数值，但函数值，但n充分大时，指数函数仍然超过多项式函数充分大时，指数函数仍然超过多项式函数。Algorithms Design Techniques and AnalysisAlgorithms Design Techniques and Analysis难解问题 这一类含有许许多多问题，其中还包含了数百个著名的问题，它们有一个共同的特性，即如果它们中的一个是多
6、项式可解的，那么所有其他的问题也是多项式可解的。此外，现存的求解这些问题的算法的运行时间，对于中等大小的输入也要用几百或几千年来测度。Algorithms Design Techniques and Analysis判定问题和最优化问题判定问题:在研究NP完全性理论时，我们很容易重述一个问题使它的解只有两个结论:yes或no，在这种情况下，称问题为判定问题。最优化问题:与此相对照，最优化问题是关心某个量的最大化或最小化的问题。在前面的章节中，已经遇到过大量的最优化问题，像找出一张表中的最大或最小元素的问题，在有向图中寻找最短路径间题和计算一个无向图的最小生成树的问题。如果我们有一个求解判定问题
7、的有效算法，那么很容易把它变成求解与它相对应的最优化问题的算法。反之亦然。Algorithms Design Techniques and Analysis例子 10.1设S是一个实数序列，ELEMENT UNIQUENESS问题为，是否S中的所有的数都是不同的。判定问题:ELEMENT UNIQUENESS.输入:一个整数序列S问题:在S中存在两个相等的元素吗?最优问题:ELEMENT COUNT输入:一个整数序列S输出:一个在S中频度最高的元素。这个问题可以用显而易见的方法在最优的时间O(nlogn)解决，这意味着它是易解的。Algorithms Design Techniques and
8、 Analysis例子 10.2给出一个无向图G=(V,E)，用k种颜色对G着色是这样的问题:对于V中的每一个顶点用k种颜色中的一种对它着色，使图中没有两个邻接顶点有相同的颜色。这个问题是难解的.例子 10.2 COLORING问题（图着色问题）输入:(着色数)k,(节点数)5,(图的边)(1,2)(1,4).写出长度为n(节点数)的字符串,例如,RGRBG,RGRB,RBYGO,RGRBY,R%*$等，至少有kn个不同着色情况。找到符合要求（任何两个邻接顶点颜色不同）的最小的k值31245Algorithms Design Techniques and Analysis例子 10.2(Con
9、tinue)判定问题:COLORING 输入:一个无向图G=(V,E)和一个正整数k 1。问题:G可以k着色吗?即G最少可以用k种颜色着色吗?这个问题的一个最优形式是，对一个图着色，使图中没有两个邻接的顶点有相同的颜色，所需要的最少颜色数是多少?这个数记为(G)，称为G的色数。最优化问题:CHROMATIC NUMBER输入：一个无向图G=(V,E)。输出：G的色数。四色猜想 地图四色定理(Four color theorem)最先是由一位叫古德里（Francis Guthrie）的英国大学生提出来的。四色问题的内容是：“任何一张地图只用四种颜色就能使具有共同边界的国家着上不同的颜色。”Alg
10、orithms Design Techniques and Analysis四色猜想1852年，刚从伦敦大学毕业的Francis Guthrie提出了四色猜想。1878年著名的英国数学家Cayley向数学界征求解答。此后数学家 Heawood 花费了毕生的精力致力于四色研究，于1890年证明了五色定理（每个平面图都是5顶点可着色的）。直到1976年6月，美国数学家 K.Appel与 W.Haken，在3台不同的电子计算机上，用了1200小时，作了100亿判断，才终于完成了“四色猜想”的计算机证明。Algorithms Design Techniques and AnalysisAlgorith
11、ms Design Techniques and Analysis例子 10.3给出一个无向图G=(V,E)，对于某个正整数k,G中大小为k的团集，是指G中有k个顶点的一个完全子图。团集问题是问一个无向图是否包含一个预定大小的团集。判定问题:CLIQUE.输入:一个无向图G=(V,E)和一个正整数k。问题:G有大小为k的团集吗?最优化问题:MAX-CLIQUE.输入：一个无向图G=(V,E).输出:一个正整数k，它是G中最大团集的大小Algorithms Design Techniques and Analysis 如果我们有一个求解判定问题的有效算法，那么很容易把它变成求解与它相对应的最优化
12、问题的算法。例如，我们有一个求解图着色判定问题的算法A，则可以用二分搜索并且把算法A作为子程序来找出图G的色数。很清楚，1=x(G)=n，这里n是G中顶点数，因此仅用O(1og n)次调用算法A就可以找到G的色数。由于我们正处理多项式时间的算法，log n因子是不重要的。因为这个理由，在NP完全问题的研究中，甚至在一般意义上的计算复杂性或可计算性的研究中，把注意力限制在判定问题上会比较容易一些10.2 P类 因此，易解问题和难解问题的划分标准可基于对所谓判定问题的求解方式。事实上，实际应用中的大部分问题问题可以很容易转化为相应的判定问题，如：排序问题 给定一个实数数组，是否可以按非降序排列?图
13、着色问题：给定无向连通图G=(V,E)，求最小色数k，使得任意相邻顶点具有不同的着色 给定无向连通图G=(V,E)和正整数k，是否可以用k种颜色.?Algorithms Design Techniques and AnalysisAlgorithms Design Techniques and Analysis10.2 P类 定义 10.1 设A是求解问题的一个算法，如果在展示问题的一个实例时，在整个执行过程中，每一步都只有一种选择，则称A是确定性算法。因此如果对于同样的输入，实例一遍又一遍地执行，它的输出从不改变。特点：对同一输入实例，运行算法A，所得结果是一样的。Algorithms De
14、sign Techniques and Analysis10.2 P类 定义 10.2 判定问题的P类由这样的判定问题组成，它们的yes/no解可以用确定性算法在运行多项式步数内，例如在O(nk)步内得到，其中k是某个非负整数，n是输入大小。也就是说：如果对于某个判定问题，存在一个非负整数k，对于输入规模为n的实例，能够以O(nk)的时间运行一个确定性算法，得到yes或no的答案，则称该判定问题是一个P(Polynomial)类问题。事实上，所有易解问题都是事实上，所有易解问题都是P类问题。类问题。Algorithms Design Techniques and AnalysisP类的问题排序
15、问题：给出一个n个整数的表，它们是否按非降序排列?不相交集问题：给出两个整数集合，它们的交集是否为空?最短路径问题：给出一个边上有正权的有向图G=(V,E)，两个特异的顶点s,t V和一个正整数k，在s到t间是否存在一条路径，它的长度最多是k。Algorithms Design Techniques and AnalysisP类的问题2着色问题:给出一个无向图G，它是否是2可着色的?即它的顶点是否可仅用两种颜色着色，使两个邻接顶点不会分配相同的颜色?注意，当且仅当G是二分图，即当且仅当它不包含奇数长的回路时，它是2可着色的。2可满足问题:给出一个合取范式(CNF)形式的布尔表达式f，这里每个子
16、句恰好由两个文字组成，问f是可满足的吗？Algorithms Design Techniques and Analysis 如果对于任意问题C，的补也在C中，我们说问题类 C在补运算下是封闭的。例如，2着色问题的补可以陈述如下:给出一个图G，它是不2可着色的吗?我们称这个问题为NOT-2-COLOR问题。它是属于P的。定理 10.1 P类问题在补运算下是封闭的。Algorithms Design Techniques and Analysis10.3 NP类 NP类由这样的问题组成，对于这些问题存在一个确定性算法A，该算法在对的一个实例展示一个断言解时，它能在多项式时间内验证解的正确性。即如果
17、断言解导致答案是yes，就存在一种方法可以在多项式时间内验证这个解。Algorithms Design Techniques and Analysis不确定性算法 对于输入x，一个不确定性算法由下列两个阶段组成:猜测阶段 验证阶段 p177Algorithms Design Techniques and Analysis猜测阶段在这个阶段产生一个任意字符串y，它可能对应于输入实例的一个解，也可以不对应解。事实上，它甚至可能不是所求解的合适形式，它可能在不确定性算法的不同次运行中不同。它仅仅要求在多项式步数内产生这个串，即在O(ni)时间内，这里n=|x|，i是非负整数。对于许多问题，这一阶段可
18、以在线性时间内完成。Algorithms Design Techniques and Analysis验证阶段在这个阶段，一个不确定性算法验证两件事首先，它检查产生的解串y是否有合适的形式，如果不是，则算法停下并回答no;另一方面，如果y是合适形式，那么算法继续检查它是否是问题实例x的解，如果它确实是实例x的解，那么它停下并且回答yes，否则它停下并回答no。我们也要求这个阶段在多项式步数内完成，即在O(nj)时间内，这里j是一个非负整数。Algorithms Design Techniques and Analysis 设A是问题的一个不确定性算法，我们说A接受问题的实例I，当且仅当对于输入
19、I存在一个导致yes回答的猜测。换句话说，A接受I当且仅当可能在算法的某次执行上它的验证阶段将回答yes。要强调的是，如果算法回答no，那么这并不意味着A不接受它的输人，因为算法可能猜测了一个不正确解。定义(不确定性算法):设A是求解问题的一个算法，如果算法A以如下猜测+验证的方式工作，称算法A为不确定性(nondeterminism)算法：猜测阶段：对问题的输入实例产生一个任意字串y，在算法的每次运行，y可能不同，因此猜测是以不确定的形式工作。这个工作一般可以在线性时间内完成。验证阶段：在这个阶段，用一个确定性算法验证两件事：首先验证猜测的y是否是合适的形式，若不是，则算法停下并回答no；若
20、是合适形式，则继续检查它是否是问题x的解，如果确实是x的解，则停下并回答yes，否则停下并回答no。要求验证阶段在多项式时间内完成。不确定性算法与不确定性算法与NP类问题类问题Algorithms Design Techniques and Analysis注意对不确定性算法输出yes/no的理解：若输出no，并不意味着不存在一个满足要求的解，因为猜测可能不正确；若输出yes，则意味着对于该判定问题的某一输入实例，至少存在一个满足要求的解。Algorithms Design Techniques and Analysis不确定的算法:伪代码 Void nondetA(String input)
21、String s=genCertif();boolean checkOK=verifyA(input,s)if(checkOK)Output“yes“return checOK为为false时不作反应时不作反应.Algorithms Design Techniques and AnalysisNP类 至于一个(不确定性)算法的运行时间，它仅仅是两个运行时间的和：一个是猜测阶段的时间，另一个是验证阶段的时间。因此它是O(ni)+O(nj)=O(nk)，k是某个非负整数。定义 10.3 判定问题类NP由这样的判定问题组成:对于它们存在着多项式时间内运行的不确定性算法。南京理工大学NP类问题类问题
22、定义(NP类问题):如果对于判定问题，存在一个非负整数k，对于输入规模为n的实例，能够以O(nk)的时间运行一个不确定性算法，得到yes/no的答案，则该判断问题是一个NP(nondeterministic polynomial)类问题。注意：NP类问题是对于判定问题定义的，事实上，可以在多项式时间内应用非确定性算法解决的所有问题都属于NP类问题。例子（图着色问题）Input:(着色数)k,(节点数)5,(图的边)(1,2)(1,4).Guessing 指写出长度为n(节点数)的字符串,例如,RGRBG,RGRB,RBYGO,RGRBY,R%*$等.至少有kn个“guessings”。Chec
23、king 指检查一guessed字符串是否合法及是否是一个k-着色。如果写字符串的时间是O(p1(n),checking时间是O(p2(n);而且p1(n),p2(n)是n的多项式(从而也是输入长度的多项式),则该不确定算法有多项式时间。如果输入的图能k着色则不确定算法停机并给出yes回答。31245Algorithms Design Techniques and Analysis例子考虑问题COLORING，我们用两种方法证明这个问题属于NP类。方法1:设I是COLORING问题的一个实例，s被宣称为I的解。容易建立一个确定性算法来验证，是否确实是I的解。从NP类的非形式定义可得COLORI
24、NG问题属于NP类。Algorithms Design Techniques and Analysis方法 2建立不确定性算法 当图G用编码表示后，一个算法A可以很容易地构建并运作如下 首先通过片顶点集合产生一个任意的颜色指派以“猜测”一个解First。接着，A验证这个指派是否是有效的指派，如果它是一个有效的指派，那么A停下并且回答yes，否则它停下并回答no。请注意，根据不确定性算法的定义，仅当对问题的实例回答是yes时，A回答yes。其次是关于需要的运行时间，A在猜测和验证两个阶段总共花费不多于多项式时间。关于关于P与与NP关系的初步思考关系的初步思考 -从字面含义从字面含义1)若问题属于
25、P类，则存在一个多项式时间的确定性算法，对它进行判定或求解；显然，也可以构造一个多项式时间的非确定性算法，来验证解的正确性，因此，问题也属NP类。因此，显然有 PNP2)若问题属于NP类，则存在一个多项式时间的非确定性算法，来猜测并验证它的解；但不一定能构造一个多项式时间的确定性算法，来对它进行求解或判定。因此，人们猜测P NP，但是否成立，至今未得到证明。P=NP?是计算机科学中最大的问题之一Algorithms Design Techniques and AnalysisAlgorithms Design Techniques and Analysis10.4 NP完全问题 术语“NP完全
26、”表示NP判定问题的一个子类，它们在下述意义上是最难的，即如果它们中的一个被证明用多项式时间确定性算法可解，那么NP中的所有问题用多项式时间确定性算法可解，即NP=P。NP完全问题是完全问题是NP类问题的子类类问题的子类，一个具有特殊性质，一个具有特殊性质与特殊意义的子类。与特殊意义的子类。归约(Reduction)人们普遍认为，人们普遍认为，P=NP不成立不成立 多数人相信，存在至少一个不可多数人相信，存在至少一个不可能有多项式级复杂度的算法的能有多项式级复杂度的算法的NP问题问题这就是这就是NP完全问题完全问题。Reduction(“约化约化”或或“归约归约”)：一个问题一个问题A可以约化
27、为问题可以约化为问题B的含义即的含义即是，可以用解决问题是，可以用解决问题B的解法来解决问题的解法来解决问题A，或者说，问题，或者说，问题A可以可以“变成变成”问题问题B。如：一元一次方程可以如：一元一次方程可以“归约归约”为一元二次方程。为一元二次方程。求解一个一元一次方程和求解一个一元二次方程。那么我们说，前者可以约化为后者，意即知道如何解一个一元二次方程那么一定能解出一 元一次方程。我们可以写出两个程序分别对应两个问题，那么我们能找到一个“规则”，按照这个规则把解一元一次方程程序的输入数据变一下，用在解一元二次方 程的程序上，两个程序总能得到一样的结果。这个规则即是：两个方程的对应项系数
28、不变，一元二次方程的二次项系数为0。按照这个规则把前一个问题转换成后一个问题，两个问题就等价了。Algorithms Design Techniques and AnalysisAlgorithms Design Techniques and Analysis归约(Reduction)问题A可“归约”为问题B直观意义：B的时间复杂度高于或者等于A的时间复杂度。也就是说，问题A不比问题B难。很显然，归约具有一项重要的性质：归约具有传递性。如果问题A可约化为问题B，问题B可约化为问题C，则问题A一定可约化为问题C。定义 10.4:P178NP完全问题NP完全问题是一类具备如下特殊性质的NP类问题（
29、该问题本身）就是一个（该问题本身）就是一个NP类问题类问题 每一个每一个NP类问题都可以通过多项式时间归约化到类问题都可以通过多项式时间归约化到NP类问题类问题NP完全问题完全问题Algorithms Design Techniques and AnalysisNP完全问题的定义完全问题的定义 定义定义9.7(NP完全问题完全问题):令令是一个判定问题，如果问是一个判定问题，如果问题题属于属于NP类问题，并且对类问题，并且对NP类问题中的每一个问类问题中的每一个问题题，都有，都有poly，则称判定问题，则称判定问题是一个是一个NP完完全问题全问题(NP complete problem,NPC
30、)。NP类问题类问题NP完全问题完全问题Algorithms Design Techniques and Analysis对对“NP完全问题完全问题”的评述的评述 NP完全问题是完全问题是NP类问题中最难的类问题中最难的 一类问题，至今已经发现了几千个，一类问题，至今已经发现了几千个，但一个也没有找到多项式时间算法。但一个也没有找到多项式时间算法。如果某一个如果某一个NP完全问题能在多项式时间内解决，则每一完全问题能在多项式时间内解决，则每一个个NP完全问题都能在多项式时间内解决。完全问题都能在多项式时间内解决。这些问题也许存在多项式时间算法这些问题也许存在多项式时间算法，因为计算机科学是相，
31、因为计算机科学是相对新生的科学，肯定还有新的算法设计技术有待发现；对新生的科学，肯定还有新的算法设计技术有待发现；这些问题也许不存在多项式时间算法这些问题也许不存在多项式时间算法，但目前缺乏足够的，但目前缺乏足够的依据来证明这一点。依据来证明这一点。Algorithms Design Techniques and AnalysisP类问题、NP类问题、NP完全问题的关系NP完全完全问题问题NP类问题类问题P类类问题问题Algorithms Design Techniques and AnalysisNP困难问题 难解问题中还有一类问题，虽然也能证明所有的NP类问题可以在多项式时间内变换到问题，
32、但并不能证明也是NP类问题，所以不是NP完全的。但问题至少与任意NP类问题有同样的难度，这样的问题称为NP困难问题。NP类问题类问题NP难问题难问题Algorithms Design Techniques and AnalysisAlgorithms Design Techniques and AnalysisNP-困难的 与 NP-完全的 定义 10.5 一个判定问题称为是NP困难的，如果对于NP中的每一个问题，存在 poly。定义10.6 一个判定问题称为是NP完全的，如果下列两个条件同时成立。(1)在NP中，(2)对于NP中的每一个问题，poly 。NP完全问题和NP困难问题间的差别是：
33、必须是NP类的而可能不在NP中。10.4.1 可满足性问题 可满足性问题即合取范式的可满足性问题，来源于许多实际的逻辑推理的应用。合取范式形如A1A2.An，其中子句Ai(1in)形如：a1a2.ak,其中aj称为文字，为布尔变量或它的否定。一个子句是文字的析取。SAT问题是指：是否存在一组对所有布尔变量的赋值，使得整个合取范式为真?例如 当x1和x3都为真、其余文字任意赋值时，f值为真。121345134fxxxxxxxxx()()()Algorithms Design Techniques and AnalysisAlgorithms Design Techniques and Analy
34、sis可满足性问题 判定问题:SATISFIABILITY.输入:一个合取范式的布尔公式f。问题:f是可满足的吗?定理 10.2 SATISFIABILITY 问题是NP完全的 实际上，可满足性问题被证明是NP完全的第一个问题。Algorithms Design Techniques and Analysis10.4.1 可满足性问题 可满足性可满足性（英语：Satisfiability）问题又叫布林可满足性问题（Boolean satisfiability problem；简写SAT）属于判定问题，它是历史上第一个被证明NP完全问题。1971年，美国的年，美国的Cook证明了证明了Cook定
35、理定理：布尔表达式的布尔表达式的可满足性可满足性(SAT)问题是问题是NP完全的完全的。为了证明SATISFIABILITY是NP完全的，必须证明对NP中的任意问题，有 poly SATISFIABILITY。假设的实例I的规模是n，在p(n)的判定时间里最多有cp(n)个动作，因此可以用cp(n)时间时间构造布尔表达式f，也就是说 poly SATISFIABILITY这就是著名的Cook定理 对于一个确定的逻辑电路，是否存在一种输入使得输出为true，是第一个被证明的NPC问题。其它的NPC问题都是由这个问题约化而来的。我们知道，一个逻辑电路由若干个输入，一个输出，若干“逻辑门”和密密麻麻
36、的线组成，如下图：直观描述这是个较简单的逻辑电路，当输入1、输入2、输入3分别为True、True、False或False、True、False时，输出为True。Algorithms Design Techniques and Analysis直观描述 有输出无论如何都不可能为True的逻辑电路吗？Algorithms Design Techniques and Analysis这个逻辑电路中，无论输入是什么，输出都是False。因此，这个逻辑电路不存在使输出为True的一组输入。NP完全问题（补充）逻 辑电路问题(可满足性问题)属于NPC问题。这是有严格证明的。它显然属于NP问题，并且可以
37、直接证明所有的NP问题都可以约化到它。约化证明过程相当复杂，其大概意思是说任意一个NP问题的输入和输出都可以转换成逻辑电路的输入和输出（想想计算机内部也不过是一些 0和1的运算），因此对于一个NP问题来说，问题转化为了求出满足结果为True的一个输入（即一个可行解）。Algorithms Design Techniques and AnalysisNP完全问题（补充）第一个NP完全问题（Cook定理 1971）可满足性问题是NP完全问题 1972年，Karp证明了十几个问题都是NP完全的。3SAT，3DM，VC，团，HC，划分 更多的NP完全问题 1979年：300多个 1998年：2000多
38、个 这些NP完全问题的证明思想和技巧，以及利用他们证明的几千个NP完全问题，极大地丰富了NP完全理论。Algorithms Design Techniques and Analysis 定理 10.3（归约关系的传递性）设，和”是三个判定问题，有 poly 和 poly”，那么 poly”P179 推论10.1（NP完全性的传递性）如果和是NP中的两个问题，若有 poly ，并且是NP完全的，则是NP完全的。Algorithms Design Techniques and Analysis 根据上面的推论，为了证明一个问题是NP完全的，仅需要证明以下两个条件同时成立(1)NP；(2)存在着一个
39、NP完全问题，使 poly。例子10.5 p179NP完全性的传递性举例 已知哈密顿回路问题是一个NP完全问题，证明货郎担问题也是一个NP完全问题 哈密顿回路问题：给定无向图G=(V,E)，是否存在一条回路，使得图中每个顶点在回路中出现且只出现一次 旅行商问题：给定n个城市和它们的距离矩阵，以及距离L，是否存在从某个城市出发，经过每个城市一次且仅一次，最后回到出发城市且距离小于或等于L的路线 后面是具体说明：对于哈密顿回路问题 中的无向图G=(V,E)，可以用多项式时间构造新的无向图G=(V,E)，使得V=V，E=E。对于E中的每条边(u,v)赋予如下权值：EvunEvuvud,2,1,通过上
40、述转换，转换为旅行商问题 可以证明两个问题等价：（1）G中包含一条哈密尔顿回路，则这条路径上的边共有n条，每条边长度是1，则G中存在一条路径经过每个顶点且一次，并且长度不超过n（2）如果G中存在一条满足旅行商问题的路径，则这条路径经过G中各个顶点一次，且仅一次，最后回到出发顶点，它肯定是一条哈密尔顿回路南京理工大学如何证明一个问题是如何证明一个问题是NP完全的？完全的？根据NP完全问题的定义（满足的两个性质），显然地，证明需要分两个步骤进行：证明问题是NP类问题；即可以在多项式时间内以确定性算法验证一个任意生成的串，以确定它是否为问题的一个解。证明NP类问题中的每一个问题都能在多项式时间内变换
41、为问题。由于多项式问题变换具有传递性，所以，只需证明一个已知的NP完全问题能够在多项式时间内变换为问题.NP类问题类问题已知的已知的NP完全问题完全问题要证明的要证明的?问题问题Algorithms Design Techniques and Analysis10.4.2顶点覆盖、独立集和团集问题顶点覆盖:给出一个无向图G=(V,E)和一个正整数k，是否存在大小为k的子集C V,使E中的每条边至少和C中的一个顶点关联?独立集:独立集:给出一个无向图G=(V,E)和一个正整数k，是否存在k个顶点的子集S V，使得对于每一对顶点u，wS,(u,w)E?团集:团集:给出一个无向图G=(V,E)和一个
42、正整数k，G包含一个大小为k的团集吗?(注意一个G中大小为k的团集是G中k个顶点的一个完全子图。)容易证明所有这三个问题确实是NP的。南京理工大学证明最大团集问题是NP完全的 下面证明团问题属于NP完全问题，证明分两步：1)团集问题属于NP类问题显然，验证图G的一个子图是否构成团只需要多项式时间，所以团问题属于NP类问题。2)可满足性问题poly团集问题Algorithms Design Techniques and Analysis可满足性poly团集问题给出一个有m个子句和n个布尔变元x1,x2,.,xn 的可满足性实例f=C1C2 Cm，我们构造一个图G=(V,E)，其中V是2n个文字的
43、所有出现的集合(注意一个文字是一个布尔变元或它的否定)，并且 E=(xi,xj)|xi和xj位于两个不同的子句，并且xixj)()()(zyxyxzyxfxyyxyzzxAlgorithms Design Techniques and Analysis 引理 10.1 f是可满足的当且仅当G 有一个大小为m的团集。证明:一个大小为m的团集对应于一个m个不同子句中对m个文字的真指派。在两个文字a和b间的边意味着当a和b同时指派真值时没有矛盾。这就得到f是可满足的当且仅当存在着一个对于m个不同子句中的m个文字的真指派，当且仅当G有一个大小为m的团集。可满足性poly团集问题团集问题对于任意一个合取
44、范式，按照如下方式构造相应的图对于任意一个合取范式，按照如下方式构造相应的图G：例如例如 图G的每个顶点对应于f中的每个文字，多次出现的重复表示；若图G中两个顶点对应的文字不互补，且不出现在同一子句中，则将其连线。（a-b连线意味着a和b同时为真）fabbcca()()()Algorithms Design Techniques and Analysis设f有n个子句，则：f可满足 n个子句同时为真 每个子句至少1个文字为真 G中有n个顶点之间彼此相连 G中有n个顶点的团 显然，上述构造图G的方法可在多项式时间内完成，故有：SATpoly团问题。由以上证明可知，团问题是NP完全问题。SAT问题
45、问题poly团问题团问题同时为真，则相连同时为真，则相连Algorithms Design Techniques and AnalysisAlgorithms Design Techniques and Analysis可满足性poly顶点覆盖 给出一个可满足性实例I，我们把它变换为顶点覆盖的一个实例I，设I是一个有m个子句和n个布尔变元x1,x2,.,xn的可满足性实例公式f=C1C2 Cm，构造I如下。1.对于f中的每一个布尔变元xi，G包含一对顶点xi和xi，它们有一条边相连;2.对于每个子句Cj包含的nj个文字，G包含一个大小为nj的团集Cj；3.对于在Cj中的每个顶点w，有一条边连接
46、w到(1)中构造的顶点对(xi,xi)中它相应的文字。这些边称为连通边;4.令mjjnnk1)1(Algorithms Design Techniques and Analysis 引理 10.2 f是可满足的当且仅当构造的图有一个大小为k的顶点覆盖。证明:P181Algorithms Design Techniques and Analysis 引理 10.3 设G=(V,E)是连通无向图，那么S V是一个独立集当且仅当V-S是G的一个顶点覆盖。证明 设e=(u,v)是G中的任意边，S是一个独立集当且仅当u或v至少有一个在V-S中，即V-S是G中的顶点覆盖。顶点覆盖poly独立集Algori
47、thms Design Techniques and Analysis定理 10.4 顶点覆盖、独立集和团集问题是NP完全的。Algorithms Design Techniques and Analysis更多NP完全问题 P182co-NP类由它们的补属于NP类的那些问题组成。例如：旅行商问题的补：给出n个城市和它们之间的距离，不存在长度为k或更少的任何旅程，情况是那样吗?可满足性问题(SAT)的补：给出一个公式f，不存在使得f为真的布尔变量指派，是吗?换言之，f是不可满足的吗?换个角度来看，co-NP类问题也是NP完全问题。10.5 co-NP类Algorithms Design Tec
48、hniques and AnalysisAlgorithms Design Techniques and Analysis10.5 co-NP类 co-NP类由它们的补属于NP类的那些问题组成。定义 10.7 问题对于co-NP类是完全的，如果(1)在 co-NP中(2)对于co-NP中的每一个问题，poly co-NP类问题类问题co-NP完全问题完全问题Algorithms Design Techniques and Analysisco-NP类定理10.5 问题是NP完全的，当且仅当它的补 对于类co-NP是完全的。定理 10.6 重言式问题:给出一个DNF公式f，它是重言式吗?这个问题
49、对于co-NP类是完全的 由此得出下列结论:(1)重言式问题属于P当且仅当co-NP=P,(2)重言式问题属于NP当且仅当co-NP=NP。Algorithms Design Techniques and Analysis10.6 NPI类 定理 10.7 如果问题和它的补 是NP完全的，那么co-NP=NP。换句话说，如果问题和它的补都是NP完全的，那么NP类在补运算下是封闭的。NPI class:the class of problems that they and their complementation are in NP,but are not NP-complete.10.6 N
50、PI类 NP类问题中还有一些问题，人们不知道是属于P类还是属于NP完全问题，还有待于证明其归属。这些问题是NP完全问题的可能性非常小，也因为不相信他们在P中，我们人为地增加另一问题类来接纳这类问题，这个类称为NPI(NP-Intermediate)类。NP完全完全问题问题NP类问题类问题P类类问题问题?Algorithms Design Techniques and Analysis关于关于NPI类问题的评述类问题的评述 NPI类是一个人为定义的、动态的概念，随着人们对问题研究的深入，许多NPI类问题逐渐被明白无误地证明他们原本属于P类问题或NP完全问题。例如：线性规划问题、素数判定问题等，在
