Chapter-9 NP完全问题

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,南京理工大学,*,南京理工大学,9 NP,完全问题,NP Complete Problem,南京理工大学,本章内容提要,易解问题与难解问题,P,类问题和,NP,类问题,NP,完全问题,co-NP,类问题,NPI,类问题,P,、,NP,、,co-NP,、,NPI,类之间的区别与联系,NP,完全问题的计算机处理技术简介,形而上者谓之道，,形而,形而下者谓之器,-,易经,系辞,南京理工大学,9.1,引言,9.1.1,易解问题与难解问题,如果对一个问题存在一个算法，时间复杂性为,O(n,k,),，其中,n,是问题规模，,k,是一个非负整数，则称问题存在,多项式时间,算法。这类算法在,可以接受的时间内,实现问题求解，,e.g.,排序、串匹配、矩阵相乘。,现实世界里还存在很多问题至今没有找到多项式时间算法，计算时间是指数和超指数函数（如,2,n,和,n!,），随着问题规模的增长而,快速增长,。,通常将前者看作是,易解问题,，后者看作,难解问题,。,南京理工大学,9.1.2,易解问题与难解问题的主要区别,在学术界已达成这样的共识：把多项式时间复杂性作为易解问题与难解问题的分界线，主要原因有：,1),多项式函数与指数函数的增长率有本质差别,问题规模,n,多项式函数,指数函数,logn,n,nlogn,n,2,n,3,2,n,n!,1,0,1,0.0,1,1,2,1,10,3.3,10,33.2,100,1000,1024,3628800,20,4.3,20,86.4,400,8000,1048376,2.4E18,50,5.6,50,282.2,2500,125000,1.0E15,3.0E64,100,6.6,100,664.4,10000,1000000,1.3E30,9.3E157,南京理工大学,2),计算机性能的提高对易解问题与难解问题算法的影响,假设求解同一个问题有,5,个算法,A1A5,，时间复杂度,T(n),如下表，假定计算机,C2,的速度是计算机,C1,的,10,倍。下表给出了在相同时间内不同算法能处理的问题规模情况：,T(n),n,n,变化,n/n,10n,1000,10000,n=10n,10,20n,500,5000,n=10n,10,5nlogn,250,1842,nn10n,7.37,2n,2,70,223,n,3.16,2,n,13,16,n=n+log10n+3,1,南京理工大学,3),多项式时间复杂性忽略了系数，但不影响易解问题与难解问题的划分,问题规模,n,多项式函数,指数函数,n,8,10,8,n,n,1000,1.1,n,2,0.01n,5,390625,510,8,5,1000,1.611,1.035,10,10,8,10,9,10,1000,2.594,1.072,100,10,16,10,10,10,2000,13780.6,2,1000,10,24,10,11,10,1000,2.4710,41,1024,观察结论：,n100,时，（不自然的）多项式函数值大于指数函数值，但,n,充分大时，指数函数仍然超过多项式函数,。,南京理工大学,9.2 P,类问题和,NP,类问题,这个划分标准是基于对所谓,判定问题,的,求解方式,。,先看看什么是判定问题。事实上，实际应用中的大部分问题问题可以很容易转化为相应的判定问题，如：,排序问题,给定一个实数数组，是否可以按非降序排列,?,图着色问题,：给定无向连通图,G=(V,E),，求最小色数,k,，使得任意相邻顶点具有不同的着色,给定无向连通图,G=(V,E),和正整数,k,，是否可以用,k,种颜色,. ?,南京理工大学,确定性算法与,P,类问题,对判定问题求解，可以采用,确定性算法,定义,9.1(,确定性算法,):,设,A,是求解问题的一个算法，如果在算法的整个执行过程中，每一步只有一个确定的选择，则称算法,A,是确定性算法。,特点：对同一输入实例，运行算法,A,，所得结果是一样的。,定义,9.2(,P,类问题,):,如果对于某个判定问题，存在一个非负整数,k,，对于输入规模为,n,的实例，能够以,O(n,k,),的时间运行一个确定性算法，得到,yes,或,no,的答案，则称该判定问题是一个,P(Polynomial),类问题。,事实上，所有易解问题都是,P,类问题。,南京理工大学,定义,9.3(,非确定性算法,):,设,A,是求解问题的一个算法，如果算法,A,以如下,猜测并验证的方式工作,，称算法,A,为非确定性,(nondeterminism),算法：,猜测阶段,：对问题的输入实例产生一个任意字串,y,，在算法的每次运行，,y,可能不同，因此猜测是以非确定的形式工作。这个工作一般可以在线性时间内完成。,验证阶段,：在这个阶段，用一个确定性算法验证两件事：首先验证猜测的,y,是否是合适的形式，若不是，则算法停下并回答,no,；若是合适形式，则继续检查它是否是问题,x,的解，如果确实是,x,的解，则停下并回答,yes,，否则停下并回答,no,。要求验证阶段在多项式时间内完成。,非确定性算法与,NP,类问题,南京理工大学,注意对非确定性算法输出,yes/no,的理解：,若输出,no,，并不意味着不存在一个满足要求的解，因为猜测可能不正确；若输出,yes,，则意味着对于该判定问题的某一输入实例，至少存在一个满足要求的解。,南京理工大学,NP,类问题,定义,9.4(,NP,类问题,):,如果对于判定问题，存在一个非负整数,k,，对于输入规模为,n,的实例，能够,以,O(n,k,),的时间,运行一个,非确定性算法,，,得到,yes/no,的答案,，则该判断问题是一个,NP(,n,ondeterministic,p,olynomial),类问题。,注意：,NP,类问题是对于判定问题定义的，事实上，可以在多项式时间内应用非确定性算法解决的所有问题都属于,NP,类问题。,南京理工大学,关于,P,与,NP,关系的初步思考,-,从字面含义,1),若问题属于,P,类，则存在一个多项式时间的确定性算法，对它进行判定或求解；显然，也可以构造一个多项式时间的非确定性算法，来验证解的正确性，因此，问题也属,NP,类。因此，显然有,P,NP,2),若问题属于,NP,类，则存在一个多项式时间的非确定性算法，来猜测并验证它的解；但不一定能构造一个多项式时间的确定性算法，来对它进行求解或判定。,因此，人们,猜测,P NP,，但是否成立，至今未得到证明。,南京理工大学,NP,完全问题是,NP,类问题的子类,，一个具有特殊性质与特殊意义的子类。,9.3 NP,完全问题,南京理工大学,问题变换,NP,类问题在最坏情况下的时间复杂性一般都是快速增长的指数函数。我们希望能够,在,NP,类问题内部,找到一种方法，比较两个问题的复杂性。,比较两个问题的计算复杂性的方法是,问题变换,。,I,算法,A,I,O,问题,问题,输入转换,O,输出转换,南京理工大学,多项式时间变换,定义,9.6(,多项式时间变换,):,若在,O(n),时间内完成上述输入,/,输出转换，则称问题以,(n),时间变换到问题,，记为,(n),其中，,n,为问题规模；若在多项式时间内完成上述转换，则称问题以多项式时间变换到问题,，记为,poly,南京理工大学,举例：多项式时间变换,排序问题,的算法,A,，输入为,x,1, x,2,., x,n,输出为非降序序列,x,i1,x,i2,. x,in,；,配对问题,：输入两组数,X=(x,1, x,2,., x,n,),和,Y=(y,1, y,2,., y,n,),，输出是两组元素的非降序依次配对。,求解配对问题，需要进行三个变换,将配对问题的输入,X,Y,变成排序问题的两个输入,I,1, I,2,；,应用算法,A,对,I,1, I,2,分别排序，得到两个排序输出,O,1, O,2,；,将两个排序输出,O,1, O,2,转换成配对问题的输出,O,。,这些操作可以在多项式时间内完成。,南京理工大学,多项式时间变换的性质,传递性,：,设、和是,3,个判定问题，若,(n),，且,(n),，则,(n),。,南京理工大学,NP,完全问题,NP,完全问题是一类具备如下特殊性质的,NP,类问题,（该问题本身）就是一个,NP,类问题,每一个,NP,类问题都可以通过多项式时间化为,NP,类问题,NP,完全问题,南京理工大学,NP,完全问题的定义,定义,9.7(,NP,完全问题,):,令是一个判定问题，如果问题属于,NP,类问题，并且对,NP,类问题中的每一个问题,，都有,poly,，则称判定问题是一个,NP,完全问题,(NP complete problem, NPC),。,NP,类问题,NP,完全问题,南京理工大学,对“,NP,完全问题”的评述,NP,完全问题是,NP,类问题中最难的,一类问题，至今已经发现了几千个，,但一个也没有找到多项式时间算法。,如果某一个,NP,完全问题能在多项式时间内解决，则每一个,NP,完全问题都能在多项式时间内解决。,(?),这些问题也许存在多项式时间算法,，因为计算机科学是相对新生的科学，肯定还有新的算法设计技术有待发现；,这些问题也许不存在多项式时间算法,，但目前缺乏足够的依据来证明这一点。,南京理工大学,P,类问题、,NP,类问题、,NP,完全问题的关系,NP,完全,问题,NP,类问题,P,类,问题,南京理工大学,关于,P,与,NP,关系的再思考,-,从深层意义,至今没有人能证明是否,P NP,。,若,P=NP,，说明,NP,类中所有问题,（包括,NP,完全问题）都具有,多项式时间算法；,若,P NP,，,说明,NP,类中除,P,类之外的所有问题,（包括,NP,完全问题）都不存在多项式时间算法。,无论哪种答案，都将为算法设计提供重要的指导和依据。,目前人们普遍猜测：,P NP,NP,完全,问题,NP,类问题,P,类,问题,南京理工大学,最基本的,NP,完全问题,1971,年，美国的,Cook,证明了,Cook,定理,：,布尔表达式的可满足性,(SAT),问题是,NP,完全的,。,可满足性问题即合取范式的可满足性问题，来源于许多实际的逻辑推理的应用。合取范式形如,A,1,A,2,.,A,n,，其中子句,A,i,(1in),形如：,a,1,a,2,.,a,k,其中,a,j,称为文字，为布尔变量。,SAT,问题是指：是否存在一组对所有布尔变量的赋值，使得整个合取范式为真,?,例如,当,x,1,和,x,3,都为真、其余文字任意赋值时，,f,值为真。,南京理工大学,其他,NP,完全问题,可满足性,(SAT),问题是第一个被证明的,NP,完全问题,。,1972,年，,Karp,证明了十几个问题都是,NP,完全的。这些,NP,完全问题的证明思想和技巧，以及利用他们证明的几千个,NP,完全问题，极大地丰富了,NP,完全理论。,已证明的,NP,完全问题：,SAT,问题,、,最大团问题,、,图着色问题,、,哈密顿回路问题,、,旅行商问题,、,背包问题,、,最长路径问题、,扫雷游戏,南京理工大学,如何证明一个问题是,NP,完全的？,根据,NP,完全问题的定义（满足的两个性质），显然地，证明需要分两个步骤进行：,证明问题是,NP,类问题,；即可以在多项式时间内以确定性算法验证一个任意生成的串，以确定它是否为问题的一个解。,证明,NP,类问题中的每一个问题都能在多项式时间内变换为问题。,由于多项式问题变换具有传递性，所以，只需证明一个已知的,NP,完全问题能够在多项式时间内变换为问题,.,NP,类问题,已知的,NP,完全问题,要证明的,?,问题,南京理工大学,证明一个问题是,NP,完全的,-,以最大团问题为例,团,的概念,：,团是图,G=(V,E),的一个完全子图，该子图（有,k,个顶点）中任意两个顶点都有,1,条边相连。,团问题,：对于给定的无向图,G=(V,E),和正整数,k,，是否存在具有,k,个顶点的团,?,下面证明团问题属于,NP,完全问题，证明分两步：,1),团问题属于,NP,类问题,显然，验证图,G,的一个子图是否构成团只需要多项式时间，所以团问题属于,NP,类问题。,2) SAT,问题,poly,团问题,南京理工大学,SAT,问题,poly,团问题,对于任意一个合取范式，按照如下方式构造相应的图,G,：,例如,图,G,的每个顶点对应于,f,中的每个文字，多次出现的重复表示；,若图,G,中两个顶点对应的文字不互补，且不出现在同一子句中，则将其连线。（,a-b,连线意味着,a,和,b,同时为真）,南京理工大学,设,f,有,n,个子句，则,f,可满足,n,个子句同时为真,每个子句至少,1,个文字为真,G,中有,n,个顶点之间彼此相连,G,中有,n,个顶点的团,显然，上述构造图,G,的方法可在多项式时间内完成，故有：,SAT,poly,团问题。,由以上证明可知，团问题是,NP,完全问题。,SAT,问题,poly,团问题,同时为真，则相连,南京理工大学,NP,难问题,难解问题中还有一类问题，虽然也能证明所有的,NP,类问题可以在多项式时间内变换到问题，,但并不能证明也是,NP,类问题,，所以不是,NP,完全的。但问题至少与任意,NP,类问题有同样的难度，这样的问题称为,NP,难问题。,NP,类问题,NP,难问题,南京理工大学,co-NP,类由它们的,补,属于,NP,类的那些问题组成。例如：,旅行商问题的补：给出,n,个城市和它们之间的距离，不存在长度为,k,或更少的任何旅程，情况是那样吗,?,可满足性问题,(SAT),的补：给出一个公式,f,，不存在使得,f,为真的布尔变量指派，是吗,?,换言之，,f,是不可满足的吗,?,换个角度来看，,co-NP,类问题也是,NP,完全问题。,9.4 co-NP,类问题,南京理工大学,co-NP,类问题的定义,定义,9.7(co-NP,完全问题,):,问题对于,co-NP,类是完全的，若,在,co-NP,中；,对于,co-NP,中的每个问题，有,poly,。,co-NP,类问题,co-NP,完全问题,南京理工大学,9.5 NPI,类问题,NP,类问题中还有一些问题，人们不知道是属于,P,类还是属于,NP,完全问题，还,有待于证明其归属,。,这些问题是,NP,完全问题的可能性非常小，也因为不相信他们在,P,中，我们,人为地增加另一问题类,来接纳这类问题，这个类称为,NPI,(NP-,I,ntermediate),类,。,NP,完全,问题,NP,类问题,P,类,问题,?,?,南京理工大学,关于,NPI,类问题的评述,NPI,类是一个,人为定义的、动态的,概念，随着人们对问题研究的深入，许多,NPI,类问题逐渐被明白无误地证明他们原本属于,P,类问题或,NP,完全问题。,例如：线性规划问题、素数判定问题等，在二者没有被证明他们均属于,P,类问题之前，人们一直将他们归于,NPI,类问题。,南京理工大学,一个例子,线性规划问题,设,AR,mn, xR,n, bR,m,，,在满足,Ax=b,，,x0,约束下，,使目标函数,c,T,x,达到最大值，其中,cR,n,.,长期以来，线性规划问题没有多项式时间解法，也无法证明它是,NP,完全问题。直到,20,世纪,80,年代，这个问题得到解决，发现了多项式时间算法。,NP,完全,问题,线性规划,问题,P,类,问题,?,?,南京理工大学,另一个例子,素数判定问题,给一个整数，判定其是素数,还是合数。,经过一个重要的理论突破，印度,M. Agrawal,教授和他的学生,N. Kayal,和,N. Saxena,于,2002,年宣布发现一个多项式时间算法。,(PRIMES is in P,Annals of Mathematics, 160 (2004), 781793),NP,完全,问题,素数判定,问题,P,类,问题,?,?,南京理工大学,9.6,P,、,NP,、,co-NP,、,NPI,类之间的区别与联系,南京理工大学,NP,完全问题是计算机难以处理的，但是实际中经常遇 到，我们无法回避这些问题。因此，人们提出了解决,NP,完全问题的各种方法：,采用先进的算法设计技术,问题规模不是很大时，采用动态规划法、回溯法、分枝限界法等。,近似算法,很多问题的解允许有一定的误差，只要给出的解是合理的、可接受的。,9.7,NP,完全问题的计算机处理技术简介,南京理工大学,NP,完全问题的计算机处理技术简介,随机算法,例如随机采样算法，穷举,+,挑一,vs.,随机化采样，,(n),或以较小的错误概率为代价，获得计算时间的大幅减少。,并行计算,利用多台,CPU,共同完成一项计算，虽然从原理上说，增强计算性能并不能从根本上解决,NP,完全问题，但这也是解决,NP,完全问题的措施之一。近年来的成就如,129,位,(bit),大整数的分解、“深蓝”下棋程序等。,南京理工大学,NP,完全问题的计算机处理技术简介,智能算法,遗传算法,人工神经网络,模拟退火算法,禁忌搜索算法,DNA,计算,人工免疫算法,蚁群算法,（蚁群算法小游戏）,http:/www.atlas- Intelligence,: a new journal dedicated to reporting on developments in the discipline of swarm intelligence. Published by Springer.,Editor-in-Chief: Marco Dorigo.,南京理工大学,祝你成功！,南京理工大学,