第八章NP完全性理论

2020/2/15计算机算法设计与分析1第八章NP完全性理论2020/2/15计算机算法设计与分析2随机存取机RAM的构造累加器指令计数器程序存储部件内存储器r0r1r2…只读输入带……只写输出带2020/2/15计算机算法设计与分析3随机存取机RAM的指令集操作码操作数指令含义⑴LOAD=i/i/*i取操作数入累加器⑵STOREi/*i将累加器中数存入内存⑶ADD=i/i/*i加法运算⑷SUB=i/i/*i减法运算⑸MULT=i/i/*i乘法运算⑹DIV=i/i/*i除法运算⑺READi/*i读入⑻WRITE=i/i/*i输出⑼JUMP标号无条件转移到标号语句⑽JGTZ标号正转移到标号语句⑾JZERO标号零转移到标号语句⑿HALT停机2020/2/15计算机算法设计与分析4RAM机的复杂性标准均匀耗费标准对数耗费标准每条RAM指令需要一个单位时间，每个寄存器占用一个单位空间。RAM指令的执行时间与操作数的长度的对数成比例，一个寄存器可放一个任意大小的整数。若每个操作数不超过一个机器字，则用均匀耗费标准是合理的，否则适用对数耗费标准。2020/2/15计算机算法设计与分析5随机存取存储程序机RASPRASP与RAM的区别在于(1)RASP的程序存储在内存并且可以修改自身；(2)RASP不允许间接寻址，它通过修改指令模拟间接寻址。RASP的指令集见P-238的表8-6。RASP更加接近冯·诺伊曼体系结构。无论是采用均匀耗费标准还是对数耗费标准，在相差一个常数因子的意义下，RAM与RASP是等价的。2020/2/15计算机算法设计与分析6RAM的变形与简化(1)实随机存取机RRAM；(2)直线式程序；(3)位式计算；(4)位向量计算；(5)判定数；(6)代数计算树ACT；(7)代数判定树。2020/2/15计算机算法设计与分析7图林机的构造图林机(TuringMachine)是英国数学家Turing在1936年提出的计算模型，被认为是当今计算机的理论模型。下面是图林机(TM)原型的构造：……输入带有限控制器磁头输入带被视为右无穷，并被划分为一个个单元用于存放符号(带符号)。有限控制器由有限个状态构成。磁头可左右移动，读写带符号。2020/2/15计算机算法设计与分析8TM的数学描述Q是有限状态的集合；T是有限个带符号的集合；IT，是输入符号的集合；δ：Q×T→Q×T×{L,R}为转移函数；b是唯一的空白符，b∈T–I；q0和qf分别为初始状态和终止状态。M=(Q,T,I,δ,b,q0,qf)其中：2020/2/15计算机算法设计与分析9图林机的变形多道图林机(输入带上有多个道)。双向图林机(输入带被视为左右均是无穷的)。多带图林机(具有多条输入带)。多头图林机(具有多个磁头)。多维图林机(输入带是多维的)。不确定的图林机(有限控制器是不确定的)。不确定的图林机类似于不确定的自动机，即δ：Q×T→ρ(Q×T×{L,R})将图林机是原型称为确定的，记为DTM；而将不确定的图林机记为NDTM，已经证明各类变形图林机在可计算的能力上等价于原型图林机。但是在复杂性是有区别的。2020/2/15计算机算法设计与分析10通用图林机不失一般性，任何图林机的T={0,1}；δ：Q×T→Q×T×{L,R}的每个动作由五个部分构成(五字诀)，δ含有有限个五字诀。于是，任一图林机都可写成一个二进制编码。所以任一图林机可用一个三带图林机来模拟。这个三带图林机就被称为通用图林机。输入带编码带工作带有限控制器code1#code2#…#codenqi通用图林机将某个图林机Mi的编码存储在编码带上；工作带上初始时为初始状态q0；然后依据状态及现行扫描的符号选择并执行编码。2020/2/15计算机算法设计与分析11用RAM模拟TM定理8-3：设算法A，对于任何长度为n的输入，在图林机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))。。2020/2/15计算机算法设计与分析12用TM模拟RAM定理8-4：设算法A，对于任何长度为n的输入，按对数耗费标准在RAM下的时间复杂性为T(n)，则A在TM下的时间复杂性为O(T2(n))。证明：用一个五带TM模拟RAM的工作，其中：带1用地址,内容的形式存放寄存器；带2存放累加器内容；带3作为暂存工作带；带4和带5作为输入带和输出带；用TM的状态对应RAM的一步程序。TM模拟RAM除乘/除法外的指令的时间为常数，查找寄存器的时间为n，整个时间为O(T2(n))。对RAM的乘除法，TM用加减法模拟的耗费不会超过乘除法耗费的平方。2020/2/15计算机算法设计与分析13TM模型与RAM模型的关系定理8-5：在对数耗费标准下，对于同一个算法，采用RAM模型和TM模型的时间复杂性是多项式相关的。对空间复杂性亦如此。注意在均匀耗费标准下这个关系不成立。TM模拟RAM的时间复杂性可能是指数的关系。因为TM模型比较原始，所以在大多数情况下采用RAM模型。若算法在RAM模型下的复杂性为多项式，则也就认为其在TM模型下的复杂性为多项式。2020/2/15计算机算法设计与分析14可计算性问题的层次若某问题存在求解的算法，则称其为可计算的；若不存在算法但是存在求解的过程，则称其为半可计算的；若连过程也不存在，则称其为完全不可计算的。完全不可计算半可计算可计算可计算的问题的集合称为递归集；半可计算的称为递归可枚举集；完全不可计算的称为非递归可枚举集。可计算的问题的计算复杂性是不是都相同呢？2020/2/15计算机算法设计与分析15求解与验证人们通常认为，求解一个问题要比验证一个问题困难些。但是也并非完全如此。例如TSP问题。要验证一条周游路线是否最小和求一条最小周游路线实际上是一样的难。希望能按计算的难度将问题分为两类：P类问题：多项式时间计算的问题。NP类问题：非多项式时间计算的问题。2020/2/15计算机算法设计与分析16确定的图林机与不确定图林机NDTM是一种并行的工作方式，它可以用交叉串行的确定方式来模拟。因此任何NDTM都可以用DTM来模拟实现，但其复杂性却不相同。对于一台复杂性为T(n)的NDTM，可用一台复杂性为O(CT(n))的DTM来模拟，这里C为常数。实际上可以将NDTM的运行方式看作并行的，而DTM是串行的。并行运行可用串行来模拟，但并行的效率要高于串行的效率。而现行计算机的运行方式本质是确定的。2020/2/15计算机算法设计与分析17P类与NP类语言/问题P={L|L在多项式时间被DTM接受}NP={L|L在多项式时间被NDTM接受}这里也可用RAM等其它的机器模型来定义。但它们都是等价的。若Q∈NP，则可以用一个DTM来模拟接受Q的NDTM，所需要时间复杂性为O(CT(n))。这使人们认为NP类问题要比P类问题更难。真的如此吗？显然，因为DTMNDTM，所以PNP。是否有P≠NP？即是否有QNP，且QP？这是个尚未解决的问题。2020/2/15计算机算法设计与分析18问题的变换及时间等价性若问题A的求解能够变换成问题B的求解且变换的时间为O(τ(n))，则称A是τ(n)时间变换为B，简记为A∝τ(n)B，其中n为问题A的规模。若A∝τ(n)B，当τ(n)为多项式时，称A可多项式归结为问题B，记为A∝B。一般来说，可变换性不是对称的。若A∝τ(n)B且B∝τ(n)A，则称A和B是τ(n)时间等价的。特别当τ(n)为线性时，称A和B等价。这时A和B具有相同的时间复杂性。2020/2/15计算机算法设计与分析19计算复杂性的归约若A∝τ(n)B，设A和B的计算时间分别为TA(n)和TB(n)，则TA(n)=τ(n)+TB(n)命题1(计算时间下界归约)：若TA(n)为A的计算时间下界，则B的计算时间TB(n)的下界为：Ω(TB(n))=TA(n)–O(τ(n))命题1(计算时间上界归约)：若TB(n)为B的计算时间上界，则A的计算时间TA(n)的上界为：O(TA(n))=TB(n)+O(τ(n))2020/2/15计算机算法设计与分析20多项式归结与NP困难多项式归结显然有如下两个性质：(1)A∝B且B∈P，则A∈P。(2)若A∝B且B∝C，则A∝C。定义：对于问题Q，如果任意问题Qi∈NP，都有Qi∝Q，则称问题Q是NP困难的。所谓NP困难的问题，是指该问题不会比NP中的任何问题容易，至少是同样难或更难。2020/2/15计算机算法设计与分析21NP完全性定义：对于问题Q，若满足Q∈NP且Q是NP困难的，则称Q是NP完全的。所有NP完全的问题记为NPC。定理：设Q∈NPC，P=NP当且仅当Q∈P。如果P≠NP，则P，NP与NPC或许如下图所示：NPPNPC2020/2/15计算机算法设计与分析22第一个NP完全的问题Cook在1971年证明了第一个NP完全的问题。Cook定理：布尔表达式的可满足性SAT是NP完全的。所谓可满足性SAT是这样的问题：给定k个布尔变量x1,…xk的m个布尔表达式A1,…,Am，若存在对各个布尔变量xi的0,1赋值，使得每个布尔表达式Ai都为真，则称布尔表达式A1,…,Am是可满足的。Cook定理的证明由两个部分构成，第一部分是SAT∈NP，这基本是显然的。第二部分是任意L∈NP，可在多项式时间内转换为SAT问题。这是一个构造证明，即将接受L的NDTM的瞬象序列转换为一个SAT问题。自从Cook证明了第一个NP完全的问题后，迄今为止，已经发现了至少有300多个NP完全的问题，但尚未证明其中任何一个是属于P的。这一事实，增强了人们对P≠NP的猜测。但遗憾的是，这个猜测迄今仍然还只是个猜测。2020/2/15计算机算法设计与分析23若干NP完全问题合取范式的可满足性问题CNF-SAT三元合取范式的可满足性3-SAT团问题CLIQUE顶点覆盖问题VERTEX-COVER子集和问题SUBST-SUM哈密顿回路问题HAM-CYCLE旅行售货员问题TSP