算法设计与分析PPT-NP完全理论

1、NP完全理论通向 $1,000,000之路 ?2Overviewn多项式时间算法 对任何规模为n的实例，这些算法的最坏情形时间复杂度为O(nk) ，其中k为常数。n停机问题 n指数级时间算法n容易的和困难的问题n一些有趣的问题 n 最短简单路径最短简单路径vs.最长简单路径问题最长简单路径问题n 欧拉回路欧拉回路vs.汉密尔顿回路汉密尔顿回路n 2-SAT问题问题vs. 3-SAT问题等问题等 3判定问题判定问题 n最优化问题 问题的每个可行解都对应一个目标函数值，求解这类问题的目的是希望得到一个有最优目标函数值的可行解 n判定问题判定问题 回答是否存在一个满足问题要求的解，即解只是简单的回答

2、“是(1)”或“否(0)”。 n最优化问题与它相应的判定问题具有密切的联系，通过限界最优化问题要优化的目标函数值，通常可以把一个最优化问题转化为一个判定问题。 n例如，最短路径问题的目标是找一条从u到v的最短路径，优化的目标函数值是路径的边数。则相应的判定问题(Path)可以描述为：给定一个有向图G，顶点u和v，以及整数k，问图中从u到v是否存在一条最多k条边的路径。 4n约简(Reduction) 实例: 具体问题的输入n多项式约简算法: 一个过程能转化A的任何一个实例到B的某个实例，且过程具有下列性质: （1）该转化过程只需要多项式时间就可以完成； （2）答案是一致的。也就是说，的答案是“

3、是”当且仅当的答案也是“是”。5约简6n在多项式时间内判定问题A的方法 1）任给问题A的一个实例 ，用一个多项式时间约简算法把它转化为问题B的一个实例 ； 2）对实例 ，调用判定B的多项式时间算法； 3）用的答案作为的答案。7n用多项式时间约简算法的思想来证明特定的问题B不存在多项式时间算法n假设我们有一个判定问题A，而且我们知道不存在求解A的多项式时间算法。n假设有多项式时间约简算法可以把A的任意一个实例转化为B的一个实例n这样我们可以用简单的反证法来证明B没有多项式时间的算法。n证明的思路是，假设B有多项式时间算法，则按照上述约简算法的思想，我们也能证明A也有多项式时间算法，这与已知不存在

