17-P类问题和NP类问题.

第18讲P类问题与NP类问题杨明指挥信息系统学院软件工程教研中心[e-mail]算法设计与分析2020/1/14第18讲P类问题和NP类问题2020/1/14计算机算法设计与分析2内容判定问题与语言识别问题P类问题NP类问题第18讲P类问题和NP类问题2020/1/14计算机算法设计与分析3最优化问题与判定问题最优化问题寻找一个有最优目标函数值的可行解许多最优化问题是难解问题最优化问题的三个层次判定模式最优值模式最优解模式三个层次的难度是依序增加的判定模式最优值模式最优解模式第18讲P类问题和NP类问题2020/1/14计算机算法设计与分析4最优化问题与判定问题判定问题输出仅为“是”或“否”的一类问题可抽象为所有输入到{yes,no}的映射最优化问题与判定问题最优化问题可简化为判定问题以简单的判定问题为研究对象若判定问题是难解问题，则更为复杂的优化问题也定是难解问题第18讲P类问题和NP类问题2020/1/14计算机算法设计与分析5例：旅行售货员问题—TSP优化问题给定一个赋权完全无向图G=(V,E)，求G的最小费用哈密顿回路。判定问题给定一个赋权完全无向图G=(V,E)和一个数k，图G是否存在一条费用不超过k的哈密顿回路？第18讲P类问题和NP类问题2020/1/14计算机算法设计与分析6判定问题与语言语言对于有限字符集∑，用∑*表示由中字符所组成的所有有限长度字符串的集合。若L是∑*的一个子集，则称L为字符集∑上的一个语言。判定问题与语言通过适当的编码，任何判定问题Q可形式化为语言LL={x∈∑*:Q(x)=1}例PATH={G,u,v,k:G=(V,E),u,v∈V,k∈Z,G中存在一条长度至多为k的路径}第18讲P类问题和NP类问题2020/1/14计算机算法设计与分析7语言识别问题语言识别问题给定x∈∑*，判定x∈L？语言识别问题很适合TM和RAM计算模型图灵机进行语言识别时的两个情况算法A接受语言L:x∈L,A(x)=1;算法A判定语言L:x∈L,A(x)=1;xL,A(x)=0;两者关系对于某些问题，存在接受算法，不存在判定算法。判定语言类是接受语言类的子集第18讲P类问题和NP类问题2020/1/14计算机算法设计与分析8DTM计算模型下的语言识别DTM计算模型移动函数为单值函数终止态qf的区分接受停机状态qy和拒绝停机状态qnDTM程序M接受的语言M接受的字符串LM={x∈∑*:M识别x}M对中LM的字符串停机第18讲P类问题和NP类问题2020/1/14计算机算法设计与分析9DTM算法DTM算法的定义DTM算法只有当一个DTM程序对定义于其输入字符表上的所有可能字符串均停机时，才称其为一个算法。DTM算法时间复杂性函数TM(n)=max{t:x∈∑*,|x|=n,M识别x所需的计算时间t}多项式时间DTM算法存在多项式函数f(n)，使得TM(n)≤f(n)第18讲P类问题和NP类问题2020/1/14计算机算法设计与分析10P类问题P类问题P={DTM能在多项式时间内所接受的语言类}对于所有与DTM等价的计算模型来说，P是不变的。P大致对应计算机上实际可解的那类问题排序问题矩阵连乘问题最小生成树问题图搜索问题……第18讲P类问题和NP类问题2020/1/14计算机算法设计与分析11NP类问题难解问题例：旅行售货员问题、团问题问题有解，蛮力搜索。时间复杂性是指数函数时间还未发现多项式时间DTM算法引入新的计算能力更强的计算模型123456第18讲P类问题和NP类问题2020/1/14计算机算法设计与分析12非确定性图灵机计算模型非确定性图灵机NDTM提出了另一个能力更强的计算模型非确定性图灵机完全是一种假想的机器非确定性图灵机允许移动函数δ具有不确定性δ:QTk→(Q(T{L，R，S})k）(Q(T{L，R，S})k为Q(T{L，R，S})k的一个子集。δ(q;x1,x2,…,xk)可在该子集中中随意选定一个值作为它的函数值。第18讲P类问题和NP类问题2020/1/14计算机算法设计与分析13非确定性图灵机的理解...b...-2-101234...bbb0(1)初始阶段(2)猜想阶段(3)验证阶段….-3-2-10123….|x|b...bbbb......变为DTMGMFCSwq0GMFCSwr/winactiveb第18讲P类问题和NP类问题2020/1/14计算机算法设计与分析14NDTM的语言识别NDTM接受的语言NDTM程序M接受字符串对于每个字符串x∈∑*，对应若干包含一系列计算步的计算路径。若这些计算路径中至少存在一个可接受计算路径，即NDTM程序最终进入可接受状态qfLM={x∈∑*:M接受x}第18讲P类问题和NP类问题2020/1/14计算机算法设计与分析15NDTM算法不确定性算法猜想阶段在多项式时间内产生一个任意字符串yy可能对应输入实例的解，也可能不是解验证阶段使用确定性算法验证字符串y是否解验证算法要求在多项式时间内完成接受拒绝T(n)第18讲P类问题和NP类问题2020/1/14计算机算法设计与分析16NDTM算法NDTM算法NDTM算法M时间复杂性函数TM(n)=max{t:x∈∑*,|x|=n,M接受x所需的计算时间t}多项式时间的NDTM算法存在多项式函数f(n)，使得TM(n)≤f(n)第18讲P类问题和NP类问题2020/1/14计算机算法设计与分析17DTM与NDTM的关系DTM与NDTM的区别DTM的每一步只有一种选择，而NDTM却可以有多种选择。NDTM的计算能力比DTM的计算能力强得多。对于一台时间复杂性为T(n)的NDTM，可用一台时间复杂性为O(CT(n))DTM模拟，其中C为常数。接受拒绝T(n)第18讲P类问题和NP类问题2020/1/14计算机算法设计与分析18NP类问题NP类问题NP={NDTM能在多项式时间内接受的语言类}例：CLIQUE问题判定图G是否包含一个k个顶点的完全子图123456164K=3第18讲P类问题和NP类问题2020/1/14计算机算法设计与分析19CLIQUE∈NP证明过程图采用邻接矩阵编码非确定性算法输入分解计算n和k,O(n2)非确定性选择O(n)确定性验证O(n4)CLIQUE={w#v|w,v∈{0,1}*，w为邻接矩阵表示的图有一个k团}j=0//非确定性算法for(i=1;i=n;i++){m=choice(0,1);//猜想switch(m){case0:a[i]=0;break;case1:a[i]=1;j++;break;}}if(j!=k)thenreject;第18讲P类问题和NP类问题2020/1/14计算机算法设计与分析20另一角度的看NP问题哈密顿路径问题求解：从图G中寻找HC?验证：判定回路C是否是HC?团问题求解：图G中是否存在k团？验证：给定子图是否是k团？猜想ABCDEFGHIJKLMN第18讲P类问题和NP类问题2020/1/14计算机算法设计与分析21多项式时间验证多项式时间可验证语言类VP验证算法定义为两个自变量的算法A(x,y)，其中x是待验证的输入串，y为称为“证据”的二进制串。如果对任意串x∈L，存在证据y，A(x,y)=1。A验证的语言L={x∈∑*:存在证据y∈∑*,满足A(x,y)=1}多项式时间可验证语言类VP={L|L∈∑*:存在一个多项式时间验证算法A(x，y)使得对任意x∈∑*，x∈L当且仅当存在y∈∑*，|y|≤O(|x|)k且A(x，y)=1}。第18讲P类问题和NP类问题2020/1/14计算机算法设计与分析22NP类问题定理VP=NPNP类问题是确定性计算模型下的多项式时间可验证的语言类NP类问题的两个等价定义NP={NDTM能在多项式时间内接受的语言类}NP={DTM能在多项式时间内验证的语言类}接受p(n)第18讲P类问题和NP类问题2020/1/14计算机算法设计与分析23实验题二超市设置问题给定一个城市小区（用图G表示），现需设置k个超市，要求小区居民到超市购物的距离最小？