第九讲NP完全问题.ppt

《第九讲NP完全问题.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、算法设计与分析大连大学信息工程学院计算机系DepartmentofComputer,Informationalschool,DaLianUniversity主讲人：张敏第九讲NP完全问题七个“千僖年数学难题”美国克雷数学研究所于2000年宣布了一件被媒体炒得火热的大事：对七个“千僖年数学难题”的每一个悬赏一百万美元。以下是这七个难题。P问题对NP问题霍奇(Hodge)猜想庞加莱(Poincare)猜想黎曼(Riemann)假设杨－米尔斯(Yang-Mills)存在性和质量缺口纳维叶－斯托克斯方程的存在性与光滑性贝赫(B

2、irch)和斯维讷通－戴尔猜想数学上著名的NP问题，完整的叫法是NP完全问题，简单的写法是NP=P？的问题。P代表Polynomial。NP里面的N，不是Non-Polynomial的N，是Non-DeterministicNP就是Non-deterministicPolynomial-time的问题，也即是非确定的多项式时间。易解的问题和难解的问题存在多项式时间算法的问题，称为易解的问题指数时间算法或排列时间算法的问题，称为难解的问题（旅行商问题）为什么用多项式作为分界点？常见的算法大致可分为两类：多项式时间内可以实

3、现的指数时间内可以实现的好算法应该与计算模型无关计算时间总是相对于一种计算模型而言的广义Church-Turing命题给定两个计算模型A和B，那么存在一个多项式p，使得对任何算法有A实现的时间（B实现的时间）为p判定问题和优化问题判定问题只牵涉到两种情况：yes或no排序问题的判定问题:给定一个整数数组，是否可以按非降顺序排序；图着色的判定问题：给定无向图G=(V,E)，是否可用k种颜色为V中的每一个顶点分配一种颜色，使得不会有两个相邻顶点具有同一种颜色。优化问题牵涉到极值问题图着色的优化问题：为图G=(V,E)着色，

4、使相邻两个顶点不会有相同颜色时所需要的最少颜色数目。一般地，优化问题比他们相应的判定问题难以解决。判定问题转换为优化问题例：求解为图G=(V,E)着色，使相邻两个顶点不会有相同颜色时所需最少颜色数。令图G的顶点个数为n，彩色数是num，假定存在一个图着色判定问题的多项式时间算法BOOLcoloring(GRAPHG,intn,intnum)则可用下面的方法，利用算法coloring来解图着色的优化问题。voidchromatic_number(GRAPHG,intn,int&num){inthigh,low;high=

5、n;low=1;while(low<=high){num=(low+high)/2;if(coloring(G,n,num))low=mid+1;elsehigh=mid–1;}num=high;}对算法coloring调用O(logn)次，就能找出为图着色的最优彩色数。确定性算法定义A是问题∏的一个算法。如果在处理问题∏的实例时，在算法的整个执行过程中，每一步只有一个确定的选择，就说算法A是确定性的算法。算法执行的每一个步骤，都有确定的选择重新用同一输入实例运行该算法，所得到的结果严格一致。P类判定问题定义：如果对某

6、个判定问题∏，存在着一个非负整数k，对输入规模为n的实例，能够以O(nk)的时间运行一个确定性的算法，得到yes或no的答案，则该判定问题∏是一个P类判定问题。特性：P类判定问题是由具有多项式(Polynomial)时间的确定性算法来解的判定问题例：最短路径判定问题SHORTESTPATH：给定有向赋权图G=(V,E)（权为正整数）、正整数k、及两个顶点s,t∈V，是否存在着一条由s到t、长度至多为k的路径。可排序的判定问题SORT：给定个元素的数组，是否可以按非降顺序排序。归约归约的定义:令∏和∏’是两个判定问题如果

7、存在一个具有如下性能的确定性算法A可以用多项式的时间，把问题∏’的实例I’转换为问题∏的实例I，使得I’的答案为yes，当且仅当的I答案是yes。就说，∏’以多项式时间归约于∏，记为∏’∝p∏。P类问题的归约性定理:∏和∏’是两个判定问题，如果∏∈P，并且∏’∝p∏，则∏’∈P。非确定性算法问题∏的非确定性算法的两个阶段：推测阶段和验证阶段。推测阶段：对规模为n的输入实例x，以多项式时间O(ni)产生输出y，而不管y的正确性验证阶段：以多项式时间O(nj)的确定性算法验证两件事情：检查上一阶段的输出y是否具有正确的形式

8、。如果y不具正确的形式，算法就以答案no结束；如果y具有正确的形式，则继续检查y是否是问题的输入实例x的解。如果它确实是问题实例x的解，则以答案yes结束，否则，以答案no结束。例:货郎担的判定问题给定n个城市、正常数k、及城市之间的费用矩阵C，判定是否存在一条经过所有城市一次且仅一次、最后返回初始出发城市、且费用小于常数k的回路