4、求解A的多项式时间算法矛盾。811.2 P和NPn写一个程序来求解一个最优化问题，作为程序输入的问题实例必须表示成计算机能够理解的符号形式。 n具体问题具体问题 问题实例编码成一个二进制串，由这些问题实例构成的问题n给定具体问题的一个实例I，令实例的规模为n=|I|，一个算法在O(T (n)的时间内得出解，那么就说该算法在O(T (n)的时间内求解了一个具体问题。9n一个具体问题是多项式时间可解的 如果该问题存在一个多项式时间O(nk)求解算法，其中k为一个常数。因此我们可以定义复杂类P为多项式时间可解的具体判定问题的集合。 10形式语言n令字符集是符号的一个有穷集合n字符集上的语言L是由中字

5、符所构成的字符串的集合。例如，给定 = 0, 1，则L = 10, 11,101, 111, 1011, 1101, 10001,.是素数的二进制表示所构成的语言。n令表示空串， 表示空语言，则上所有串的语言表示为*。例如， = 0, 1，则* = , 0, 1, 00, 01, 10, 11, 000,. ，字符集上的任一个语言L是* 的一个子集。11n从形式语言的观点看，任何具体判定问题Q的实例集合仅仅是集合*的一个子集，其中，由于Q完全被产生答案1（是）的实例所刻画，因此我们可以把Q看作是字符集 = 0, 1上的语言 L = x *: Q(x) = 1.n例如，对判定问题Path，我们可

6、以构造相应的语言： PATH = : G = (V, E) is an undirected graph, u, vV, k 0 is an integer, and there exists a path from u to v in G consisting of at most k edges.12n形式语言的框架可以方便地表示判定问题及其相应求解算法之间的关系。 n定义定义11.1对于给定的输入串x 0,1* ，如果算法的输出A(x)=1，则说算法A接受串x。算法A所接受的串x的集合，称为算法接受的语言L = x0, 1*: A(x) = 1。如果A(x) = 0 ，则算法拒绝串x。n

7、从定义11.1可以看出，即使算法A接受一个语言L，但是对于不属于L的串x，算法不一定拒绝串x，例如算法A可能永远循环下去。13n定义定义11.2如果算法A接受L中的每个串x，且算法A拒绝不在L中的串x，则说算法A能够判定语言L。如果算法A接受语言x，且对于任意的xL ，能够在多项式时间O(nk) (n为串的长度，k为一个常数)内接受x，则说算法A在多项式时间内接受语言L。如果算法能够在多项式时间O(nk) (为串的长度，为一个常数)内正确判定x是否属于L，则说算法A在多项式时间内判定语言L。n从上面的定义可以看出，算法接受一个语言，算法只考虑语言中的串，而判定一个语言，则需要考虑属于中的串以及

8、不属于中的串。 14n现在，我们形式化的定义复杂类为语言的集合，成员资格由某种复杂类的度量来确定，例如判定一个给定串是否属于语言所需要的运行时间。 n定义定义11.3 P = L0, 1* : there exists an algorithm A that decides L in polynomial timen由定义11.3可知，P类是由所有可以在多项式时间内所判定的问题组成。事实上，P也是在多项式时间内所接受语言的集合。n定理定理11.1 P = L : L is accepted by a polynomial-time algorithm.1511.2 P and NPn汉密尔顿回

9、路 无向图G = (V, E)的汉密尔顿回路是通过V中每个顶点恰好一次的简单回路。汉密尔顿图(hamiltonian graph)是存在汉密尔顿回路的图。n汉密尔顿回路问题 给定一个无向图，它含有汉密尔顿回路吗? 这个问题已经研究了上百年。现在可用语言HamCycle定义该问题如下： HamCycle = G : G is a hamiltonian graph.n一个算法是怎样判定语言HamCycle？ 16验证算法 n定义验证算法A为带两个参数的算法。一个参数是给定的输入串x（即输入实例），另一个参数是一个证书y（即解）。如果存在一个证书y，使得A(x,y) = 1 ，则说算法A验证了输入

10、串x。因此，我们可以定义能够被算法A所验证的语言 L=x0,1*:there exists y0,1* such that A(x, y)=1.n直观地说，如果对任何的串x，存在证书y，能够用该证书证明x L，而且，对任何x L，没有证书能够证明xL ，则说算法验证了语言。 17n复杂类NPn定义定义11.4复杂类NP指的是一类能够被多项式时间验证算法所验证语言的集合。n一个语言L属于NP当且仅当存在有两个输入的多项式时间算法A和常数c，使得 L = x0, 1* : there exists a certificate y with |y| = O(|x|c) such that A(x,

11、y) = 1.n意思是说，算法A在多项式时间内验证了语言L。n 现在我们知道，NP问题中包括了P问题，即如果L P，则L NP，即P NP，也就是说，NP问题中有些问题是容易的。是否NP P成立是不知道的，但是大多数的研究者相信，P和NP不同类，即PNP。NP类由那些其解能很快验证的问题所构成。n从我们的直觉和经验，我们知道，解一个问题比验证该问题的解要困难得多。很多理论计算机科学家相信，NP确实包括一些不属于P的语言，即NPC。n一个有趣的问题，令co-NP=NP，即NP类在补运算下是否封闭的问题。例如，HamCycleNP，HamCycle的补问题可以描述如下，对于给定的一个无向图，不存在

12、一条汉密尔顿回路吗？co-NP是否等于NP的问题，也仍然悬而未决，但是大多数研究者相信co-NPNP。 $1,000,000 problem ? /millennium/nSolved?!$1,000,000 offered by Clay Mathematical InstituteThe FutureP = NP?2111.3 NP-completeness (NPC)n大多数理论计算机科学家相信PNP是因为他们确实找到一类问题NPC，这类问题有令人非常惊奇的性质，即如果NPC中任何一个问题能够在多项式时间内求解，则NP中的每个问题都能多项式时间

13、求解，即P=NP，尽管研究了大半个世纪，但是还没有找到任何一个NPC问题的多项式时间算法。 n为什么研究 NP-completeness?n能够显示一个问题确实很难n最好寻找近似算法来求解n许多有趣的实际问题事实上是NPC.n怎么样比较语言(问题)的相对难度?22n约简n定义定义11.5 给定一个函数f : 0, 1* 0,1* ，对任意给定的x 0, 1*，如果存在一个多项式时间算法A， A产生输出f (x) ，则称f是多项式时间可计算的。n定义定义11.6 给定语言L1和L2，如果存在多项式可计算的函数f : 0, 1* 0,1*使得对任意的x0, 1*，x L1当且仅当f (x) L2

14、，则说语言L1能多项式时间约简到L2 ，记为L1 P L2 。函数称为约简函数。计算函数f的算法称为约简算法。 23n 图11.2描述了将一个语言多项式时间约简到语言的例子。约简函数f提供了一个多项式时间映射使得如果x L1 ，则f(x) L2 。而且如果x L1 ，则f (x) L2 。这样约简函数f将由语言L1表示的判定问题的任何实例x映射到由L2表示的判定问题的一个实例f(x)。因而，是否f(x) L2的答案提供了是否x L1的答案。f0, 1*0, 1*24FA2yes, f(x) L2no, f (x) L2yes, x L1no, x L1A1xf (x)引理引理11.1如果语言L

15、1, L20,1*使得L1 P L2 ，且L2 P ，则L1 P证明：令A2是判定L2的多项式时间算法，令A是计算从L1到L2约简函数f的多项式时间约简算法，为了证明该引理，只需构造一个能够判定L1的多项式时间算法A1即可。25NP-completenessn多项式时间约简提供了一种证明一个问题至少与另一个问题一样难的形式化方法 n定义定义11.7 给定语言L 0, 1* ， L是NP完全的（NP-complete）当且仅当n (1) L NP；n (2) 对于所有L NP，有L P L 。n 如果有一个语言L满足上述性质(2)，但不一定满足性质(1)，则称该语言L是NP难的（NP-hard）

16、。并记NPC表示所有NP完全语言构成的语言类。NPC是NP中最难的问题。 26n定理定理11.2 如果任何一个NPC问题多项式时间可解，则P=NP。等价地，如果NP中的任何问题没有多项式时间求解算法，则没有NPC问题是多项式时间可解的。PNPNPCNP-hard27电路可满足性问题电路可满足性问题 Circuit satisfiabilityNOTORANDLogic Gates:Inputs:01011111Output:01001n布尔电路是一个无环的有向图，图中每个顶点对应一个逻辑门，它对应简单的布尔函数，例如NOT、AND 和OR。逻辑门的入边是其相应布尔函数的输入，如果入边的起点没有

17、连接到一个逻辑门，则该入边为布尔电路的输入。逻辑门的出边是其相应布尔函数的输出，如果一个输出的终点不再连接到一个逻辑门，则它称为整个布尔电路的输出。n具有一个输出的布尔组合电路是可满足的，指的是它有一组可满足的赋值，使得组合电路的输出为1。 n电路可满足性(Circuit Satisfiablity，简记Circuit SAT)问题指的是，给定一个由逻辑门AND、 OR 和NOT构成的组合电路C，它可满足吗? 从形式语言的角度，可以定义如下 CircuitSAT = C : C is a satisfiable boolean combinational circuit29NOTORANDLo

18、gic Gates:Inputs:01011111Output:01001n引理引理11.2 CircuitSAT属于NP 30Cook-Levin Theoremn引理引理11.3 CircuitSAT是NP难的。n证明：令L是NP中的任何一个语言，我们将描述一个多项式时间算法F ，它计算约简函数f。对于每个二进制串x，f能够将其映射到一个组合电路，即C = f (x) ， 使得x L当且仅当C CircuitSAT 。NPpoly-timeCIRCUIT-SATL定理定理11.3 CircuitSAT是NP完全的。3111.4 NPC的证明的证明 n引理引理11.4 如果L是一个语言，对某

19、个语言LNPC ，使得L P L ，则L是NP难的。而且，如果有LNP ，则LNPC。n证明：因为L是NP完全的，对任意的L NP ，我们有L P L，按照假设有L P L ，这样按照传递性，我们有L P L ，这表明L是NP难的。如果LNP ，则由NP完全的定义，可知L NPC，故所证成立。32n证明一个语言L属于NP完全的证明方法：n首先证明LNP ；n最后证明是NP难的，其证明过程如下：a)首先选择一个已知属于NP完全的语言L；b)设计一个计算函数f的算法，能将L的每个实例x0, 1*映射到L的实例f(x) ；c)证明上述转换函数f满足，对任意的x0, 1*， x L当且仅当有f (x)

