第八章NP完全性理论.ppt

《第八章NP完全性理论.ppt》由会员分享，可在线阅读，更多相关《第八章NP完全性理论.ppt（23页珍藏版）》请在三一文库上搜索。

1、2019/3/12,计算机算法设计与分析,1,第八章 NP完全性理论,2019/3/12,计算机算法设计与分析,2,随机存取机RAM的构造,累加器,指令 计数器,程序存储部件,内存储器,r0 r1 r2,只读输入带,只写输出带,2019/3/12,计算机算法设计与分析,3,随机存取机RAM的指令集,2019/3/12,计算机算法设计与分析,4,RAM机的复杂性标准,均匀耗费标准 对数耗费标准,每条RAM指令需要一个单位时间，每个寄存器占用一个单位空间。,RAM指令的执行时间与操作数的长度的对数成比例，一个寄存器可放一个任意大小的整数。,若每个操作数不超过一个机器字，则用均匀耗费标准是合理的，否

2、则适用对数耗费标准。,2019/3/12,计算机算法设计与分析,5,随机存取存储程序机RASP,RASP与RAM的区别在于(1)RASP的程序存储在内存并且可以修改自身；(2)RASP不允许间接寻址，它通过修改指令模拟间接寻址。 RASP的指令集见P-238的表8-6。 RASP更加接近冯诺伊曼体系结构。 无论是采用均匀耗费标准还是对数耗费标准，在相差一个常数因子的意义下，RAM与RASP是等价的。,2019/3/12,计算机算法设计与分析,6,RAM的变形与简化,(1)实随机存取机RRAM； (2)直线式程序； (3)位式计算； (4)位向量计算； (5)判定数； (6)代数计算树ACT；

3、(7)代数判定树。,2019/3/12,计算机算法设计与分析,7,图林机的构造,图林机(Turing Machine)是英国数学家Turing在1936年提出的计算模型，被认为是当今计算机的理论模型。下面是图林机(TM)原型的构造：,输入带,有限 控制器,磁头,输入带被视为右无穷，并被划分为一个个单元用于存放符号(带符号)。,有限控制器由有限个状态构成。,磁头可左右移动，读写带符号。,2019/3/12,计算机算法设计与分析,8,TM的数学描述,Q是有限状态的集合； T是有限个带符号的集合； I T，是输入符号的集合； ：QTQTL, R为转移函数； b是唯一的空白符，bT I； q0和qf分

4、别为初始状态和终止状态。,M = (Q, T, I, , b, q0, qf ) 其中：,2019/3/12,计算机算法设计与分析,9,图林机的变形,多道图林机(输入带上有多个道)。 双向图林机 (输入带被视为左右均是无穷的)。 多带图林机(具有多条输入带)。 多头图林机 (具有多个磁头)。 多维图林机(输入带是多维的)。 不确定的图林机(有限控制器是不确定的)。,不确定的图林机类似于不确定的自动机，即 ：QT(QTL, R),将图林机是原型称为确定的，记为DTM；而将不确定的图林机记为NDTM，,已经证明各类变形图林机在可计算的能力上等价于原型图林机。但是在复杂性是有区别的。,2019/3/

5、12,计算机算法设计与分析,10,通用图林机,不失一般性，任何图林机的T = 0, 1； ：QTQTL, R的每个动作由五个部分构成(五字诀)，含有有限个五字诀。 于是，任一图林机都可写成一个二进制编码。 所以任一图林机可用一个三带图林机来模拟。 这个三带图林机就被称为通用图林机。,输入带,编码带,工作带,有限 控制器,code1#code2#coden,qi,通用图林机将某个图林机Mi的编码存储在编码带上；工作带上初始时为初始状态q0；然后依据状态及现行扫描的符号选择并执行编码。,2019/3/12,计算机算法设计与分析,11,用RAM模拟TM,定理8-3：设算法A，对于任何长度为n的输入，

