第九章-NP完全性理论与近似计算.ppt

第9章NP完全性理论与近似计算,上海大学计算机学院,9.1计算模型9.1.1随机存取机RAM9.1.2随机存取存储程序机RASP9.1.3图灵机9.2P类与NP类问题9.2.1非确定性图灵机9.2.2P类与NP类语言9.2.3多项式时间验证9.3NP完全问题9.3.1多项式时间变换,本章主要知识点,9.3.2一些典型的NP完全问题9.4NP完全问题的近似算法9.4.1近似算法的性能9.4.2顶点覆盖问题的近似算法9.4.3旅行售货员问题近似算法9.4.4集合覆盖问题的近似算法9.4.5子集和问题的近似算法,引言,1、何为“好的”算法？,Cobham1964和Edmonds1965首先加以区别。Edmonds把多项式时间算法与“好的”算法等同看待，并猜想某些整数规划问题可能不能用这种“好的”算法求解。一般观点：认为指数时间算法不应该算作“好的”算法。大多数指数时间算法只是穷举搜索法的变种多项式时间算法通常只有在对问题的结构有了某些比较深入地了解之后才有可能给出计算机科学家们：多顶式时间算法和指数时间算法之间的区别明显。,2、什么问题“易计算”？“难计算”？,只有用多项式时间算法解决的问题才能认为“易计算”的。一般，如果一个问题困难到不可能用多项式时间算法求解，则认为这个问题是“难解的”。,上述按能否用“多项式时间算法解决问题”来理解一个问题是否“易计算”或“难解的”是不深刻的。,3、有关时间复杂性问题的探讨,时间复杂性是一种最坏情况的度量。时间复杂性为2n的算法仅仅表示至少有一个规模为n的问题实例需要这么多的运算时间，而大多数问题实例可能需要远比2n少得多的时间。例如：几个著名的算法线性规划的单纯形算法：已经证明具有指数时间复杂性Kleex1,x2,xk)，当它属于的定义域时，Q(TL，R，S)k中有惟一的一个子集(q;x1,x2,xk)与之对应。运行时可以在(q;x1,x2,xk)中随意选定一个值作为它的转移。,3.非确定性图林机接受的语言,（1）x被非确定性图林机接受，当且仅当，存在一个计算步骤，使从q0开始，经过一系列计算步骤后，最终进入终止状态qf,就说TM接受字符串x。（2）被非确定性图林机NDTMM接受的语言：能被NDTM接受的所有字符串的集合，记作L(M)。,4、非确定性图灵机的时间复杂性,非确定性图灵机NDTM对输入x的时间复杂性：有计算步骤，从初态到终态的计算步数非确定性图灵机NDTM的时间复杂性T(n)：是它处理所有长度为n的输入x，有计算步骤，使NDTM接受x，其所需的最大计算步数。如果对某个长度为n的输入，图灵机不停机，T(n)对这个n值无定义。,9.2.2P类与NP类语言,1、P类与NP类语言,P类和NP类语言的定义：P=L|L是一个能在多项式时间内被一台DTM所接受的语言NP=L|L是一个能在多项式时间内被一台NDTM所接受的语言,由于一台确定性图灵机可看作是非确定性图灵机的特例，所以可在多项式时间内被确定性图灵机接受的语言也可在多项式时间内被非确定性图灵机接受。故PNP。,NP,P,2、非确定性RAM或RASM计算模型,在指令系统中加入非确定性选择指令Choice(L1,L2,Lk)其中，L1,L2,Lk是标号在对数耗费下，可用非确定性RAM或RASM计算模型定义NP类：NP=L|L是一个能在多项式时间内被一台非确定性RAM或RASM下所接受的语言,3、计算复杂性理论中的核心问题,P=NP？,4、非确定性图灵机的操作方式,猜测路径（或解、点集）验证路径或解,5、NP类语言举例无向图的团问题,该问题的输入是一个有n个顶点的无向图G=(V，E)和一个整数k。要求判定图G是否包含一个k顶点的完全子图(团)，即判定是否存在VV，|V|=k，且对于所有的u，vV，有(u，v)E。,输入的表示：用邻接矩阵表示图G，用二进制串表示整数k，则团问题的一个实例可用长度为n2+(logk)+1的二进位串表示。邻接矩阵中的元素是0或1,非确定性的图林机NDTM的实现,猜测路径（或解、点集）：用非确定性选择指令选出包含k个顶点的候选顶点子集V验证路径或解：确定性地检查该子集V是否是团问题的一个解。若V是一个团则接受输入，否则拒绝输入。这显然可以在O(n4)时间内完成。,初始化：算法的第一阶段将输入串w#v分解，并计算出n=，以及用v表示的整数k。若输入不具有形式w#v或|w|不是一个平方数就拒绝该输入。显而易见，第一阶段可在时间内完成。,9.2.3多项式时间验证,多项式时间可验证语言类VP可定义为：,VP=L|L*，为一有限字符集，存在一个多项式p和一个多项式时间验证算法A(X，Y)使得对任意X*，XL当且仅当存在Y*，|Y|p(|X|)且A(X，Y)=1。,X*为输入字符串，Y*为证书，A用Y来证明XL，称A在多项式时间内验证X,定理9-1：VP=NP。,9.3NP完全问题,9.3.1多项式时间变换,1、多项式时间变换定义,多项式时间变换定义,设，是2个语言。所谓语言能在多项式时间内变换为语言(简记为p)是指存在映身f:，且f满足：(1)有一个计算f的多项式时间确定性图灵机；(2)对于所有x，x，当且仅当f(x)。,L1,L2,f,f未必是多项式,2、NP完全语言类定义,定义：语言L是NP完全的当且仅当(1)LNP；(2)对于所有LNP，有LpL。定义：语言L是NP难的，如果语言L满足上述性质(2)，但不一定满足性质(1)定义：所有NP完全语言构成的语言类称为NP完全语言类，记为NPC。,3、引理与性质,引理：若APB，且BP，则AP,性质：（1）APA，（2）若APB，BPC，则APC,4、多项式时间变换的有关定理,定理9-2：设L是NP完全的，即LNPC，则(1)LP当且仅当PNP；(2)若Lp，且NP，则是NP完全的。,定理9-2的(2)可用来证明问题的NP完全性。但前提是：要有第一个NP完全