算法设计与分析耿国华第八章.pptVIP

8.3 NP完全问题 如下设计NDTM机M，输入长为n的串w：k(i1,j1)(i2,j2)...(im,jm)，则该机可在O(n3)时间内认知w，其构成是： ①若k＞n， M计算1步便停机在拒绝指令上（非正常情况）。 ②k≤n， M在G的一切k点子集中猜测（选择）一个k点团集，并对之进行验证。确切地说，就是要验证所有猜测的k点子图的任何两个相异点间均有一条边连接 因为一个k点团集共有 条边，每验证一边可从头到尾看完字w（长度为n），故共用O(n3)步。 Chapter 8 8.3 NP完全问题8.3.1 多项式变换与问题归约 NP完全问题是NP类问题的一个子类，如果一个NP完全问题能在多项式时间内得到解决，那么NP类中的每个问题都可以在多项式时间内得到解决，即P=NP成立！因为，任何一个NP问题均可在多项式时间内变换成NP完全问题。 8.3.1 多项式变换与问题归约 假设问题Q存在一个算法A，对于问题Q的输入实例I，算法A求解问题Q得到一个输出O，另外一个问题Q的输入实例是I，对应于输入I，问题Q有一个输出O，则问题Q变换到问题Q有如下三个步骤： Chapter 8 8.3.1 多项式变换与问题归约 Chapter 8 步骤1.输入转换：把问题Q的输入I转换为问题Q‘的适 当输入I； 步骤2.问题求解：对问题Q‘应用算法A产生一个输出O ’； 步骤3.输出转换：把问题Q‘的输出O’转换为问题Π对应于 输入I的正确输出。可用图8.5表示。 8.3.1 多项式变换与问题归约 定义：设Q1 ∑1*和Q2 ∑2* ，若存在函数f满足∑1*→∑2* （1）若存在一个确定算法DTM机，它在多项式时间内可计算函数f； （2）若 则说f是Q1到Q2的一个多项式变换。记作：Q1∝Q2 多项式变换的非形式化描述： 对于问题Q1，Q2 （1）对Q1任何具体问题I，存在多项式时间的确定算法，它计算出f（I），且 （2）对 的解，存在一个多项式时间的确定型算法，得到 的解。 则说：Q1多项式归结为Q2，记作：Q1∝Q2 Chapter 8 8.3.1 多项式变换与问题归约 定理8.5（计算时间下限归约） 若已知问题Q的计算时间下限是T(n)，且问题Q可τ(n)变换到问题Q，即Q∝τ(n)Q，则T(n)－O(τ(n))为问题Q的一个计算时间下限。 定理8.6（计算时间上限归约） 若已知问题Q的计算时间上限是T(n)，且问题Q可τ(n)变换到问题Q，即Q∝τ(n)Π，则T(n)＋O(τ(n))为问题Q的一个计算时间上限。 Chapter 8 8.3.1 多项式变换与问题归约 多项式变换具有以下性质： 性质1：若Q1∝Q2，则Q2∈P，蕴含Q1∈P 性质2：若Q1∝Q2，Q2∝Q3，则Q1∝Q3 性质3：若Q1是NP完全的，则Q1∈P蕴含P=NP 性质4：Q1，Q2∈P，Q1∈NPC且Q1∝Q2，则Q2∈NPC 这些性质可以说明多项式变换的重要意义。性质1说明NP-C问题看成NP中最难的，若某个NPC问题能在多项式时间内解决，则NP所有问题都能在多项式时间内解决；若某个NP中某个问题难解，则所有NPC都难解。所以，NP完全问题具有性质1或说 若 则 。 Chapter 8 8.3.2 NP完全问题定义 Chapter 8 定义：如果问题Q是NP完全问题，则 （1）问题Q属于NP类问题 （2）对NP类问题中的每一个问题Q，都有Q∝pQ。 如果某个问题同工满足定义中的性质(2)，但不满足性质(1)，则称该问题是NP难问题。 定理8.7：设问题Q是NP完全问题，则 (1)Q∈P当且仅当P＝NP； (2)若Q∝p Q’，且Q’∈NP，则Q是NPC问题。 根据上述定理，可以得到证明一个问题是NPC是NPC问题的基本思想，如图8.6。 8.3.2 NP完全问题定义 Chapter 8 NP类问题 已知的NP完全问题 图8.6 证明NPC问题的思路 要证明的NP完全问题 方法1：若Q1∈NPC， ， 存在,由传递性 ， 方法2：若 ,若已知某个问题 ，且有