NP完全性理论与近似算法.ppt

1,第9章NP完全性理论与近似算法,2,学习要点理解RAM，RASP和图灵机计算模型理解非确定性图灵机的概念理解P类与NP类语言的概念理解NP完全问题的概念,3,引言,问题的计算复杂性可以通过解决问题所需计算量的多少来度量。易：可在多项式时间(O(nk)内解决的问题难：需要指数函数(O(kn)时间解决的问题,4,9.1计算模型,在进行问题的计算复杂性分析之前，首先必须建立求解问题所用的计算模型，包括定义该计算模型中所用的基本运算。建立计算模型的目的是为了使问题的计算复杂性分析有一个共同的客观尺度。3个基本计算模型：随机存取机RAM(RandomAccessMachine)；随机存取存储程序机RASP(RandomAccessStoredProgramMachine)图灵机(TuringMachine)。,5,9.1.1随机存取机RAM,1、RAM的结构,6,9.1.1随机存取机RAM,2、RAM程序,一个RAM程序定义了从输入带到输出带的一个映射。可以对这种映射关系作2种不同的解释。,解释一：把RAM程序看成是计算一个函数若一个RAM程序P总是从输入带前n个方格中读入n个整数x1，x2，xn，并且在输出带的第一个方格上输出一个整数y后停机，那么就说程序P计算了函数f(x1，x2，xn)=y,解释二：把RAM程序当作一个语言接受器。将字符串S=a1a2an放在输入带上。在输入带的第一个方格中放入符号a1，第二个方格中放入符号a2，第n个方格中放入符号an。然后在第n+1个方格中放入0，作为输入串的结束标志符。如果一个RAM程序P读了字符串S及结束标志符0后，在输出带的第一格输出一个1并停机，就说程序P接受字符串S。,7,9.1.1随机存取机RAM,3、RAM程序的耗费标准,标准一：均匀耗费标准在均匀耗费标准下，每条RAM指令需要一个单位时间；每个寄存器占用一个单位空间。以后除特别注明，RAM程序的复杂性将按照均匀耗费标准衡量。,标准二：对数耗费标准对数耗费标准是基于这样的假定，即执行一条指令的耗费与以二进制表示的指令的操作数长度成比例。在RAM计算模型下，假定一个寄存器可存放一个任意大小的整数。因此若设l(i)是整数i所占的二进制位数，则,8,9.1.2随机存取存储程序机RASP,1、RASP的结构,RASP的整体结构类似于RAM，所不同的是RASP的程序是存储在寄存器中的。每条RASP指令占据2个连续的寄存器。第一个寄存器存放操作码的编码，第二个寄存器存放地址。RASP指令用整数进行编码。,2、RASP程序的复杂性,不管是在均匀耗费标准下，还是在对数耗费标准下，RAM程序和RASP程序的复杂性只差一个常数因子。在一个计算模型下T(n)时间内完成的输入-输出映射可在另一个计算模型下模拟，并在kT(n)时间内完成。其中k是一个常数因子。空间复杂性的情况也是类似的。,9,9.1.3图灵机,图灵最大的贡献就是把算法这样一个基本的、深刻的概念用他的图灵机模型讲清楚了。正是因为图灵奠定的理论基础，人们才有可能发明20世纪以来甚至是人类有史以来最伟大的发明：计算机。因此人们称图灵为：计算机理论之父。图灵在二战期间他曾经为英国政府效力成功破译了德国的密码，因而为英国做出了突出贡献。为了纪念这个伟大的学者，计算机界设立了最高荣誉奖：ACM图灵奖。,10,9.1.3图灵机,11,9.1.3图灵机,根据有限状态控制器的当前状态及每个读写头读到的带符号，图灵机的一个计算步可实现下面3个操作之一或全部。(1)改变有限状态控制器中的状态。(2)清除当前读写头下的方格中原有带符号并写上新的带符号。(3)独立地将任何一个或所有读写头，向左移动一个方格(L)或向右移动一个方格(R)或停在当前单元不动(S)。,12,9.1.3图灵机,k带图灵机可形式化地描述为一个7元组(Q，T，I，b，q0，qf)，其中:(1)Q是有限个状态的集合。(2)T是有限个带符号的集合。(3)I是输入符号的集合，IT。(4)b是唯一的空白符，bT-I。(5)q0是初始状态。(6)qf是终止(或接受)状态。(7)是移动函数。它是从QTk的某一子集映射到Q(TL，R，S)k的函数。,13,9.1.3图灵机,图灵机M的时间复杂性T(n)是它处理所有长度为n的输入所需的最大计算步数。如果对某个长度为n的输入，图灵机不停机，T(n)对这个n值无定义。,图灵机的空间复杂性S(n)是它处理所有长度为n的输入时，在k条带上所使用过的方格数的总和。如果某个读写头无限地向右移动而不停机，S(n)也无定义。,与RAM模型类似，图灵机既可作为语言接受器，也可作为计算函数的装置。,14,9.1.3图灵机,例1、设计一台可以计算“x+1”的图灵机。根据图灵机的原理，利用二进制来设计一个专门计算“x+1”的图灵机，要求计算完成时读写头要回归原位。于是我们设计的图灵机为：状态集合K:start,add,carry,noncarry,overflow,return,halt字母表：0,1,*初始状态s：start停机状态H：halt规则集合：（见下页表）,15,9.1.3图灵机,16,9.1.3图灵机,该图灵机是如何具体进行计算动作的：假定x=5，则图灵机的初始状态如图2.2所示，箭头表示读写头当前的位置。,17,9.1.3图灵机,从规则表2.1可知，当前状态为“add”,当前符号为“1”时，读写头的响应为：改写当前符号为“0”，并向左移动一格，内部状态改变为“carry”表示有进位，如图2.4所示：,18,9.1.3图灵机,接下来从规则表2.1可知，读写头应改写当前符号为“1”，并向左移动一格，进入“noncarry”状态，表明没有进位，如图2.5所示,19,9.1.3图灵机,此时，从规则表2.1知道：读写头不改写当前符号，只是继续向左移动一格，指向“*”,如图2.6所示：,20,9.1.3图灵机,这时实际已经完成“516”的计算，因为我们要求读写头要回归原位，按规则接下来就是将读写头一路右移直到原位“*”,内部状态保持为“return”状态，如图2.7所示：,21,9.1.3图灵机,从读写头状态可知，图灵机这时还处在运行状态，从规则表中可知，当读写头状态为“return”且当前符号为“*”时，则应进入“halt”状态，由于“halt”状态是该图灵机的停机状态，所以，图灵机停止运行，圆满地完成了计算要求，如图2.8所示：,22,9.1.3图灵机,图灵停机问题存在不存在一个程序比如说P，能够判断出任意一个程序X是否会在输入Y的情况下陷入死循环？不妨设P(X,Y)表示P判断程序是X，数据是Y的结果。如果存在死循环，那么P(X,Y)就输出一个yes。如果不存在死循环，那么P(X,Y)就输出一个no。这样的P(X,Y)存在么？这就是停机问题。所谓的某个程序X在输入Y上停机就是说X不存在着死循环，反过来如果不停机就是存在着死循环，因而这里停机和死循环是一回事儿。那么，这种判断停机问题的程序P存在么？答案是不存在的。,23,9.2P类与NP类问题,一般地说，将可由多项式时间算法求解的问题看作是易处理的问题，而将需要超多项式时间才能求解的问题看作是难处理的问题。有许多问题，从表面上看似乎并不比排序或图的搜索等问题更困难，然而至今人们还没有找到解决这些问题的多项式时间算法，也没有人能够证明这些问题需要超多项式时间下界。在图灵机计算模型下，这类问题的计算复杂性至今未知。为了研究这类问题的计算复杂性，人们提出了另一个能力更强的计算模型，即非确定性图灵机计算模型，简记为NDTM(NondeterministicTuringMachine)。在非确定性图灵机计算模型下，许多问题可以在多项式时间内求解。,24,9.2.1非确定性图灵机,非确定性图灵机（NDTM）：一个k带的非确定性图灵机M是一个7元组：(Q，T，I，b，q0，qf)。与确定性图灵机不同的是非确定性图灵机允许移动函数具有不确定性，即对于QTk中的每一个值(q;x1,x2,xk)，当它属于的定义域时，Q(TL，R，S)k中有唯一的一个子集(q;x1,x2,xk)与之对应。可以在(q;x1,x2,xk)中随意选定一个值作为它的函数值。,在图灵机计算模型中，移动函数是单值的，即对于QTk中的每一个值，当它属于的定义域时，Q(TL，R，S)k中只有唯一的值与之对应，称这种图灵机为确定性图灵机，简记为DTM(DeterministicTuringMachine)。,25,9.2.2P类与NP类语言,P类和NP类语言的定义：P=L|L是一个能在多项式时间内被一台DTM所接受的语言NP=L|L是一个能在多项式时间内被一台NDTM所接受的语言,由于一台确定性图灵机可看作是非确定性图灵机的特例，所以可在多项式时间内被确定性图灵机接受的语言也可在多项式时间内被非确定性图灵机接受。故PNP。,26,9.2.2P类与NP类语言,P就是Polynomial的问题，也即是多项式复杂程度的问题。NP就是Non-deterministicPolynomial的问题，也即是多项式复杂程度的非确定性问题。P是所有可在多项式时间内用确定算法求解的判定问题的集合。NP是所有可在多项式时间内用不确定算法求解的判定问题的集合。,27,9.2.2P类与NP类语言,PNP。直观上看，P类问题是确定性计算模型下的易解问题类，而NP类问题是非确定性计算模型下的易验证问题类。大多数的计算机科学家认为NP类中包含了不属于P类的语言，即PNP。,28,9.2.2P类与NP类语言,NP类语言举例无向图的团问题。该问题的输入是一个有n个顶点的无向图G=(V，E)和一个整数k。要求判定图G是否包含一个k顶点的完全子图(团)，即判定是否存在VV，|V|=k，且对于所有的u，vV，有(u，v)E。若用邻接矩阵表示图G，用二进制串表示整数k，则团问题的一个实例可以用长度为的二进位串表示。因此，团问题可表示为语言：CLIQUE=w#v|w，v0，1*，以w为邻接矩阵的图G有一个k顶点的团，其中v是k的二进制表示。,29,9.2.3多项式时间验证,VP=L|L*，为一有限字符集，存在一个多项式p和一个多项式时间验证算法A(X，Y)使得对任意X*，XL当且仅当存在Y*，|Y|p(|X|)且A(X，Y)=1。,多项式时间可验证语言类VP可定义为：,定理9-1：VP=NP。,例如(哈密顿回路问题)：一个无向图G含有哈密顿回路吗?无向图G的哈密顿回路是通过G的每个顶点恰好一次的简单回路。可用语言HAM-CYCLE定义该问题如下：HAM-CYCLE=G|G含有哈密顿回路,30,9.3NP完全问题,NP完全理论指出在NP类中有一些问题具有以下性质：若其中一个问题获得多项式算法，则这一类问题就全部获得了多项式算法；反之，若能证明其中一个问题是多项式时间内不可解的，则这-类问题就全部是多项式时间内不可解的。这类问题将称之为NP完全问题。NP完全理论不打算找出这一类问题的算法，仅仅着眼于证明这一类问题的等价性，即证明它们的难度相当。目前还没有一个NP完全问题有多项式时间算法。,31,9.3NP完全问题,NP完全理论还很年轻，有许多问题等待人们研究。例如，“NPP”还是相反“P是NP的真子集”。这个问题是当代计算机科学中的一大难题。,各类问题之间的关系,32,9.3.1多项式时间变换,定义：语言L是NP完全的当且仅当(1)LNP；(2)对于所有LNP有LpL。如果有一个语言L满足上述性质(2)，但不一定满足性质(1)，则称该语言是NP难的。所有NP完全语言构成的语言类称为NP完全语言类，记为NPC。,设，是2个语言。所谓语言能在多项式时间内变换为语言(简记为p)是指存在映身f:，且f满足：(1)有一个计算f的多项式时间确定性图灵机；(2)对于所有x，x，当且仅当f(x)。,33,9.3.1多项式时间变换,定理9-2：设L是NP完全的，则(1)LP当且仅当PNP；(2)若Lp，且NP，则是NP完全的。,定理的(2)可用来证明问题的NP完全性。但前提是：要有第一个NP完全问题L。,34,9.3.2一些典型的NP完全问题,部分NP完全问题树,可满足性问题,35,迄今为止，所有的NP完全问题都还没有多项式时间算法。对于这类问题，通常可采取以下几种解题策略。(1)只对问题的特殊实例求解(2)用动态规划法或分支限界法求解(3)用概率算法求解(4)只求近似解(5)用启发式方法求解,9.4NP完全问题的近似算法,36,小结,P(Polynomial问题)。从理论上来说，如果一个问题能够有多项式的解法的话，就算是一个很好的算法了。这种问题总可以找到一个DTM（DeterministicTuringMachine）。NP(NondeterministicPolynomial问题)。对于很多问题来说，找不到一个多项式的解决方法，他们只能对应一个NDTM(NondeterministicTuringMachine）来解决。对于下一步的动作，他们也不知道确切的应该怎么办，只能“尝试”很多种方案才能够得出一个答案，这显然是很费时的，这种问题就是NP问题。NPC(NPComplete)问题，可以这么认为，这种问题只有把解域里面的所有可能都穷举了之后才能得出答案，这样的问题是NP里面最难的问题，这种问题就是NPC问题。NPC问题是一个问题族，如果里面任意一个问题有了多项式的解，那么所有的问题都可以有多项式,