NP完全性理论ppt课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,二级,三级,四级,五级,*,NP完全性理论,*,第8章,NP,完全性理论,1,NP完全性理论,8.1,计算模型,8.1.1,随机存取机,RAM,8.1.2,随机存取存储程序机,RASP,8.1.3,RAM,模型的变形与简化,8.1.4,图灵机,8.1.5,图灵机模型与,RAM,模型的关系,8.1.6,问题变换与计算复杂性归约,2,NP完全性理论,8.1.1,随机存取机,RAM,1.,RAM,的结构,2.,RAM,程序,一个,RAM,程序定义了从输入带到输出带的一个映射。可以对这种映射关系作2种不同的解释。,3,NP完全性理论,解释一：把,RAM,程序看成是计算一个函数,若一个,RAM,程序,P,总是从输入带前,n,个方格中读入,n,个整数,x,1,，,x,2,，,，,x,n,，并且在输出带的第一个方格上输出一个整数,y,后停机，那么就说程序,P,计算了函数,f(x,1,，,x,2,，,，,x,n,)=y,4,NP完全性理论,解释二：把,RAM,程序当作一个语言接受器。,将字符串,S=a,1,a,2,a,n,放在输入带上。在输入带的第一个方,格中放入符号,a,1,，第二个方格中放入符号,a,2,，,，第,n,个方格中,放入符号,a,n,。然后在第,n+1,个方格中放入0，作为输入串的结束标,志符。如果一个,RAM,程序,P,读了字符串,S,及结束标志符0后，在输出,带的第一格输出一个1并停机，就说程序,P,接受字符串,S,。,5,NP完全性理论,8.1.1,随机存取机,RAM,3.,RAM,程序的耗费标准,标准一：均匀耗费标准,在均匀耗费标准下，每条,RAM,指令需要一个单位时间；每,个寄存器占用一个单位空间。以后除特别注明，,RAM,程序的复杂,性将按照均匀耗费标准衡量。,标准二：对数耗费标准,对数耗费标准是基于这样的假定，即执行一条指令的耗费,与以二进制表示的指令的操作数长度成比例。在,RAM,计算模型下，,假定一个寄存器可存放一个任意大小的整数。因此若设,l(i),是整,数,i,所占的二进制位数，则,6,NP完全性理论,8.1.2,随机存取存储程序机,RASP,1.,RASP,的结构,RASP,的整体结构类似于,RAM,，所不同的是,RASP,的程序是存储在寄存器中的。每条,RASP,指令占据2个连续的寄存器。第一个寄存器存放操作码的编码，第二个寄存器存放地址。,RASP,指令用整数进行编码。,2.,RASP,程序的复杂性,不管是在均匀耗费标准下，还是在对数耗费标准下，,RAM,程序和,RASP,程序的复杂性只差一个常数因子。在一个计算模型下,T(n),时间内完成的输入-输出映射可在另一个计算模型下模拟，并在,kT(n),时间内完成。其中,k,是一个常数因子。空间复杂性的情况也是类似的。,7,NP完全性理论,8.1.3,RAM,模型的变形与简化,1.,实随机存取机,RRAM,在,RRAM,模型下，一个存储单元可以存放一个实数。下列的各,运算为基本运算且每个运算只耗费单位时间。,(1),算术运算+，。,(2)2个实数间的比较()。,(3)间接寻址(整数地址)。,(4)常见函数的计算，如三角函数，指数函数，对数函数等。,优点：能够方便处理实数；,适合于用,FORTRAN,，,PASCAL,等高级语言写的算法。,8,NP完全性理论,8.1.3,RAM,模型的变形与简化,2.,直线式程序,对于许多问题，所设计的,RAM,程序中的转移指令仅用于重复,一组指令，而且重复的次数与问题的输入规模,n,成比例。在这种情,况下，可以用重复地写出相同指令组的方法来消除程序中的循环。,由此，对每一个固定的,n,得到一个无循环的直线式程序。,经过对,RAM,模型的简化，得到直线式程序的指令系统如下：,xy+z,xy-z,xy*z,xy/z,xi,其中,x,，,y,和,z,是符号地址(或变量)，而,i,是常数。,每条指令耗费一个单位时间。,9,NP完全性理论,8.1.3,RAM,模型的变形与简化,3.,位式计算,直线式程序计算模型显然是基于均匀耗费标准的。在对数,耗费标准下，使用另一个,RAM,的简化计算模型，称之为位式计算,(,Bitwise Computation),模型。,除了下列2点外，该计算模型与直线式程序计算模型基本,相同：,(1)假设所有变量取值0或1，即为位变量。,(2)所用的运算是逻辑运算而不是算术运算。,用代表与，代表或，,代表异或，,代表非。,在位式计算模型下，每个逻辑运算指令耗费一个单位时间。,10,NP完全性理论,8.1.3,RAM,模型的变形与简化,4.,位向量运算,(,Bit Vector Operations),若在直线式程序计算模型中，假设所有变量均为位向量，而,且所用的运算均为位操作指令，则得到位向量运算计算模型。,例如，要表示一个有100个顶点的图中从顶点,v,到其余各顶点,间有没有边相连，可以用100位的一个位向量表示。若顶点,v,到顶,点,v,j,之间有边相连，则该位向量的第,j,位为1，否则为0。,缺点：,所需的机器字长要远大于其他模型。,11,NP完全性理论,8.1.3,RAM,模型的变形与简化,5.,判定树,判定树是一棵二叉树。它的每个内结点表示一个形如,xy,的,比较。指向该结点左儿子的边相应于,xy,，标号为。指向该结,点右儿子的边相应于,xy,，标号为。每一次比较耗费一个单位时,间。下图是对,a,，,b,，,c,三个数进行排序的一棵判定树。,在判定树模型下，算法的时间复杂性可用判定树的高度衡量。最大的比较次数是从根到叶的最长路径的长度。,12,NP完全性理论,8.1.3,RAM,模型的变形与简化,6.,代数计算树,ACT,以,x=(x,1,，,x,2,，,，,x,n,),为输入的一棵代数计算树,T,是一棵,二叉树，且：,(1)每个叶结点表示一个输出结果,YES,或,NO,。,(2),每个单儿子内部结点(简单结点),v,表示下列形式运算指令：,op,或,op,或,其中， 和 分别是结点,v,在树,T,中的祖先结点,v1,和,v2,处得到,的结果值，或是,x,的分量；,op+,，,，,/,；,c,是一个常数。,(3)每个有2个儿子的内部结点(分支结点),v,，表示下列形式的,测试指令：,0或 0或 =0,其中， 是结点,v,在树,T,中的祖先结点,v1,处得到的结果值，或是,x,的分量。,13,NP完全性理论,8.1.3,RAM,模型的变形与简化,7.,代数判定树,ADT(Algebraic Decision Tree),在代数计算树,T,中，若将所有的简单结点都压缩到其最近,的子孙分支结点处，并将简单结点处的计算在压缩后的分支结点,处同时完成，则计算结果可看作是输入,x,的一个代数函数,f,v,(x),。,由此引出另一个称为代数判定树的计算模型。,代数判定树,T,是一棵二叉树，且,(1)每个叶结点表示输出结果,YES,或,NO,。,(2),每个内部结点,v,表示一个形如,f,v,(x,1,，,x,2,，,，,x,n,)0,的,比较。其中，,x=( x,1,，,x,2,，,，,x,n,),是输入，,f,v,是一个代数,函数。,14,NP完全性理论,8.1.4,图灵机,1.,多带图灵机,15,NP完全性理论,8.1.4,图灵机,1.,多带图灵机,根据有限状态控制器的当前状态及每个读写头读到的带符号，,图灵机的一个计算步可实现下面3个操作之一或全部。,(1)改变有限状态控制器中的状态。,(2)清除当前读写头下的方格中原有带符号并写上新的带符号。,(3)独立地将任何一个或所有读写头，向左移动一个方格(,L),或向右移动一个方格(,R),或停在当前单元不动(,S),。,k,带图灵机可形式化地描述为一个7元组(,Q,，,T,，,I,，,，,b,，,q,0,，,q,f,),，其中:,(1),Q,是有限个状态的集合。,(2),T,是有限个带符号的集合。,(3),I,是输入符号的集合，,I,T,。,(4)b,是惟一的空白符，,bT-I,。,(5)q,0,是初始状态。,(6),q,f,是终止(或接受)状态。,(7),是移动函数。它是从,Q,T,k,的某一子集映射到,Q,(T,L,，,R,，,S),k,的函数。,16,NP完全性理论,8.1.4,图灵机,1.,多带图灵机,图灵机,M,的时间复杂性,T(n),是它处理所有长度为,n,的输入所需的最大计算步数。如果对某个长度为,n,的输入，图灵机不停机，,T(n),对这个,n,值无定义。,图灵机的空间复杂性,S(n),是它处理所有长度为,n,的输入时，在,k,条带上所使用过的方格数的总和。如果某个读写头无限地向右移动而不停机，,S(n),也无定义。,与,RAM,模型类似，图灵机既可作为语言接受器，也可作为计算函数的装置。,17,NP完全性理论,8.1.5,图灵机模型与,RAM,模型的关系,图灵机模型与,RAM,模型的关系是指同一问题在这2种不同计算模型下的复杂性之间的关系。,定理8-3,对于问题,P,的任何长度为,n,的输入，设求解问题,P,的算法,A,在,k,带图灵机模型,TM,下的时间复杂性为 ，那么，算法,A,在,RAM,模型下的时间复杂性为 。,定理8-4,对于问题,P,的任何长度为,n,的输入，设求解问题,P,的算法,A,在,RAM,模型下，不含有乘法和除法指令，且按对数耗费标准其时间复杂性为 ，那么，算法,A,在,k,带图灵机模型,TM,下的时间复杂性为 。,18,NP完全性理论,8.1.6,问题变换与计算复杂性归约,具体地说，假设有2个问题,A,和,B,，将,问题,A,变换为问题,B,是指：,(1)将问题,A,的输入变换为问题,B,的适当输入。,(2)解出问题,B,。,(3),把问题,B,的输出变换为问题,A,的正确解。,若用,O(n),时间能完成上述变换的第(1)步和第(3)步，则称问题,A,是,(n),时间可变换到问题,B,，且简记为,A,(n),B,。其中的,n,通常为问题,A,的规模(大小)。,当,(n),为,n,的多项式时，称问题,A,可在多项式时间内变换为问题,B,。特别地，当,(n),为,n,的线性函数时，称问题,A,可线性地变换为问题,B,。,通过问题变换的技巧，可以将2个不同问题的计算复杂性联系在一起。这样就可以将一个问题的计算复杂性归结为另一个问题的计算复杂性，从而实现问题的计算复杂性归约。,19,NP完全性理论,8.1.6,问题变换与计算复杂性归约,命题1(计算时间下界归约),：若已知问题,A,的计算时间下界为,T(n),，且问题,A,是,(n),可变换到问题,B,，即,A,(n),B,，则,T(n)-O(n),为问题,B,的一个计算时间下界。,命题2(计算时间上界归约),：若已知问题,B,的计算时间上界为,T(n),，且问题,A,是,(n),可变换到问题,B,，即,A,(n),B,，则,T(n)+O(n),是问题,A,的一个计算时间上界。,问题的变换与问题的计算复杂性归约的关系,：,在命题1和命题2中，当,(n)=o(T(n),时，问题,A,的下界归约为问题,B,的下界，问题,B,的上界归约为问题,A,的上界。,20,NP完全性理论,8.1.6,问题变换与计算复杂性归约,通过问题变换获得问题的计算时间下界的例子,：,(1)判别函数问题：给定,n,个实数 ，计算其判别函数 。,元素惟一性问题可以在,O(1),时间内变换为判别函数问题。任何一个计算判别函数的算法，计算出判别函数值后，再作一次测试，判断其值是否为0，即可得到元素惟一性问题的解。由命题1即知，元素惟一性问题的计算时间下界 也是判别函数问题的一个计算时间下界。,(2)最接近点对问题：给定平面上,n,个点，找出这,n,个点中距离最近的2个点。,在元素惟一性问题中，将每一个实数 ，1,in,，变换为平面上的点( ，0)，1,in,，则元素惟一性问题可以在线性时间内变换为最接近点对问题。,21,NP完全性理论,8.2,P,类与,NP,类问题,8.2.1,非确定性图灵机,8.2.2,P,类与,NP,类语言,8.2.3,多项式时间验证,22,NP完全性理论,8.2.1,非确定性图灵机,非确定性图灵机,（,NDTM,）,：一个,k,带的非确定性图灵机,M,是一个7元组：(,Q,，,T,，,I,，,，,b,，,q,0,，,q,f,),。与确定性图灵机不同的是非确定性图灵机允许移动函数,具有不确定性,，即对于,Q,T,k,中的每一个值(,q;x,1,x,2,x,k,),，当它属于,的定义域时，,Q,(T,L,，,R,，,S),k,中有惟一的一个,子集,(q;x,1,x,2,x,k,),与之对应。可以在,(q;x,1,x,2,x,k,),中随意选定一个值作为它的函数值。,在图灵机计算模型中，移动函数,是单值的,，即对于,Q,T,k,中的每一个值，当它属于,的定义域时，,Q,(T,L,，,R,，,S),k,中只有惟一的值与之对应，称这种图灵机为,确定性图灵机,，简记为,DTM,(Deterministic Turing Machine),。,23,NP完全性理论,8.2.2,P,类与,NP,类语言,P,类和,NP,类语言的定义：,P=L|L,是一个能在,多项式时间内,被一台,DTM,所接受的语言,NP=L|L,是一个能在,多项式时间,内被一台,NDTM,所接受的语言,由于一台确定性图灵机可看作是非确定性图灵机的特例，所以可在多项式时间内被确定性图灵机接受的语言也可在多项式时间内被非确定性图灵机接受。故,P,NP,。,24,NP完全性理论,8.2.3,多项式时间验证,VP=L|L*,，为一有限字符集，存在一个多项式,p,和一个多项式时间验证算法,A(X,，,Y),使得对任意,X*,，,XL,当且仅当存在,Y*,，,|Y|p(|X|),且,A(X,，,Y)=1,。,多项式时间可验证语言类,VP,可定义为：,定理8-5：,VP=NP,。（证明见书本）,例如(,哈密顿回路问题,)：一个无向图,G,含有哈密顿回路吗?,无向图,G,的哈密顿回路是通过,G,的每个顶点恰好一次的简单回路。可用语言,HAM-CYCLE,定义该问题如下：,HAM-CYCLE=G|G,含有哈密顿回路,25,NP完全性理论,从图中的任意一点出发，路途中经过图中每一个结点当且仅当一次，则成为哈密顿回路。,要满足两个条件：,封闭的环,是一个连通图，且图中任意两点可达,经过图（有向图或无向图）中所有顶点一次且仅一次的通路称为哈密顿通路。,经过图中所有顶点一次且仅一次的回路称为哈密顿回路。,具有哈密顿回路的图称为哈密顿图，具有哈密顿通路但不具有哈密顿回路的图称为半哈密顿图。,平凡图是哈密顿图。,26,NP完全性理论,8.3,NP,完全问题,8.3.1,多项式时间变换,8.3.2,Cook,定理,27,NP完全性理论,8.3.1,多项式时间变换,定义：,语言,L,是,NP,完全的当且仅当,(1),LNP,；,(2),对于所有,L,NP,有,L,p,L,。,如果有一个语言,L,满足上述性质(2)，但不一定满足性质(1)，则称该语言是,NP,难,的。,所有,NP,完全语言构成的语言类称为,NP,完全语言类,，记为,NPC,。,设 ， 是2个语言。所谓语言 能在多项式时间内变换为语言 (简记为 ,p,),是指存在映设,f:,，且,f,满足：,(1)有一个计算,f,的多项式时间确定性图灵机；,(2)对于所有,x,，,x,，当且仅当,f(x),。,28,NP完全性理论,8.3.1,多项式时间变换,定理8-6,：设,L,是,NP,完全的，则,(1)LP,当且仅当,P,NP,；,(2),若,L,p,，且 ,NP,，则 是,NP,完全的。,定理8-6的(2)可用来证明问题的,NP,完全性。但前提是：要有第一个,NP,完全问题,L,。,29,NP完全性理论,8.3.2,Cook,定理,定理8-7(,Cook,定理)：,布尔表达式的可满足性问题,SAT,是,NP,完全的。,证明：,SAT,的一个实例是,k,个布尔变量 ，,， 的,m,个布尔表达式 ，,， 若存在各布尔变量 (1,ik),的0，1赋值，使每个布尔表达式 (1,im),都取值1，则称布尔表达式,是可满足的。,SATNP,是很明显的。对于任给的布尔变量 ，,， 的0，1赋值，容易在多项式时间内验证相应的,的取值是,否为1。因此，,SATNP,。,现在只要证明对任意的,LNP,有,L,p,SAT,即可。,（详细证明见书本,P,307,310,）,30,NP完全性理论,8.4.5,子集和问题,（,SUBSET-SUM,）,问题描述：,给定整数集合,S,和一个整数,t,，判定是否存在,S,的一个子集,S,S,，使得,S,中整数的和为,t,。例如，若,S=1,，,4,，,16,，,64,，,256,，,1040,，,1041,，,1093,，,1284,，,1344,且,t=3754,，则子集,S,=1,，,16,，,64,，,256,，,1040,，,1093,，,1284,是一个解。,证明思路：,首先，对于子集和问题的一个实例,，给定一个,“,证书,”,S,，要验证,t=,是否成立，显然可在多项式时间内完成。因此，,SUBSET-SUMNP,。,31,NP完全性理论,8.4.6,哈密顿回路问题,（,HAM-CYCLE,）,证明思路：,首先，已知哈密顿回路问题是一个,NP,类问题。,其次，通过证明3-,SAT,p,HAM-CYCLE,，,得出：,HAM-CYCLENPC,。,问题描述：,给定无向图,G=(V,，,E),，判定其是否含有一哈密顿回路。,32,NP完全性理论,8.4.7,旅行售货员问题,TSP,首先，给定,TSP,的一个实例(,G,，,c,，,k),，和一个由,n,个顶点组成的顶点序列。验证算法要验证这,n,个顶点组成的序列是图,G,的一条回路，且经过每个顶点一次。另外，将每条边的费用加起来，并验证所得的和不超过,k,。这个过程显然可在多项式时间内完成，即,TSPNP,。,其次，旅行售货员问题与哈密顿回路问题有着密切的联系。哈密顿回路问题可在多项式时间内变换为旅行售货员问题。即,HAM-CYCLE,p,TSP,。从而，旅行售货员问题是,NP,难的。,因此，,TSPNPC,。,问题描述：,给定一个无向完全图,G=(V,，,E),及定义在,V,V,上的一个费用函数,c,和一个整数,k,，判定,G,是否存在经过,V,中各顶点恰好一次的回路，使得该回路的费用不超过,k,。,33,NP完全性理论,