第八章NP完全性理论

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

1、第八章NP完全性理论*1计算机算法设计与分析随机存取机RAM的构造累加器指令 计数器程序存储部件内存储器r0 r1 r2 只读输入带只写输出带Date2计算机算法设计与分析随机存取机RAM的指令集操作码操作数指令含义 LOAD=i / i / *i取操作数入累加器 STOREi / *i将累加器中数存入内存 ADD=i / i / *i加法运算 SUB=i / i / *i减法运算 MULT=i / i / *i乘法运算 DIV=i / i / *i除法运算 READ i / *i读入 WRITE=i / i / *i输出JUMP标号无条件转移到标号语句 JGTZ标号正转移到标号语句 JZER

2、O标号零转移到标号语句 HALT停机Date3计算机算法设计与分析RAM机的复杂性标准n均匀耗费标准n对数耗费标准每条RAM指令需要一个单位时间，每个寄存器 占用一个单位空间。RAM指令的执行时间与操作数的长度的对数成 比例，一个寄存器可放一个任意大小的整数。n若每个操作数不超过一个机器字，则用均匀耗 费标准是合理的，否则适用对数耗费标准。Date4计算机算法设计与分析随机存取存储程序机RASPnRASP与RAM的区别在于(1)RASP的程序存储 在内存并且可以修改自身；(2)RASP不允许间 接寻址，它通过修改指令模拟间接寻址。nRASP的指令集见P-238的表8-6。nRASP更加接近冯诺

3、伊曼体系结构。n无论是采用均匀耗费标准还是对数耗费标准， 在相差一个常数因子的意义下，RAM与RASP 是等价的。Date5计算机算法设计与分析RAM的变形与简化n(1)实随机存取机RRAM；n(2)直线式程序；n(3)位式计算；n(4)位向量计算；n(5)判定数；n(6)代数计算树ACT；n(7)代数判定树。Date6计算机算法设计与分析图林机的构造n图林机(Turing Machine)是英国数学家Turing在 1936年提出的计算模型，被认为是当今计算机 的理论模型。下面是图林机(TM)原型的构造：输入带有限 控制器磁头输入带被视为右无穷，并被划分为一个个 单元用于存放符号(带符号)。

4、 有限控制器由有限个状态构成。 磁头可左右移动，读写带符号。Date7计算机算法设计与分析TM的数学描述nQ是有限状态的集合；nT是有限个带符号的集合；nI T，是输入符号的集合；n：QTQTL, R为转移函数；nb是唯一的空白符，bT I；nq0和qf分别为初始状态和终止状态。M = (Q, T, I, , b, q0, qf ) 其中：Date8计算机算法设计与分析图林机的变形n多道图林机(输入带上有多个道)。n双向图林机 (输入带被视为左右均是无穷的)。n多带图林机(具有多条输入带)。n多头图林机 (具有多个磁头)。n多维图林机(输入带是多维的)。n不确定的图林机(有限控制器是不确定的)

5、。 不确定的图林机类似于不确定的自动机，即 ：QT(QTL, R)将图林机是原型称为确定的，记为DTM；而 将不确定的图林机记为NDTM，n已经证明各类变形图林机在可计算的能力上等 价于原型图林机。但是在复杂性是有区别的。Date9计算机算法设计与分析通用图林机n不失一般性，任何图林机的T = 0, 1；n：QTQTL, R的每个动作由五个部分 构成(五字诀)，含有有限个五字诀。n于是，任一图林机都可写成一个二进制编码。n所以任一图林机可用一个三带图林机来模拟。n这个三带图林机就被称为通用图林机。输入带编码带工作带有限 控制器code1#code2#codenqi通用图林机将某个图林机Mi的编

