NP-完全问题(NP

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

1、NP-完全问题(NPCompleteProblem)ThinkingaboutAlgorithmsAbstractly宫秀军天津大学计算机科学与技术学院gongxj@tju.edu.cn主要内容NP-完全问题：一些典型的例子NP-完全问题：相关定义近似算法两种新的计算模型NP-Complete:涵义N-NondeterministicDeterministicalgorithm:Givenaparticularinput,itwillalwaysproducethesamecorrectoutputNon-deterministic

2、algorithm:withoneormorechoicepointswheremultipledifferentcontinuationsarepossible,withoutanyspecificationofwhichonewillbetakenP-Polynomial(time)ComputablePolynomialtimeisassumedthelowestcomplexityCompleteReducible输入/输出算法复杂性变换/封闭性NP-C:典型的问题（1）问题1图着色问题判定问题：是否存在不超过k种颜色的着色方

3、案?优化问题：求图的最小着色数和着色方案问题2作业调度问题判定问题：是否存在罚款额不超过k的作业调度?优化问题：求最小罚款额调度NP-C:典型的问题（2）问题3Binpacking问题：假设有n种物品，它们的尺寸分别为s1,…,sn，0

4、数等于C的子集?优化问题：求≤C的最大子集和数.可归约为背包问题:pi=wi.NP-C:典型的问题（3）问题6CNF(合取范式)-可满足问题(SAT)判定问题：是否存在真假赋值使得该CNF为真.合取范式例:问题7Hamiltonian回路判定问题问题8TSP(旅行商)问题判定问题：任意给定一整数k，是否存在一长度不超过k的Hamiltonian回路？优化问题NP-C:典型的问题（4）问题9:节点覆盖:无向图中的每一条边都被某些节点关联判定问题：给定无向图G和正整数k,是否存在一k节点覆盖.优化问题：最小节点覆盖问题10:给定一无向图G

5、,k-独立集;最大独立集.问题11:给定一无向图G,k-集团;最大集团.问题10和11可互相转化:边互补图目标函数取整数值时,优化值问题和判定问题等价我们可用二分查找从判定问题解得到优化值的问题的解类P与类NP（ClassP&ClassNP）类P(1)算法输入为问题实例的二进制编码.定义该0/1字符串的长度为输入长度.例如n个节点和m条边的图的长度为Θ(mlogn)(见图13.1).多项式界:如一算法的最坏情形时间复杂度T(n)=O(p(n)),其中p(n)为输入长度n的多项式,则称该算法有多项式界.如一个问题有多项式界的算法,则称该

6、问题有多项式界.类P(2)类P的定义一个算法解决判定问题指:对该判定问题的yes实例,算法要停机并给出yes回答.对no实例算法要停机并给出no的回答.具有多项式界的判定问题组成的类称为类P.多项式的相加,相乘及复合仍为多项式;所以一个有多项式界的算法调用另一有多项式界的算法构成的算法仍有多项式界.类NPNon-deterministic--不确定的算法：对给定输入字符串w,1.Guessing不确定地写一个称为”certificate”(guessed解)的字符串c.c实际上是可行解的一种表示;例如,表示背包问题的n元组,表示图的字

7、符串或邻接矩阵.2.checking使用一确定的有多项式界的算法验证c是否为问题的答案.如果是给出yes,反之,不回答.Polynomial--多项式界:写c和验证的时间为O(q(

8、w

9、)),q()为某一多项式,w为输入长度.不确定的算法:伪代码VoidnondetA(Stringinput)Strings=genCertif();booleancheckOK=verifyA(input,s)if(checkOK)Output“yes“returnchecOK为false时不作反应.类NP：几点说明“不确定”指:对同一输入w,算法使用

10、任意多个不同的c,进行验证.对不同c的这些计算,可以看作是同时进行的.一个不确定算法解决判定问题指:对输入w,如果它有解,不确定算法一定会写出一个c,使得验证阶段能通过,并返回一个yes回答.如果一个判定问题有不确定的多