6、在图林机TM下的时间复杂性为T(n)，则A在RAM下的时间复杂性为O(T2(n)。 证明：每个寄存器放输入带一个单元的内容，这样RAM就可以模拟TM的工作。 均匀耗费标准下，模拟TM一个动作，RAM需常数时间。A在RAM下时间复杂性为O(T(n)。 对数耗费标准下，RAM模拟TM的时间复杂性为O(T(n)logT(n) =O(T2(n)。 。,2019/3/12,计算机算法设计与分析,12,用TM模拟RAM,定理8-4：设算法A，对于任何长度为n的输入，按对数耗费标准在RAM下的时间复杂性为T(n)，则A在TM下的时间复杂性为O(T2(n)。 证明：用一个五带TM模拟RAM的工作，,其中： 带

7、1用的形式存放寄存器； 带2存放累加器内容；带3作为暂存工作带； 带4和带5作为输入带和输出带； 用TM的状态对应RAM的一步程序。,TM模拟RAM除乘/除法外的指令的时间为常数，查找寄存器的时间为n，整个时间为O(T2(n)。 对RAM的乘除法，TM用加减法模拟的耗费不会超过乘除法耗费的平方。,2019/3/12,计算机算法设计与分析,13,TM模型与RAM模型的关系,定理8-5：在对数耗费标准下，对于同一个算法，采用RAM模型和TM模型的时间复杂性是多项式相关的。对空间复杂性亦如此。 注意在均匀耗费标准下这个关系不成立。TM模拟RAM的时间复杂性可能是指数的关系。 因为TM模型比较原始，所

8、以在大多数情况下采用RAM模型。 若算法在RAM模型下的复杂性为多项式，则也就认为其在TM模型下的复杂性为多项式。,2019/3/12,计算机算法设计与分析,14,可计算性问题的层次,若某问题存在求解的算法，则称其为可计算的；若不存在算法但是存在求解的过程，则称其为半可计算的；若连过程也不存在，则称其为完全不可计算的。,完全不可计算,半可计算,可计算,可计算的问题的集合称为递归集；半可计算的称为递归可枚举集；完全不可计算的称为非递归可枚举集。,可计算的问题的计算复杂性是不是都相同呢？,2019/3/12,计算机算法设计与分析,15,求解与验证,人们通常认为，求解一个问题要比验证一个问题困难些。

9、 但是也并非完全如此。例如TSP问题。要验证一条周游路线是否最小和求一条最小周游路线实际上是一样的难。 希望能按计算的难度将问题分为两类： P类问题：多项式时间计算的问题。 NP类问题：非多项式时间计算的问题 。,2019/3/12,计算机算法设计与分析,16,确定的图林机与不确定图林机,NDTM是一种并行的工作方式，它可以用交叉串行的确定方式来模拟。因此任何NDTM都可以用DTM来模拟实现，但其复杂性却不相同。 对于一台复杂性为T(n)的NDTM，可用一台复杂性为O(CT(n)的DTM来模拟，这里C为常数。 实际上可以将NDTM的运行方式看作并行的，而DTM是串行的。并行运行可用串行来模拟，

10、但并行的效率要高于串行的效率。 而现行计算机的运行方式本质是确定的。,2019/3/12,计算机算法设计与分析,17,P类与NP类语言/问题,P = L | L在多项式时间被DTM接受 NP = L | L在多项式时间被NDTM接受,这里也可用RAM等其它的机器模型来定义。但它们都是等价的。,若QNP，则可以用一个DTM来模拟接受Q的NDTM，所需要时间复杂性为O(CT(n)。,这使人们认为NP类问题要比P类问题更难。,真的如此吗？,显然，因为DTMNDTM，所以PNP。 是否有PNP？,即是否有QNP，且QP？,这是个尚未解决的问题。,2019/3/12,计算机算法设计与分析,18,问题的变

11、换及时间等价性,若问题A的求解能够变换成问题B的求解且变换的时间为O(n)，则称A是(n)时间变换为B，简记为A(n)B，其中n为问题A的规模。 若A(n)B，当(n)为多项式时，称A可多项式归结为问题B，记为AB 。 一般来说，可变换性不是对称的。 若A(n)B且B(n)A，则称A和B是(n)时间等价的。特别当(n)为线性时，称A和B等价。这时A和B具有相同的时间复杂性。,2019/3/12,计算机算法设计与分析,19,计算复杂性的归约,若A(n)B，设A和B的计算时间分别为TA(n)和TB(n)，则,TA(n) = (n) + TB(n),命题1 (计算时间下界归约) ：若TA(n)为A的

12、计算时间下界，则B的计算时间TB(n)的下界为：,(TB(n) = TA(n) O(n),命题1 (计算时间上界归约) ：若TB(n)为B的计算时间上界，则A的计算时间TA(n)的上界为：,O(TA(n) = TB(n) + O(n),2019/3/12,计算机算法设计与分析,20,多项式归结与NP困难,多项式归结显然有如下两个性质： (1) AB且BP，则AP。 (2) 若AB且BC，则AC。 定义：对于问题Q，如果任意问题QiNP，都有QiQ，则称问题Q是NP困难的。 所谓NP困难的问题，是指该问题不会比NP中的任何问题容易，至少是同样难或更难。,2019/3/12,计算机算法设计与分析,

13、21,NP完全性,定义：对于问题Q，若满足QNP且Q是NP困难的，则称Q是NP完全的。 所有NP完全的问题记为NPC。 定理：设QNPC，P=NP当且仅当QP。 如果PNP，则P，NP与NPC或许如下图所示：,NP,P,NPC,2019/3/12,计算机算法设计与分析,22,第一个NP完全的问题,Cook在1971年证明了第一个NP完全的问题。 Cook定理：布尔表达式的可满足性SAT是NP完全的。,所谓可满足性SAT是这样的问题：给定k个布尔变量x1, xk的m个布尔表达式A1, , Am，若存在对各个布尔变量xi的0, 1赋值，使得每个布尔表达式Ai都为真，则称布尔表达式A1, , Am是

14、可满足的。,Cook定理的证明由两个部分构成，第一部分是SATNP，这基本是显然的。第二部分是任意LNP，可在多项式时间内转换为SAT问题。这是一个构造证明，即将接受L的NDTM的瞬象序列转换为一个SAT问题。,自从Cook证明了第一个NP完全的问题后，迄今为止，已经发现了至少有300多个NP完全的问题，但尚未证明其中任何一个是属于P的。,这一事实，增强了人们对PNP的猜测。但遗憾的是，这个猜测迄今仍然还只是个猜测。,2019/3/12,计算机算法设计与分析,23,若干NP完全问题,合取范式的可满足性问题CNF-SAT 三元合取范式的可满足性3-SAT 团问题CLIQUE 顶点覆盖问题VERTEX-COVER 子集和问题SUBST-SUM 哈密顿回路问题HAM-CYCLE 旅行售货员问题TSP,