计算机算法设计与分析第十章NP-Hard和NP-Complete

10.1基本概念10.1.1不确定的算法10.1.2NP-Hard和NP-Complete类10.3NP-Hard问题实例第十章NP-Hard和NP-Complete1预备知识算法时间复杂度的渐进表示多项式时间算法与非多项式时间算法10.1基本概念2确定算法运算结果是唯一确定的之前介绍的算法都是确定算法确定算法可以在确定型图灵机上执行不确定算法运算结果不是唯一确定的不确定算法可以在非确定型图灵机上执行10.1.1不确定的算法3图灵机1936年图灵提出了一个抽象计算模型──

图灵机，并用它来精确定义可计算函数。图灵机的基本思想是模拟人用纸笔进行数学运算的过程，这个运算过程可分解为下面两种简单的动作：

1.在纸上写或擦除某个符号；

2.把注意力从纸的一个位置移动到另一个位置。在每个阶段将由执行运算的人决定下一步的动作，而他的决定依赖于此人当前所关注的是纸上哪个位置的符号，以及此人当前思维的状态。

4TuringMachine5DeterministicTuringMachine定义一台图灵机由一个八元组所组成TM=(Q,T,I,δ,b,q0,

qaccept,qreject)其中Q：一个有限状态集；

T：一个有限符号集（字母表）；

I：输入字符集，I

T；

b：空符，b∈T－I；

δ：Q×T的子集→Q×(T×{L,R,S})，即转移函数或有限状态控制函数，其中L,R表示读写头左移或右移，S表示读写头原地不动；

q0：表示初始状态；

qaccepr：表示终止（接受）状态；

qreject：表示拒绝状态。这里规定δ是单值映射，所以也称为确定型图灵机。6一个例子例：设TM=({0,1,10,11},{0,1,“”(空格)},{0,1},δ,0)，做一个以1的个数表示数值的整数加法运算,在磁带上的数据设为0000001110110000，就是3+2的意思。转移函数δ定义如下：

0,0→0,0R

0,1→1,1R

1,0→10,1R

1,1→1,1R

10,0→11,0L

10,1→10,1R

11,0→

E

11,1→

S在

xx,y

→

aa,bb

中，xx是当前状态，y是当前格子的值，aa是程序下一步的状态，b是当前格的修改值。例如第一行指令

0,0→0,0R，意思就是如果机器读到格子的值是0，就将其仍变成0，状态变为0，读写头向右移动一格。最后两行中的E代表错误，S代表停机。

7图灵机的格局序列

（粗体的字符表示读写头的当前位置）

步数状态磁带步数状态磁带1000000011101100009100000011101100002000000011101100001010000001110110000300000001110110000111000000011111100004000000011101100001210000000111111000050000000111011000013100000001111110000600000001110110000141100000011111100007000000011101100001500000001111100000 (停机)810000001110110000

8其他类型的图灵机双向无限带图灵机。其带子向左向右都是无限长的，与确定型图灵机基本模型不同的是，它的带子没有左端、带头永远不会走出两端。多带多头图灵机。它具有一个有穷控制器，k个带头和k条带子，每条带子都是双向无穷的，并且各带头在操作时相互独立，除改写带符、左右移动外，还可以保持不动。非确定型图灵机。这种类型的图灵机具有一个有限控制器和一条单向无限带，对于一个给定的状态，机器的下一动作可以有穷多个选择，每个选择包括一个新状态，一个要打印的带符号和一个带头移动方向。9非确定型图灵机定义:

一个非确定型图灵机（NDTM）由下述八元组给出：

NDTM=(Q，T，I，δ，b，q0，qaccept，qreject)

其中Q,T,I,b,q0

和qr

的定义与确定型图灵机的相同，唯一的区别在于状态控制函数（转移函数）δ。非确定型图灵机的状态控制函数δ给出的下一个动作不是唯一确定的,即δ为多值映射,它的值域是一个有穷集合A。因此非确定型图灵机在下一时刻的动作可以有多种选择。在处理问题时，对于δ(q1,al,…,ak)的多个值，非确定型图灵机对于其中任意一个值都存在一个格局序列可以推导下去，只要其中有一种可以到达终止状态qaccept，就说该问题是可以处理的（输入字符串被接受或函数是可计算的）。10在SPARKS语言中增加：choice(S)failuresuccess例10.1不确定机上的检索算法例10.2不确定机上的排序算法不确定算法的表示11非确定机在现实技术条件下是不存在的，是为了分析计算机复杂度难题而虚构的理论模型。可以设想非确定机在执行choice(S)语句时，具有主动选择正确值（导致success）的能力，这是通过同时复制大量副本实现的。非确定算法的设计思路一般是，先随机生成解，再检查是否为答案。不确定算法的执行12只关心唯一输出的不确定算法不确定的判定算法只产生0/1输出0:当且仅当没有一种选择可导致success1:当且仅当至少存在一种选择导致success输出隐含于success和failure，此外无输出语句最优化问题和判定问题是相互对应的，很多问题满足：判定问题在多项式时间内求解当且仅当对应的最优化问题可以在多项式时间内求解，反之亦然不确定的判定算法13不确定算法的时间复杂度14可满足性问题[SAT]15可满足性问题时间复杂度O(n)1610.1.2NP-Hard和NP-Complete对于算法A，如果存在多项式P()，使得对A的每个大小为n的输入，A的计算时间为O(P(n))，则称A具有多项式时间复杂度。P是所有可在多项式时间内用确定算法求解的判定问题的集合。NP是所有可在多项式时间内用不确定算法求解的判定问题的集合。17cook定理【cook定理】可满足性(SAT)在P内，当且仅当P=NP。SAT问题如果有多项式解，当且仅当P=NP18约化（多项式变换）理解：算法L1约化为算法L2当且仅当存在一个多项式时间的确定算法可将算法L1转换为算法L2【算法L2的解决意味着L1的解决，反之不一定】【L2

可能比L1更复杂】19NP-Hard和NP-Complete如果可满足性问题可约化为一个问题L，则L是NP-Hard

如果L是NP-Hard

且LNP，则L是NP-CompleteNP-CompleteNP-Hard有的问题，判定问题是NP完全，优化问题是NP难度但非NP完全。20NP-Hard非NP-Complete实例21

如何证明一个问题是NP-难度的证明L是NP-难度，只需证明一个已知的NP-难度问题可约化为L证明L是NP-完全，需首先证明L是NP-难度，在找到一个解决它的多项式时间不确定算法22NP完全问题第一个NP完全问题（Cook定理1971）可满足性问题是NP完全问题六个NP完全问题（Karp1972)3SAT、团集等更多的NP完全问题1979年：300多个1998年：2000多个23最大集团问题(clique)G=(V,E)的最大完全子图称为一个集团(Clique)。最大集团问题是确定G内最大集团的大小。对应的判定问题CDP是，是否存在大小至少为k的集团。10.2NP-难度问题实例24CDP属于NP25定理10.2