6、码存储在编码 带上；工作带上初始时为初始状态q0；然后依 据状态及现行扫描的符号选择并执行编码。Date10计算机算法设计与分析用RAM模拟TMn定理8-3：设算法A，对于任何长度为n的输入 ，在图林机TM下的时间复杂性为T(n)，则A在 RAM下的时间复杂性为O(T2(n)。n证明：每个寄存器放输入带一个单元的内容， 这样RAM就可以模拟TM的工作。n均匀耗费标准下，模拟TM一个动作，RAM需 常数时间。A在RAM下时间复杂性为O(T(n)。n对数耗费标准下，RAM模拟TM的时间复杂性 为O(T(n)logT(n) =O(T2(n)。 。Date11计算机算法设计与分析用TM模拟RAMn定理

7、8-4：设算法A，对于任何长度为n的输入 ，按对数耗费标准在RAM下的时间复杂性为 T(n)，则A在TM下的时间复杂性为O(T2(n)。n证明：用一个五带TM模拟RAM的工作， 其中：带1用的形式存放寄存器；带2存放累加器内容；带3作为暂存工作带；带4和带5作为输入带和输出带；用TM的状态对应RAM的一步程序。nTM模拟RAM除乘/除法外的指令的时间为常数 ，查找寄存器的时间为n，整个时间为O(T2(n) 。n对RAM的乘除法，TM用加减法模拟的耗费不 会超过乘除法耗费的平方。Date12计算机算法设计与分析TM模型与RAM模型的关系n定理8-5：在对数耗费标准下，对于同一个算法 ，采用RAM

8、模型和TM模型的时间复杂性是多 项式相关的。对空间复杂性亦如此。n注意在均匀耗费标准下这个关系不成立。TM 模拟RAM的时间复杂性可能是指数的关系。n因为TM模型比较原始，所以在大多数情况下 采用RAM模型。n若算法在RAM模型下的复杂性为多项式，则也 就认为其在TM模型下的复杂性为多项式。Date13计算机算法设计与分析可计算性问题的层次n若某问题存在求解的算法，则称其为可计算的 ；若不存在算法但是存在求解的过程，则称其 为半可计算的；若连过程也不存在，则称其为 完全不可计算的。完全不可计算半可计算可计算n可计算的问题的集合称为递归集；半可计算的 称为递归可枚举集；完全不可计算的称为非递 归

9、可枚举集。n可计算的问题的计算复杂性是不是都相同呢？Date14计算机算法设计与分析求解与验证n人们通常认为，求解一个问题要比验证一个问 题困难些。n但是也并非完全如此。例如TSP问题。要验证 一条周游路线是否最小和求一条最小周游路线 实际上是一样的难。n希望能按计算的难度将问题分为两类：nP类问题：多项式时间计算的问题。nNP类问题：非多项式时间计算的问题 。Date15计算机算法设计与分析确定的图林机与不确定图林机nNDTM是一种并行的工作方式，它可以用交叉 串行的确定方式来模拟。因此任何NDTM都可 以用DTM来模拟实现，但其复杂性却不相同。n对于一台复杂性为T(n)的NDTM，可用一台

10、复 杂性为O(CT(n)的DTM来模拟，这里C为常数。n实际上可以将NDTM的运行方式看作并行的， 而DTM是串行的。并行运行可用串行来模拟， 但并行的效率要高于串行的效率。n而现行计算机的运行方式本质是确定的。Date16计算机算法设计与分析P类与NP类语言/问题nP = L | L在多项式时间被DTM接受nNP = L | L在多项式时间被NDTM接受n这里也可用RAM等其它的机器模型来定义。但 它们都是等价的。n若QNP，则可以用一个DTM来模拟接受Q的 NDTM，所需要时间复杂性为O(CT(n)。n这使人们认为NP类问题要比P类问题更难。真的如此吗？n显然，因为DTMNDTM，所以PN

11、P。n是否有PNP？ 即是否有QNP，且QP？这是个尚未解决的问题。Date17计算机算法设计与分析问题的变换及时间等价性n若问题A的求解能够变换成问题B的求解且变 换的时间为O(n)，则称A是(n)时间变换为B ，简记为A(n)B，其中n为问题A的规模。n若A(n)B，当(n)为多项式时，称A可多项式 归结为问题B，记为AB 。n一般来说，可变换性不是对称的。n若A(n)B且B(n)A，则称A和B是(n)时间 等价的。特别当(n)为线性时，称A和B等价。 这时A和B具有相同的时间复杂性。Date18计算机算法设计与分析计算复杂性的归约n若A(n)B，设A和B的计算时间分别为TA(n) 和TB

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

13、不会比NP中 的任何问题容易，至少是同样难或更难。Date20计算机算法设计与分析NP完全性n定义：对于问题Q，若满足QNP且Q是NP困 难的，则称Q是NP完全的。n所有NP完全的问题记为NPC。n定理：设QNPC，P=NP当且仅当QP。n如果PNP，则P，NP与NPC或许如下图所示：NPPNPCDate21计算机算法设计与分析第一个NP完全的问题nCook在1971年证明了第一个NP完全的问题。nCook定理：布尔表达式的可满足性SAT是NP完 全的。 所谓可满足性SAT是这样的问题：给定k个布尔 变量x1, xk的m个布尔表达式A1, , Am，若存 在对各个布尔变量xi的0, 1赋值，使

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