20、 L ；d)证明计算函数f的算法是多项式时间算法。33可满足性问题可满足性问题 n布尔公式的可满足性(Satisfiablity，简记为SAT)问题是，给定一个布尔公式，其构成如下：nn个布尔变元： x1, x2, ., xn ；nm个布尔连接符：任何一个布尔连接符（或称布尔函数）连接一个或两个输入，具有一个输出。常见的布尔连接符有, , , ；n括号。n一个布尔公式的真值赋值是关于布尔变元的一组取值，一个可满足的赋值是一个真值赋值，它使得布尔公式的值为1。如果一个公式具有可满足赋值，则称该公式是可满足的。34n可满足性问题指的是一个给定的布尔公式是否是可满足的。用形式语言可以描述如下： SA

21、T = : is a satisfiable boolean formula. n则可满足性问题可以描述为，对于给定的 ， 是否属于SAT。35An examplen = (x1 x2) (x1 x3) x4) x2n赋值x1 = 0, x2 = 0, x3 = 1, x4 = 1, 使得 = (0 0) (0 1) 1) 0 = (1 (1 1) 1 = (1 0) 1 =1. 因此 属于 SAT.36n定理定理11.4 SAT是NP完全的。 证明：首先我们证明SATNP。 对于一个布尔公式以及它的一个可满足赋值构成的证书，验证算法只要将公式中的变元用其赋值代替，然后计算公式的值，这个过程显

22、然能够在多项式时间内完成，如果 =1，则它是可满足的。因此SATNP。37n再证SAT是NP难的。对于已知的NP完全问题CircuitSAT，如果我们能够证明CircuitSAT P SAT，则问题得证。首先我们要证明CircuitSAT的任意一个实例能够在多项式时间内约简到可满足性问题的一个实例。 我们可以按照下列方式进行约简，对于组合电路的每个输入，布尔公式有对应的变元。电路中一个逻辑门能够表达为一个公式，公式由逻辑门的输入和输出决定。 38n例如输出AND逻辑门能够表达成公式 对于图11.7所示的布尔电路，其对应的布尔公式如下 = x10 (x4 x3) (x5 (x1 x2) (x6

23、x4) (x7 (x1 x2 x4) (x8 (x5 x6) (x9 (x6 x7) (x10 (x7 x8 x9)(98710 xxxx39n上述转换能够在多项式时间内完成。由此可见，任意给定一个布尔电路，我们能够在多项式时间内将其约简为布尔公式。这样如果有一个可满足的赋值，电路的每条输入线都有一个确定的值，电路的输出为1。因此每条输入线的赋值对应布尔公式的一个赋值，使得公式中的每个子句的值均为1，所有子句的合取仍然为1。反过来，如果有一组赋值使得布尔公式取值为1，则类似可证明电路是可满足的。因此，我们就证明了SAT是NP难的。综上所述，SAT是NP完全的。 n 定理11.4就是著名的Coo

24、k-Levin定理，简称Cook定理。虽然，本书是从证明CircuitSAT属于NP完全开始的，是因为CircuitSAT的证明比较容易理解，而直接证明SAT属于NP完全则要复杂些，但是证明它们的思路是一样的。事实上，SAT才是第一个被证明的NP完全问题。Cook定理揭开了计算复杂性中NP完全理论的研究。在此基础上关于NP完全问题的研究，成为过去几十年来计算机科学最活跃和重要的研究领域之一。Stephen A. Cook因为其在计算复杂性领域的开创性贡献而获得1982年的图灵奖。41n3-CNF可满足性 布尔公式中的一个文字是布尔变元或者其非的一个出现。如果一个布尔公式，是一些析取子句的合取，

25、而且析取子句是一个文字或者多个文字的析取，则该公式称为合取范式（CNF）。如果CNF中每个子句都精确的有3个不同的文字，则该公式称为3-CNF。n从形式语言的角度定义3-CNF可满足性问题如下 3-CNF-SAT= ：3-CNF公式是可满足的n3-CNF-SAT问题就是给定一个-CNF公式，问它是否是可满足的。 42An examplen布尔公式 (x1 x1 x2) (x3 x2 x4) (x1 x3 x4) 是3-CNF，其中每个子句含有三个不同的文字。n定理定理11.5 3-CNF-SAT是NP完全的。 证明：类似定理11.4的证明，我们能够证明3-CNF-SAT属于NP。下面我们只需证

26、明SAT P 3-CNF-SAT。为止，我们需要构造一个约简算法，它由以下三步组成。43n第一步，对于任意给定的输入公式，我们构造一棵二叉树，文字作为叶子，连接符作为内部节点，对每个连接符引进一个新变元，作为连接符的输出。图11.8给出了由公式 构造出的一棵二叉树。n这棵二叉树现在能够看成一个计算函数值的组合电路。类似定理11.4的证明，我们能够把原始的布尔公式写成根变元和子句的合取，即243121)()(xxxxxx44An examplen = (x1 x2) (x1 x3) x4) x2y3x1x2x2x4x3x1y2y4y5y6y1 = y1 (y1 (y2 x2) (y2 (y3 y

27、4) (y3 (x1 x2) (y4 (y5) (y5 (y6 x4) (y6 (x1 x3)i45n约简算法的第二步就是将上述公式转换为合取范式。对每个子句 ，我们可以构造真值表。真值表的每一行是子句变元的一组可能的赋值以及在这个赋值下，子句的值。对真值表中子句的值为0的赋值，我们可以建立一个析取范式（DNF），它是合取子句的析取，合取子句为文字的合取，它等价于 。通过DeMorgan定律（对所有文字取反，然后将变成，变成），可以得到一个CNF。下面给出一个子句的转化例子。对公式的一个子句，ii46An examplen2=(y1 (y2 x2)y1 y2 x2 2 1 1 1 01 1 0

28、 11 0 1 01 0 0 00 1 1 10 1 0 00 0 1 10 0 0 1(y1 y2 x2) (y1 y2 x2) (y1 y2 x2) (y1 y2 x2)由真值表，可以得到DNF公式应用DeMorgan定律，我们得到CNF公式i=( y1 y2 x2) ( y1 y2 x2) ( y1 y2 x2) (y1 y2 x2)47n约简算法的第三步是进一步转化公式，使得中的每个子句精确含有三个不同的文字。为了完成这一步，我们引进两个辅助变元和。对公式的子句，公式包括下列子句：n如果有三个不同的文字，只需要将其加入到的子句中即可。n如果有2个不同的文字，即Ci = (l1 l2)，只需要将子句(l1 l2 p)(l1 l2 p) 加入到子句中即可。n如果仅有1个文字l，只需要将子句(l p q) (l p q) (l p q) (l p q) 加入到子句中即可。48团问题团问题n令V为无向图G = (V, E)顶点V的子集，当且仅当对于V中的任意顶点u和v，(u,v)是图的一条边时， V定义了