算法分析与设计-第10章.pptVIP

南京邮电大学计算机学院*定义10-3(多项式约化)令Q1和Q2是两个问题，如果存在一个确定算法A求解Q1，而算法A以多项式时间调用另一个求解Q2的确定算法B。若不计B的工作量，算法A是多项式时间的，则称Q1约化(reducedto)为Q2，记做Q1∝Q2。算法A算法BQ1Q2用多项式时间调用若不计工作量,则Q1∝Q2是多项式时间的南京邮电大学计算机学院*定义10-3说明：求解Q1的确定算法是通过调用求解Q2的确定算法完成的,Q1算法自身及对Q2算法实施的调用过程所需的时间都是多项式时间的,那么,只要对Q2存在多项式时间求解算法,Q1就能在多项式时间内求解。算法A算法BQ1Q2用多项式时间调用若不计工作量,则Q1∝Q2是多项式时间的南京邮电大学计算机学院*性质10-1若Q1?P，Q2∝Q1，则有Q2?P。性质10-2若Q1∝Q2，Q2∝Q3，则Q1∝Q3。约化具有传递性南京邮电大学计算机学院*10.1.4NP难度和NP完全问题定义10-4(NP难度)对于问题Q以及任意问题Q1?NP，都有Q1∝Q，则称Q是NP难度(NPhard)的。定义10-5(NP完全)对于问题Q?NP，Q是NP难度的，则称Q是NP完全(NPcomplete)的。南京邮电大学计算机学院*NP类表明：一个问题是NP难度的,不一定是NP完全的.一个NP难度问题，如果不是NP类问题，则不是NP完全的。所有NP完全问题都是NP难度的,反之不然.P类NP难度NP完全南京邮电大学计算机学院*学习这方面知识的现实意义：如果一个问题已经证明是NP难度的，恐怕很难指望能找到一个多项式时间的有效算法。如果所求解问题的实例规模较大，那么明智的做法是选择其他算法设计策略，比如启发式算法、随机算法和近似算法等。南京邮电大学计算机学院*如何确定某个问题Q是否是NP难度的？一般的证明策略由以下两步组成：选择一个已经证明是NP难度问题Q1；求证Q1∝Q。由于Q1是NP难度的，因此所有NP类问题都可约化到Q1，根据约化的传递性，任何NP类问题都可约化到Q，所以Q是NP难度的。如果进一步表明Q本身是NP类的，则问题Q是NP完全的。南京邮电大学计算机学院*10.2Cook定理和证明南京邮电大学计算机学院*10.2.1Cook定理斯蒂芬·库克(StevenCook)于1971年证明了第一个NP完全问题，称为Cook定理。Cook定理表明可满足性问题是NP完全的。CNF可满足性问题也被证明是NP完全的。自从Cook证明了可满足性问题是NP完全的之后，迄今为止至少有300多个问题被证明是NP难度问题，但尚未证明其中任何一个是属于P的。南京邮电大学计算机学院*定理10-1(Cook定理)可满足性问题在P中，当且仅当P=NP。定理10-2CNF可满足性问题是NP完全的。南京邮电大学计算机学院*10.3一些典型的NP完全问题南京邮电大学计算机学院*证明一个问题Q是NP难度（或NP完全）问题的具体步骤如下：（1）选择一个已知其具有NP难度的问题Q1；（2）证明能够从Q1的一个实例I1，在多项式时间内构造Q的一个实例I；（3）证明能够在多项式时间内从I的解确定I1的解。（4）从（2）和（3）可知，Q1∝Q；（5）由（1）和（4）及约化的传递性得出所有NP类问题均可约化到Q，所以Q是NP难度的；（6）如果Q是NP类问题，则Q是NP完全的。南京邮电大学计算机学院*10.3.1?最大集团证明最大集团判定问题是NP完全的。最大集团判定问题是NP类的。因为它是在多项式时间内用不确定算法(程序10-3)求解的判定问题。因此只要证明它是NP难度的NP类P类NP难度NP完全定义10-4(NP难度)对于问题Q以及任意问题Q1?NP，都有Q1∝Q，则称Q是NP难度（NPhard）的。南京邮电大学计算机学院*定理10-3CNF可满足性∝最大集团判定问题。证明分两步证明这一定理：首先寻找一种方法，它能在多项式时间内，从任意给定的CNF公式F构造一个无向图G=(V,E)；然后证明，F是可满足的，当且仅当G有一个规模至少为k的集团。它属于NP类的南京邮电大学计算机学院*第一步：以任意给定的CNF公式F为输入，构造一个相应的无向图G，并且这种构造能够在多项式时间内完成。令是一