算法设计与分析 NP完全性理论

第8章NP完全性理论8.1计算机模型8.2P类与NP类问题8.3NP完全问题本章主要知识点：NP完全性理论在计算机算法理论中，最深刻的问题之一是“从计算的观点看，要解决的问题的内在复杂性如何？”它是“易”计算还是“难”计算的？问题的计算复杂性可以通过解决该问题所需要的计算量的多少来衡量。人们通常将可在多项式时间内解决的问题看作是“易”解决的问题，而将需要指数函数时间解决的问题看作是“难”问题。多项式时间和指数函数时间是针对问题的规模而言，即解决问题所需的时间是问题规模的多项式还是指数函数。P(Polynomial,多项式)问题是可以在多项式时间内被确定机(通常意义的计算机)解决的问题。NP(Non-DeterministicPolynomial,非确定多项式)问题,是指可以在多项式时间内被非确定机解决的问题。NP完全性理论NP完全(NPComplete,NPC)问题是指这样一类NP问题,所有的NP问题都可以用多项式时间划归到它们中的一个。所以显然NP完全的问题具有如下性质:它可以在多项式时间内求解，当且仅当所有的其他的NP－完全问题也可以在多项式时间内求解。这样一来,只要我们找到一个NPC问题的多项式解,所有的NP问题都可以多项式时间内划归成这个NPC问题,再用多项式时间解决,这样NP就等于P了.8.1计算机模型•8.1.1随机存取机RAM•8.1.2随机存取存储程序机RASP•8.1.3RAM模型的变形与简化•8.1.4图灵机8.1.1随机存取机RAM1.RAM的结构8.1.1随机存取机RAM只读输入带由一系列方格组成，每格可存放一个整数（可为负）。只读输入带读取一个数后，读写头向右移动一格。只写输出带的每个方格初始为空。每执行一条指令就在读写头下的方格中打印一个整数，然后读写头右移一格。输出的符号一经写出，不能修改。内存储器由一系列寄存器r0，r1,…ri…组成。每个寄存器可以存放一个任意大的整数。内存中寄存器的个数不受限制。r0是是累加器，所有的计算都在r0中进行。8.1.1随机存取机RAMRAM程序是一个带有标号的指令序列。程序不能修改其自身。RAM中设有算术运算指令、输入输出指令、存取数指令及转移指令。每条RAM指令由操作码和操作数组成。操作数：(1)=i，(直接数型)操作数是整数i本身；(2)i，（直接地址型）操作数是寄存器ri的内容；(3)*i，（间接地址型）若ri的内容为j，则操作数为rj的内容。操作码：ADDSUBMULTDIV；READWRITE；LOADSTORE；JUMPJGTZJZERO；HALT2.RAM程序8.1.1随机存取机RAM总的来讲，一个RAM程序定义了从输入带到输出带的一个映射。可以对这种映射关系作2种不同的解释。解释一：把RAM程序看成是计算一个函数若一个RAM程序P总是从输入带前n个方格中读入n个整数x1，x2，…，xn，并且在输出带的第一个方格上输出一个整数y后停机，那么就说程序P计算了函数f(x1，x2，…，xn)=y解释二：把RAM程序当作一个语言接受器。将字符串S=a1a2…an放在输入带上。在输入带的第一个方格中放入符号a1，第二个方格中放入符号a2，…，第n个方格中放入符号an。然后在第n+1个方格中放入0，作为输入串的结束标志符。如果一个RAM程序P读了字符串S及结束标志符0后，在输出带的第一格输出一个1并停机，就说程序P接受字符串S。8.1.1随机存取机RAM3.RAM程序的耗费标准标准一：均匀耗费标准在均匀耗费标准下，每条RAM指令需要一个单位时间；每个寄存器占用一个单位空间。以后除特别注明，RAM程序的复杂性将按照均匀耗费标准衡量。在RAM计算模型下，要精确地计算一个算法的时间和空间复杂性，就必须知道执行每条指令所需的时间以及每个寄存器实际所占的空间。下面介绍两个耗费标准：标准二：对数耗费标准对数耗费标准是基于这样的假定，即执行一条指令的耗费与以二进制表示的指令的操作数长度成比例。在RAM计算模型下，假定一个寄存器可存放一个任意大小的整数。因此若设l(i)是整数i所占的二进制位数，则001||log)(iiiil8.1.1随机存取机RAM其中，log是以2为底的对数。8.1.2随机存取存储程序机RASP1.RASP的结构（3）每条RASP指令占据2个连续的寄存器。第一个寄存器存放操作码的编码，第二个寄存器存放地址。RASP指令用整数进行编码。RASP的整体结构类似于RAM，不同之处在于：（1）RASP的程序是存储在寄存器中的。因此，允许程序修改其自身。（2）RASP指令集中，由于不需要间接寻址，因而不允许使用间接地址。2.RASP程序的复杂性8.1.2随机存取存储程序机RASPRASP指令编码：LOADi，LOAD=i,STOREi,ADDi,ADD=i,SUBi,SUB=i,MULTi,MULT=i,DIVi，DIV=i,READi,WRITEi,WRITE=i,JUMPi,JGTZi,JZEROi，HALTi,在均匀耗费标准下，RASP的计算复杂性与RAM相同。在对数耗费标准下，RASP不仅需要支付计算操作数的耗费，而且要支付存取指令本身的耗费。定理不管是在均匀耗费标准下，还是在对数耗费标准下，RAM程序和RASP程序的复杂性只差一个常数因子。即，在一个计算模型下T(n)时间内完成的输入-输出映射可在另一个计算模型下模拟，并在kT(n)时间内完成。其中k是一个常数因子。空间复杂性的情况也是类似的。8.1.3RAM模型的变形与简化RAM和RASP是在现实计算机原型上抽象出来的计算模型。在许多场合下直接使用这两种计算模型太复杂。因此，在不影响复杂性阶的情况下，人们从时间需要出发提出了一些简化的计算模型，如实随机存取机（RRAM），直线式程序（SLP），位计算（BC），位向量运算（BVO），判定树（DT），代数计算树（ACT）和代数判定树（ADT）等。8.1.3RAM模型的变形与简化1.实随机存取机RRAM在RRAM模型下，一个存储单元可以存放一个实数。下列的各运算为基本运算且每个运算只耗费单位时间。(1)算术运算+，－，×，／。(2)2个实数间的比较(，≤，=，≠，≥，)。(3)间接寻址(整数地址)。(4)常见函数的计算，如三角函数，指数函数，对数函数等。优点：能够方便处理实数；适合于用FORTRAN，PASCAL等高级语言写的算法。8.1.3RAM模型的变形与简化2.直线式程序对于许多问题，所设计的RAM程序中的转移指令仅用于重复一组指令，而且重复的次数与问题的输入规模n成比例。在这种情况下，可以用重复地写出相同指令组的方法来消除程序中的循环。由此，对每一个固定的n得到一个无循环的直线式程序。对于许多问题，其相应的RAM程序中转移指令的时间耗费只是整个程序时间耗费的一小部分。因此，直线化程序忽略这部分时间耗费不会影响复杂性结论。类似地，输入语句只是一个程序耗费的常数部分，可以假设在程序开始已将输入放入存储器中，从而不需要输入语句。因此，可以将RAM中READ，JUMPJGTZ和JZERO指令去掉。经过对RAM模型的简化，得到直线式程序的指令系统如下：x←y+zx←y-zx←y*zx←y/zx←i其中x，y和z是符号地址(或变量)，而i是常数。每条指令耗费一个单位时间。由于直线式程序结束就意味着停机，因此，不需要HALT指令。对于WRITE指令，只要指定某些符号地址是输出，而不需要WRITE指令。这样，直线式程序中只剩下LOAD和STORE指令和算术指令。进一步，还可以将LOAD和STORE也组合到算术运算中去。8.1.3RAM模型的变形与简化8.1.3RAM模型的变形与简化3.位式计算直线式程序计算模型显然是基于均匀耗费标准的。在对数耗费标准下，使用另一个RAM的简化计算模型，称之为位式计算(BitwiseComputation)模型。除了下列2点外，该计算模型与直线式程序计算模型基本相同：(1)假设所有变量取值0或1，即为位变量。(2)所用的运算是逻辑运算而不是算术运算。用∧代表与，∨代表或，代表异或，代表非。在位式计算模型下，每个逻辑运算指令耗费一个单位时间。8.1.4图灵机1.多带图灵机一台多带图灵机由一个有限状态控制器和k条读写带组成。这些读写带的右端无限，每条带从左到右划分为方格，每个方格可以存放一个带符号。带符号的总数是有限的。每条带上都有一个由有限状态控制器操纵的读写头，它可以对这k条带进行读写操作。有限状态控制器在某一时刻处于某种状态，且状态的总数是有限的。图灵机是一个结构简单且计算能力很强的计算模型。8.1.4图灵机多带图灵机的示意图如下：8.1.4图灵机根据有限状态控制器的当前状态及每个读写头读到的带符号，图灵机的一个计算步可实现下面3个操作之一或全部。(1)改变有限状态控制器中的状态。(2)清除当前读写头下的方格中原有带符号并写上新的带符号。(3)独立地将任何一个或所有读写头，向左移动一个方格(L)或向右移动一个方格(R)或停在当前单元不动(S)。k带图灵机可形式化地描述为一个7元组(Q，T，I，δ，b，q0，qf)，其中:(1)Q是有限个状态的集合。(2)T是有限个带符号的集合。(3)I是输入符号的集合，IT。(4)b是惟一的空白符，b∈T-I。(5)q0是初始状态。(6)qf是终止(或接受)状态。(7)δ是移动函数。它是从QTk的某一子集映射到Q(T{L，R，S})k的函数。8.1.4图灵机8.1.4图灵机图灵机M的时间复杂性T(n)是它处理所有长度为n的输入所需的最大计算步数。如果对某个长度为n的输入，图灵机不停机，T(n)对这个n值无定义。图灵机的空间复杂性S(n)是它处理所有长度为n的输入时，在k条带上所使用过的方格数的总和。如果某个读写头无限地向右移动而不停机，S(n)也无定义。与RAM模型类似，图灵机既可作为语言接受器，也可作为计算函数的装置。