计算复杂性与智能算法课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,*,第,8,课 计算复杂性,第,3,章 计算复杂性与智能算法,第,8,课 计算复杂性,第,9,课 近似算法,第,10,课 智能型算法,第,11,课,线性规划,第,8,课,计算复杂性,算法复杂性问题,图灵机,P,类与,NP,类问题,NP,完全问题,算法的复杂性问题,算法本身能不能解，这个问题应该在求解问题前就应该首先确定，因为如果一个问题是不可解的，那么对这个问题寻求算法的努力也是徒劳的。问题否可解的相关内容，也就是算法复杂性理论所涉及到的内容。包括,P,、,NP,问题的定义以及比较，还有确定型图灵机的介绍。这些内容不足以构成算法复杂性理论体系，但是了解这些内容是复杂性理论深入学习的基础。,计算复杂性问题,可解问题与不可解问题,并不是任何计算问题都能够利用计算机来解决。算法复杂性理论关心的是哪些问题是可以利用计算机来解决的，也就是说是,“,可解的问题,”,；哪些问题是在计算机也解决不了的，也就是,“,不可解的问题,”,。尽管理论上可解的问题在实际中未必能够找到实现的算法，但算法复杂性理论关心的是如何在理论上证明问题的可解，而不关心具体如何实现。,计算复杂性问题,P,问题与,NP,问题,如果一个判定性问题的复杂度是该问题的一个实例的规模,n,的多项式函数，则我们说这种可以在多项式时间内解决的判定性问题属于,P,类问题。,P,类问题就是所有复杂度为多项式时间的问题的集合。通俗地称所有复杂度为多项式时间的问题为易解的问题类，否则为难解的问题。,这种可以在多项式时间内验证一个解是否正确的问题称为,NP,问题,亦称为易验证问题类。,计算复杂性问题,NP,理论的核心问题,如果说,P,问题是,NP,问题的一个真子集，那么可以不必花太多时间寻找大规模输入,NP,问题的解，因为这样的努力都是徒劳的；然而如果能够证明,NP,问题是,P,问题，那么结果就很不一样了，它说明了现在许多的指数复杂度的问题都有多项式复杂度的解法，只不过是暂时找不到而已。,计算复杂性问题,三种常用计算模型,.,随机存取机,RAM,模型,.,随机存取存储程序机,RASP,模型,.,图灵机模型,计算复杂性,问题,随机存取机,RAM,1.,RAM,的结构,计算复杂性,问题,2.,RAM,程序,一个,RAM,程序定义了从输入带到输出带的一个映射。可以对这种映射关系作2种不同的解释。,解释一：,把,RAM,程序看成是计算一个函数,若一个,RAM,程序,P,总是从输入带前,n,个方格中读入,n,个整数,x,1,，x,2,，,，x,n,，,并且在输出带的第一个方格上输出一个整数,y,后停机，那么就说程序,P,计算了函数,f(x,1,，x,2,，,，x,n,)=y,计算复杂性,问题,解释二：,把,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。,计算复杂性,问题,3.,RAM,程序的耗费标准,标准一：,均匀耗费标准,在均匀耗费标准下，每条,RAM,指令需要一个单位时间；每个寄存器占用一个单位空间。,RAM,程序的复杂性一般按照均匀耗费标准衡量。,计算复杂性,问题,标准二：,对数耗费标准,对数耗费标准是基于这样的假定，即执行一条指令的耗费与以二进制表示的指令的操作数长度成比例。在,RAM,计算模型下，假定一个寄存器可存放一个任意大小的整数。因此若设,l(i),是整数,i,所占的二进制位数，则,计算复杂性,问题,随机存取机,RASP,1.,RASP,的结构,RASP,的整体结构类似于,RAM，,所不同的是,RASP,的程序是存储在寄存器中的。每条,RASP,指令占据2个连续的寄存器。第一个寄存器存放操作码的编码，第二个寄存器存放地址。,RASP,指令用整数进行编码。,计算复杂性,问题,2.,RASP,程序的复杂性,不管是在均匀耗费标准下，还是在对数耗费标准下，,RAM,程序和,RASP,程序的复杂性只差一个常数因子。在一个计算模型下,T(n),时间内完成的输入-输出映射可在另一个计算模型下模拟，并在,kT(n),时间内完成。其中,k,是一个常数因子。空间复杂性的情况也是类似的。,计算复杂性,问题,图灵机,1,、图灵机的构成,图灵机由一个控制器和一条无限长的工作带组成，,工作带：划分为许多单元，每个单元可以存放字母表 中的一个符号。,控制器：具有有穷个内部状态和一个读写头。,计算复杂性,问题,单带图灵机结构,计算复杂性,问题,图灵机的工作过程,计算的每一步，控制器处于某个状态，读写头扫描工作带的某一个单元符号；根据当前状态、被扫描单元的内容，决定下一步的执行动作：,把当前单元内容，改写成某一个符号；使读写头停止不动、向左或向右移动一个单元；使控制器转移到某一个状态等等。,计算复杂性,问题,计算开始时，输入符号串放在工作带上，控制器处于初始状态 ，读写头扫描输入符号串左端的第一个符号；,如果对于当前的状态和所扫描的符号，没有下一步的动作，则图灵机就停止计算。,计算复杂性,问题,图灵机形式定义,图灵机 是一个六元组：,S,：控制器的非空有限状态集合；,：有限工作带符号集合，含空白符,B,；,：输入符号字母表， ；,P,0,：初始状态， ；,P,f,：最终状态或接受状态， ；,：转移函数。,计算复杂性,问题,转移函数,的说明,转移函数的定义域：,转移函数的值域：,计算复杂性,问题,L,P,R,读写头的动作,:,L:,左移一个单元；,P:,停止不动；,R:,右移一个单元；,转移函数的含义：,控制器当前状态为,P,、读写头扫描到的符号为,x,时，把控制器状态修改为,P,；把符号修改为符号,x,；使读写头向右移动一个单元。,计算复杂性,问题,图灵机格局定义,是一个图灵机，,M,的格局是一个二元组：,:,是工作带上的内容。,:,表示在此格局下读写头的位置；,1,:,表示处于读写头左边的符号串；,2,:,表示处于读写头右边的符号串。,读写头指向符号串,2,的第一个符号。,计算复杂性,问题,图灵机格局,初始格局： ，,1,为空串；,可接受格局： ，,P,是可接受状态，即 。,停机格局： 中，,2,的第一个符号是,x,，转移函数 没有定义，则称,是停机格局。,计算复杂性,问题,图灵机的计算,是一个有穷、或无穷的格局序列，如果每一个,i+1,都由,i,经过一步得到，称这个序列是一个计算。,计算复杂性,问题,图灵机计算的停机状态,1,）计算是有穷序列 ，是可接受的停机格局，称停机在接受状态。,称图灵机,M,接受符号串,；,2,）计算是有穷序列 ， 不是可接受的停机格局，称停机在拒绝状态。,称图灵机,M,不接受符号串,，或拒绝符号串,;,3,）计算是无穷序列 ，永不停机。,计算复杂性,问题,图灵机对语言的识别,构造一个识别语言 的图灵机,设计思想：,使读写头来回移动，成对地对输入符号串的左端和右端作标记。,如果全部符号都作了标记，则左边的与右边的个数相等， ；否则，,。,计算复杂性,问题,图灵机的构造,S=,P,0,P,1,P,2,P,3,P,4,P,N,;,=,a,b,x,B,;,=,a,b,;,P,f,=,P,4,P,N,;,其中，,P,4,为接受状态，,P,N,为拒绝状态。,计算复杂性,问题,转移函数,(,p,0,a,)=,(,p,0,b,)=,(,p,1,a,)=,(,p,1,x,)=,(,p,1,B)=,(,p,2,b,)=,(,p,2,x,)=,(,p,2,B )=,(,p,3,a,)=,(,p,3,x,)=,(,p,3,B,)=,计算复杂性,问题,对于 ，设,n=2,，图灵机的工作过程如下：,计算复杂性,计算复杂性,问题,计算复杂性,问题, K,带图灵机结构,有,K,个工作带，每个工作带有一个读写头，都可以独立地移动。,计算复杂性,问题, K,带图灵机形式定义,转移函数,的形式：,K,带图灵机格局,若,x,是输入符号串，则初始格局表示为,计算复杂性,问题,确定的图灵机和非确定的图灵机,确定性图灵机,若图灵机的转移函数,是单值的，则称该图灵机为确定性图灵机，记为,DTM,，图灵机每一步的动作都是确定的。,非确定的图灵机,若图灵机的转移函数,是多值的，则称该图灵机为非确定性图灵机，记为,NDTM,。,计算复杂性,问题,图灵机的执行时间,图灵机的计算的长度,设 是一个格局序列，它是图灵机对输入的一个计算。如果,t,是一个可接受的停机格局，则称这个计算是可接受的计算，,t,称为这个计算的长度。,计算复杂性,问题,图灵机的执行时间,图灵机,M,对输入,x,进行计算的执行时间，记为,T,M,(x),，它定义为：,(1),如果,M,对输入,x,有一个可接受的计算，则,T,M,(x),是最短的可接受计算的长度；,(2),如果,M,对输入,x,没有一个可接受的计算，则,T,M,(x) =,。,计算复杂性,问题,图灵机的时间复杂性,图灵机,M,的时间复杂性,T(n),是它处理所有长度为,n,的输入所需的最大计算步数。如果对某个长度为,n,的输入，图灵机不停机，,T(n),对这个,n,值无定义。,计算复杂性,问题,图灵机的空间复杂性,图灵机的空间复杂性,S(n),是它处理所有长度为,n,的输入时，在,k,条带上所使用过的方格数的总和。如果某个读写头无限地向右移动而不停机，,S(n),也无定义。,计算复杂性,问题,图灵机模型与,RAM,模型的关系,图灵机模型与,RAM,模型的关系是指同一问题在这两种不同计算模型下的复杂性之间的关系。,对于问题,P,的任何长度为,n,的输入，设求解问题,P,的算法,A,在,k,带图灵机模型,TM,下的时间复杂性为,T(n),，那么，算法,A,在,RAM,模型下的时间复杂性为,O(T,2,(n),。,计算复杂性,问题,对于问题,P,的任何长度为,n,的输入，设求解问题,P,的算法,A,在,RAM,模型下，不含有乘法和除法指令，且按对数耗费标准其时间复杂性为,T(n),，那么，算法,A,在,k,带图灵机模型,TM,下的时间复杂性为,O(T,2,(n),。,通过问题变换的技巧，可以将不同问题的计算复杂性联系在一起。这样就可以将一个问题的计算复杂性归结为另一个问题的计算复杂性。,计算复杂性,问题,易解的问题和难解的问题,存在多项式时间算法的问题，称为易解的问题。,指数时间算法或排列时间算法的问题，称为难解的问题。,P,类与,NP,类问题,难解问题的计算相关性,计算相关：,某类问题可以归约为另一类问题。,计算相关问题,若它们之一可用多项式时间求解，则其它同类问题也可用多项式时间求解；若它们之一肯定不存在多项式时间算法，则同类的其它问题，也肯定不会找到多项式时间算法。,P,类与,NP,类问题, P,类和,NP,类语言的定义,P=L|L,是一个能在多项式时间内被一台,DTM,所接受的语言,NP=L|L,是一个能在多项式时间内被一台,NDTM,所接受的语言,P,类与,NP,类问题,判定问题和优化问题,判定问题,:,只牵涉到两种情况：,YES,或,NO,，可以容易地表达为语言的识别问题，方便在图灵机上进行求解。,例如：排序问题的判定问题。给定一个整数数组，是否可以按非降顺序排序；,图着色的判定问题。给定无向图 ，是否可用,K,种颜色为,N,中的每一个顶点分配一种颜色，使得不会有两个相邻顶点具有同一种颜色。,P,类与,NP,类问题,优化问题,优化问题牵涉到极值问题。,例：图着色的优化问题。,为图,G,着色，使相邻两个顶点不会有相同颜色时所需要的最少颜色数目。,P,类与,NP,类问题,例：求解为图,G,着色，使相邻两个顶点不会有相同颜色时所需最少颜色数,num,。,令图,G,的顶点个数为,n,，彩色数是,num,，,假定存在一个图,G,着色判定问题的多项式时间算法,coloring,：,BOOL coloring(GRAPH G,int n,int num),则可用下面的方法，利用算法,coloring,来解图着色的优化问题。,P,类与,NP,类问题,void chromatic_number(GRAPH G,int n,int &num),int high,low;,high = n;,low = 1;,while (low=high) ,P,类与,NP,类问题,num = (low + high) / 2;,if (coloring(G,n,num),low = mid + 1;,else,high = mid 1;,num = high;,P,类与,NP,类问题,判定问题转换为优化问题,对算法,coloring,调用,O,(log n),次，就能找出为图着色的最优彩色数。,根据假定，,coloring,是多项式时间算法,;,所以，这个算法也是一个多项式时间算法。,P,类与,NP,类问题, P,类问题,确定性算法,若,A,是问题的一个算法。如果在处理问题的实例时，在算法的整个执行过程中，每一步只有一个确定的选择，就说算法,A,是确定性的算法。,含义：算法执行的每一个步骤，都有确定的选择。重新用同一输入实例运行该算法，所得到的结果严格一致。,P,类与,NP,类问题, P,类判定问题,如果对某个判定问题，存在着一个非负整数,K,，对输入规模为,n,的实例，能够以,O,(n,k,),的时间运行一个确定性的算法，得到,YES,或,NO,的答案，则该判定问题是一个,P,类判定问题。,特性：,P,类判定问题是由具有多项式时间的确定性算法来解的判定问题。,P,类与,NP,类问题,例如：,最短路径判定问题,给定有向赋权图,G,（权为正整数）、正整数,K,、及两个顶点,s,t,，是否存在着一条由,s,到,t,、长度至多为,K,的路径。,可排序的判定问题,给定,n,个元素的数组，是否可以按非降顺序排序。,P,类与,NP,类问题, P,类判定问题的补,改变判定问题的提法，,“,是否不可以,”,、,“,是否不存在,”,的判定问题。,例：,可排序判定问题的补,给定,n,个元素的数组，是否不可以按非降顺序排序。,最短路径判定问题的补,给定有向赋权图,G,（权为正整数）、正整数,K,、及两个顶点,s,、,t,，是否不存在着一条由,s,到,t,、长度至多为,K,的路径。,P,类与,NP,类问题, P,类问题的封闭性,令,C,是一类问题，如果对,C,中的任何问题,C,，的补也在,C,中，则称,C,类问题在补集下封闭。,P,类问题的封闭性,:,P,类问题在补集下是封闭的。,P,类与,NP,类问题,归约的定义,令和,是两个判定问题，如果存在一个确定性算法,A,，可以用多项式的时间，把问题,的实例,I,转换为问题的实例,I,，使得的答案为,yes,，当且仅当,I,的答案是,yes,。就说，,以多项式时间归约于，记为,p, 。,P,类与,NP,类问题, P,类问题的归约性,和,是两个判定问题， 如果,P,，并且， ,p,，则,P,。,P,类与,NP,类问题, NP,类问题,非确定性算法,问题的非确定性算法的分为两个阶段：推测阶段和验证阶段。,推测阶段,对规模为,n,的输入实例,x,，以多项式时间,O,(n,i,),产生输出,y,，而不管,y,的正确性。,P,类与,NP,类问题,验证阶段,以多项式时间,O,(n,j,),的确定性算法验证两件事情：,1,）检查上一阶段的输出,y,是否具有正确的形式。如果,y,不具正确的形式，算法就以答案,no,结束；,2,）如果,y,具有正确的形式，则继续检查 是否是问题的输入实例,x,的解。如果它确实是问题实例,x,的解，则以答案,yes,结束，否则，以答案,no,结束。,P,类与,NP,类问题,旅行售货商的判定问题,给定,n,个城市、正常数,k,、及城市之间的费用矩阵,C,，判定是否存在一条经过所有城市一次且仅一次、最后返回初始出发城市、且费用小于常数,k,的回路。,令,A,是求旅行售货商判定问题的算法。,A,用非确定性的方法，在多项式时间内推测存在着一条回路，假定它是问题的解,;,P,类与,NP,类问题,A,用确定性的算法，在多项式时间内检查：该回路是否是哈密尔屯回路，,如果答案为,yes,，则继续检查该回路的费用是否小于常数,C,，如果答案仍为,yes,，则算法,A,输出,yes,，否则输出,no,。,因此，,A,是求解旅行售货商判定问题的非确定性算法。,P,类与,NP,类问题,非确定性算法的运行时间,非确定性算法的运行时间，是推测阶段和验证阶段运行时间的和。,若推测阶段的运行时间为,O,(n,i,),，,验证阶段的运行时间为,O,(n,j,),，,则对某个非负整数,k,，非确定性算法的运行时间为,O,(n,i,)+,O,(n,j,)=,O,(n,k,),。,P,类与,NP,类问题, NP,类判定问题,如果对某个判定问题，存在着一个非负整数,k,，对输入规模为,n,的实例，能够以,O,(n,k,),的时间运行一个非确定性的算法，得到,yes,或,no,的答案，则该判定问题是一个,NP,类判定问题。,P,类与,NP,类问题,旅行售货商问题,若算法,A,可在推测阶段用多项式时间推测出一条回路，并假定它是问题的解；在验证阶段用多项式时间的确定性算法，检查所推测的回路是否恰好每个城市经过一次，如果是，再进一步判断这条回路的长度是否小于或等于,L,，如果是，答案为,yes,，否则，答案为,no,。,根据定义，旅行售货商判定问题是,NP,类判定问题。,P,类与,NP,类问题, P,类问题和,NP,类问题的差别,P,类问题可以用多项式时间的确定性算法来进行判定或求解；,NP,类问题可以用多项式时间的确定性算法来检查和验证它的解。,P,，必然有,NP,，所以，,P,NP,。,猜测,PNP,。该不等式是否成立、至今还没有得到证明。,P,类与,NP,类问题, NP,完全问题概念,NP,难题,令是一个判定问题，如果对,NP,中的每一个问题,NP,，有,p, ，就说判定问题 是一个,NP,难题。,NP,完全问题,NP,完全问题,令是一个判定问题，如果：,(1),NP,，并且：,(2),对,NP,中的所有问题,NP,，都有,p, ；则称判定问题是,NP,完全的。,NP,难题和,NP,完全问题的差别,是,NP,完全问题， ,是,NP,难题，则必定在,NP,类中，而,不一定在,NP,类中。,NP,完全问题, NP,完全问题的特性,令 和,是,NP,中的两个问题，使得,p, 。如果,是,NP,完全的，则 也是完全的。,NP,完全问题的证明,证明下面两件事情：,(1),NP,，并且：,(2),存在一个,NP,完全问题,，使得 ；,p,。,NP,完全问题, NP,完全问题举例,已知哈密尔顿回路问题是一个,NP,完全问题，证明旅行售货商问题也是一个,NP,完全问题。,哈密尔顿回路问题,给定无向图,G,，是否存在一条回路，使得图中每个顶点在回路中出现一次且仅一次。,NP,完全问题,旅行售货商问题,给定,n,个城市和最短距离,l,，是否存在从某个城市出发、经过每个城市一次且仅一次、最后回到出发城市、且距离小于或等于,l,的路线。,证明旅行售货商问题是,NP,问题。,证明哈密尔顿回路问题,可用多项式时间归约为旅行售货商问题，即,p, 。,NP,完全问题,令,G=(V,E),是哈密尔顿回路问题的任一实例，,|V|=n,。,构造赋权图 ，使得,V=V, E= (u,v)|u,v,V,。,对,E,中的每一条边,u,v,赋予如下的长度：,NP,完全问题,令,l,=n,。,可以由一个算法在多项式时间里完成这个构造。,因此，哈密尔顿回路问题可以用多项式时间归约为旅行售货商问题。,(3),证明,G,中包含一条哈密尔顿回路，当且仅当,G,中存在一条经过各个顶点一次，且全长不超过,l,=n,的路径。,NP,完全问题,1. G,中包含一条哈密尔顿回路，设这条回路是,v,1,v,2,v,n,v,1,。,则该回路也是,G,中一条经过各个顶点一次且仅一次的回路，根据定义的公式，这条回路长度为,n,，因此，这条路径满足旅行售货商问题。,NP,完全问题,2. G,中存在一条满足旅行售货商问题的路径，则这条路径经过,G,中各个顶点一次且仅一次，最后回到起始出发顶点的回路，因此它是一条哈密尔顿回路。,综上所述，哈密尔顿回路问题,可用多项式时间归约为旅行售货商问题成立，即 ,p, 。,所以旅行售货商问题也是一个,NP,完全问题。,NP,完全问题,可满足性问题,合取范式,由若干个析取子句的合取构成的布尔表达式,f,。,例：,合取范式的可满足性,对合取范式,f,的相应布尔变量赋值，使,f,的真值为真，就说布尔表达式,f,是可满足的。,NP,完全问题,可满足性问题定义,判定问题：可满足性问题（,SAT,）,输入：布尔表达式合取范式,f,（,CNF,）,问题：对布尔表达式,f,中的布尔变量赋值,是,否可使,f,的真值为真, Cook,定理,可满足性问题是,NP,完全的。,NP,完全问题, Cook,定理的意义,Cook,定理给出了第一个,NP,完全问题，使得对任何问题 ，只要能够证明 ,NP,，并且,SAT,p,，那么， 就是,NP,完全的。,NP,完全问题,三元可满足性问题,三元合取范式,在合取范式中，每个析取子句恰好由三个文字组成，称为三元合取范式。,三元合取范式的可满足性问题是,NP,完全问题,判定问题：,3_SAT,输入：三元合取范式,f,问题：对布尔表达式,f,中的布尔变量赋值,是否可使,f,的真值为真,NP,完全问题,典型的,NP,完全问题,NP,完全问题,部分,NP,完全问题树,旅行售货商问题（,TSP,）,问题描述,给定一个无向完全图,G=(V，E),及定义在,V,V,上的一个费用函数,c,和一个整数,k，,判定,G,是否存在经过,V,中各顶点恰好一次的回路，使得该回路的费用不超过,k。,NP,完全问题,哈密尔顿回路问题（,HAM-CYCLE,）,问题描述,给定无向图,G=(V，E)，,判定其是否含有一哈密顿回路。,证明思路,首先，已知哈密顿回路问题是一个,NP,类问题。,其次，通过证明3-,SAT,p,HAM-CYCLE，,得出：,HAM-CYCLENPC。,NP,完全问题,团集问题（,CLIQUE,）,问题描述,给定一个无向图,G=(V，E),和一个正整数,k，,判定图,G,是否包含一个,k,团，即是否存在，,V,V，|V,|=k，,且对任意,u，wV,有(,u，w)E。,证明思路,已经知道,CLIQUENP。,通过3-,SAT,p,CLIQUE,来证明,CLIQUE,是,NP,难问题，从而证明团问题是,NP,完全问题。,NP,完全问题,顶点覆盖问题（,VERTEX-COVER,）,问题描述,给定一个无向图,G=(V，E),和一个正整数,k，,判定是否存在,V,V，|V |=k，,使得对于任意(,u，v)E,有,uV,或,vV。,如果存在这样的,V，,就称,V,为图,G,的一个大小为,k,顶点覆盖。,NP,完全问题,证明思路,首先，,VERTEX-COVERNP。,因为对于给定的图,G,和正整数,k,以及一个实例,V，,验证|,V,|=k，,然后对每条边(,u，v)E，,检查是否有,uV,或,vV,，,显然可在多项式时间内完成。,其次，通过,CLIQUE,p,VERTEX-COVER,来证明顶点覆盖问题是,NP,难的。,NP,完全问题,子集和问题（,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,是一个解。,NP,完全问题,证明思路,首先，对于子集和问题的一个实例，,给定一个,“,证书,”,S,，,要验证,t=,是否成立，显然可在多项式时间内完成。因此，,SUBSET-SUMNP；,其次，证明,VERTEX-COVER,p,SUBSET-SUM。,NP,完全问题,图的着色问题（,COLORING,）,问题描述,给定一个无向图,G=(V，E),和一个正整数,k，,用,k,种颜色为,G,中的每一个顶点分配一种颜色，使得不会有两个相邻顶点具有同一种颜色。归结为：,判定问题：,COLORING,输入：无向图,G,(V,E),正整数,k1,问题：是否可用,k,种颜色为图,G,着色,NP,完全问题,证明：图着色问题是,NP,完全问,题,（,1,）图的着色问题是,NP,问题,假定，图,G,有,n,个顶点，可以在线性时间内，用,k,种颜色为,G,中的每一个顶点着色，并假定它就是问题的解；,可以在多项式时间内验证该着色是否就是问题的解。,因此，图的着色问题是,NP,问题。,NP,完全问题,（,2,）可用多项式时间把,3_SAT,问题归约为,COLORING,问题。,设 是,3_SAT,的一个实例，它具有,m,个三元析取子句,c,i,，,1im,，和,n,个布尔变量,x,1,x,2,x,n,，且,n4,。,1,）把,3_SAT,问题变换为,COLORING,问题,构造图,G,(V,E),，使得顶点集,V,为：,其中，,y,i,是新增加的辅助变元。,NP,完全问题,对所有的,1i,jn,，,1km,，使边集,E,为：,显然，可以在多项式时间内完成图,G,的构造,。,NP,完全问题,2,）三元合取范式,f,可满足，当且仅当图,G,可着色。,必要性：,考察边集 ，对所有的,1in,，,y,i,构成图,G,的一个完全子图，,则,y,i,和,y,j,不能为同一种颜色。,若令顶点,y,i,的颜色为,i,，则由,y,i,构成的完全子图可着色。,NP,完全问题,考察边集 及边集, y,i,和,x,j,、,y,i,和 不能为同一种颜色。,若令顶点,x,i,的颜色为,i,或,n+1,，则由,x,i,和,y,i,构成的导出子图可着色,;,同理，若令顶点 的颜色为,i,或,n+1,，则由 和,y,i,构成的导出子图可着色。,NP,完全问题,考察边集 ，,x,i,和 不能为同一种颜色，若令,x,i,和 中，一个顶点的颜色为,i,，另一个顶点的颜色为,n+1,，则由,x,i,、 和,y,i,构成的导出子图可着色。,NP,完全问题,考察边集 和边集 ，,每个,c,k,，,1km,，都包含三个命题变元、或命题变元的否定，而,n4,，因此，每个,c,k,至少与一对顶点,x,i,、及 相连接，从而，每个顶点,c,k,的颜色都不能为,n+1,。,NP,完全问题,如果三元合取范式,f,可满足，则它的每个三元析取子句 都可满足。令,c,k,为：,其中，,u,为,x,或 ，,1km,，,1r,s,tn,，因为,c,k,为真，在,u,r,、,u,s,、,u,t,中，必定有一个为真，假定,u,r,为真。,令,c,k,的颜色为,r,，可使与边集 、,相关联的顶点可着色，从而图,G,可着色。,NP,完全问题,充分性,若图,G,可着色，则与边集 、,相关联的顶点可着色。,对所有的,k,，,1km,，存在着,r,，,1rn,，使得,c,k,的颜色值就是,u,r,的颜色值,r,。,只要,u,r,的真值为真，,c,k,的真值就为真，而三元合取范式,f,也为真。,NP,完全问题,而,u,r,可能是,x,r,或 ，对所有的,r,，,x,r,和,不能为同一种颜色。,x,r,和 中，必有一个颜色值为,r,，另一个颜色值为,n+1,，,c,k,的颜色值不可能为,n+1,，这意味着，在三元合取范式 中，使所有,f,取值为真的的,x,r,和 不能发生矛盾。,综上，三元合取范式,f,是可满足的。,由此，,3_SAT,p COLORING,，,所以，图着色问题,COLORING,是,NP,完全问题。,NP,完全问题,本课结束,下课啦，,休息一会儿！,