计算的复杂性第七章NP完全问题.ppt

Email： 2019年5月6日星期一,计算的 复杂性,计算机科学与工程学院,顾 小 丰,99 - 2,2019/5/6,第7章 NP完全问题,判定问题、语言和编 码 多项式变换与可满足 性问题 非确定型图灵机 NP类,NP完全问题与Cook 定理 强NP完全问题 Co-NP类问题 NP困难问题 空间复杂性简介,99 - 3,2019/5/6,序,对一个已确定是可计算的问题，人们总试图寻求实现它的最优算法。然而对有些问题，这个工作难度很大，目前还不能做到这点。,目前人们已经证明了一些问题，它们的时间复杂性是多项式阶 的，这只须设计一个实现它的时间复杂性是多项式阶的算法即可，例 如分类（又称排序）问题。这样一类问题将被称之为P类问题。还有一 类问题，人们已经设计出实现它的时间复杂性为指数阶的算法，并且 已证明该问题不存在多项式阶的算法，例如梵塔问题；这样一类问题 人们称之为顽型问题。但是有这样一类问题，人们目前已设计的实现 它的算法其时间复杂性为指数阶的，但还不能肯定它有或没有多项式 阶的算法，例如第6章讨论的当m2时任意图的m-可着色问题。为研 究这类问题，人们又设计一种称为非确定图灵机的计算模型，这些问 题对应一个非确定的图灵机，而且可以在多项式时间内完成计算。人 们称这类问题为NP问题，NP是Nondeterministic Polynomial的缩 写，即非确定的多项式的意思。,99 - 4,2019/5/6,1971年S. Cook发表了“The Complexity of Theorem Proving Procedures”这篇著名论文，1972年R. Karp发表了“Reducibilty Among Combinatorial Prob1ems”，从此奠定了NP完全理论的基础。NP完全理论指出在NP类中有一些问题具有以下性质：若其中一个问题获得多项式算法，则这一类问题就全部获得了多项式算法；反之，若能证明其中一个问题是多项式时间内不可解的，则这-类问题就全部是多项式时间内不可解的。这类问题将称之为NP完全问题。NP完全理论不打算找出这一类问题的算法，仅仅着眼于证明这一类问题的等价性，即证明它们的难度相当。 NP完全理论还很年轻，有许多问题等待人们研究。例如，“NPP”还是相反“P是NP的真子集”。这个问题是当代计算机科学中的一大难题。,99 - 5,2019/5/6,7.1 判定问题、语言和编码,我们讨论的几种计算模型，都可以认为是语言的接受器或函数的计算器。 为讨论问题简明，本章只讨论语言的识别问题。这是因为象图论、数论、逻辑和规划中的种种问题常常可以表示为语言的识别问题。其它的计算问题往往都有对应的判定问题。这种问题只有两个可能的解，或者回答“是”，或者回答“否”。,99 - 6,2019/5/6,判定问题,定义7-1 判定问题是由实数集合D和“是”的实例子集YD组成。 但是，我们感兴趣的多数判定问题具有相当数量的附加结构，在描述判定问题时，要强调这些附加结构。我们用来规定问题的标准格式由两部分组成。第一部分用各种分量，如集合、图、函数、数字等规定该问题的一般实例。第二部分陈述根据这个一般实例提出的是-否问题。规定D和Y的方法是明显的，一个实例属于D当且仅当它可以通过用规定类型的具体对象替换一般实例中的所有分量得到，而这个实例属于Y当且仅当具体到这个实例时，对所陈述的问题的回答为“是”。,99 - 7,2019/5/6,货郎担问题,实例：一个有穷的“城市”集合C=c1,c2,cm，对于每一对城市ci,cjC有“距离”d(ci,cj)Z+，以及界限BZ+（这里Z+表示正整数集合）。 问：是否有经过C中所有城市的“旅行路线”，其全长不超过B，即是否有C的一个排列次序使得,99 - 8,2019/5/6,语言,我们只考虑判定问题的原因是因为它们有一个非常自然的、适合在数学上精确的计算理论中研究的形式对应物。这个对应物叫做“语言”，其定义如下： 定义7-2 对于任意有穷符号集合，我们用*表示所有的有穷字符串组成的集合。如果L是*的一个子集，我们称L是字母表上的语言。 例如，如果=0,1，那么*由空字符串“”，字符串0、1、00、01、10、11、000、001以及所有其它0和1的有穷字符串组成。于是01,001,111,1101010是0,1上的一个语言，由所有完全平方数的二进制表示组成的集合以及集合0,1*本身也都是0,1上的语言。,99 - 9,2019/5/6,编码,判定问题的每一实例可以编码成一个符号串，这样就将判定问题重新描述为一个语言的识别问题。这个语言必须由对应的判定问题中回答“是”的一切实例编码的串组成。 在选择编码方法时，必须慎重，因为一个问题的复杂性可能与编码的方法有关。由于问题的难度在本质上不依赖于用来决定时间复杂性的具体编码方法和计算机模型，因此很难想象一个“合理的”编码方法与标准的编码方法之间的差异超过多项式。,99 - 10,2019/5/6,编码的条件,实例I的编码必须是简洁的，不能“填塞”不必要的信息或符号； I中出现的数字必须用十进制（或二进制、八进制、以及以任何不等于1的数为基的进制）表示。,虽然不可能把我们在这里用“合理的”这个词表示的含义形式化，但是下述两个条件抓住了这个概念的主要内容：,99 - 11,2019/5/6,编码的标准,如果我们规定只使用满足这些条件的编码方法，那么具体使用什么编码方法将不会影响关于一个给定问题的难度的判断。为此，我们对问题的标准表示约定如下： 整数用十进制表示； 用十进制数1,2,.,n表示一个图的n个节点，用(i1,i2)表示图中的边，其中i1,i2分别是该边的两个端点； 具有n个命题变元的布尔表达式由*（与），+（或），（非）与整数1,2,.,n（命题变元）所组成的字符串表示，其中*可以省略（但不引起混淆），必要时可以加括号。例如，布尔表达式(P1+P2)*P3可以写成：(1+2)3。,99 - 12,2019/5/6,当把整数及其它符号都采用二进制编码后，一个问题的判定过程就可以形式地描述如下： 已知 L0，1*，对于x0，1*，若xL则回答“是”；若xL，则回答“非”。 这里，0，1*是指由有限个0和1组成的串的集合。 再次重申，我们的讨论仅限于语言的识别。,99 - 13,2019/5/6,7.2 多项式变换与可满足性问题,定义7-3 PL0,1*|L为确定图灵机在多项式时间内所接受。 该怎义中符号“”意义为“定义为”。 定义7-4 f|f:0，1*0，1*且f可在多项式时间内完成。 这个定义是说，表示可在多项式时间内完成0，1*0，1*这一转换的集合。,99 - 14,2019/5/6,多项式变换,定义7-5 若A0，1*，B0，1*且存在f使得 xA f(x)B 成立，则称A可多项式变换于B，记作 ，或简称A变换为B。 符号 的意思是：存在一台确定图灵机M，它将可以A在多项式时间内转换为B。,99 - 15,2019/5/6,引理7-1,引理7-1 若 ，BP，则AP。,证明： xA f(x)B f，所以由f产生的输出也必有多项式界，设为多项式g。但B也有多项式界，设为h。对于输入x，先作用以f，接着解属于B的问题，总共所需时间： g(|x|)+h(g(|x|) 显然也是多项式，所以AP，这个过程可以用下图表示：,问题A的输入x,问题B的输入,最长为(g(|x|),f转换至多在g(|x|)内将x换成f(x),多项式h(g(|x|)内求解B,输出问题B的解,99 - 16,2019/5/6,可满足性问题,实例：集合L=A，B，.，A，B，.，c1，c2，.，ck是L的有限子集，称为子句。每个ci中不出现L中的互补对（即xcI则xci），i=1，2，.，k。 问：是否存在一集合SL，满足以下两个条件： s中不包含互补对； 。,99 - 17,2019/5/6,从数理逻辑看来，设U=u1,u2,um是一个布尔变量集合。关于U的真值赋值是一个函数t：UT,F。如果t(u)=T，我们称u在t下取“真值”；如果t(u)=F，我们称u取“假值”。如果u是U中的一个变量，那么u和u是U上的文字。文字u在t下取真值当且仅当变量u在t下取真值；文字u取真值当且仅当变量u取假值。 U上的子句是U上的一个文字集合，例如，u1u2 u8。它表示这些文字的析取，对于U上的一个真值赋值，这个真值赋值满足它当且仅当它至少有一个元素在这个赋值下取真值。除去t(u1)=F，t(u2)=T和t(u8)=F之外，t满足上面那个子句。U上的子句类C是可满足的当且仅当存在关于U的一个真值赋值同时满足C中所有子句。我们称这样一个真值赋值是满足C的真值赋值。,99 - 18,2019/5/6,命题逻辑的可满足性问题,实例：布尔变量集合U以及U上的子句类C。 问：是否存在满足C的真值赋值？ 例如，U=u1,u2和C=u1u2，u1u2是SAT的一个实例，对这个实例的回答为“是”，t(u1)=t(u2)=T给出一个满足的真值赋值。如果用Cu1u2，u1u2, u1代替C也给出一个实例，对这个实例的回答为“否”，C不是可满足的。 可满足性问题常用符号SAT表示，它是Satisfiability的缩写。,99 - 19,2019/5/6,图的m-可着色问题,实例：无向连通图G-(V,E)和m种不同的颜色，用这些颜色为G的各节点着色，每个节点着一色。 问：是否有使得G中任何一条边的两个节点的颜色不同的着色法。 例7-1 图的m-可着色问题可以多项式变换为SAT。 证明：已知图G的节点数为n，c1，c2，.，cm表示m种颜色，设,99 - 20,2019/5/6,因此，G的每一种着色方案对应于给mn个变量Pij的一种赋值。但是必须满足条件： (1)每个节点至少有一种颜色，故对任一i，有子句Pi1Pi2.Pim； (2)相邻的节点着不同颜色，故对图G的任意一对相邻节点(r,s)，必有PrjPsj，1jm。 于是图G可m-着色的充要条件是可对变量Pij赋值i=1,2,.,n，j=1,2,.,m，使得由(1)和(2)构成的所有子句取值为T。 转换步骤(1)，(2)所需的时间有多项式的界。,99 - 21,2019/5/6,哈密顿回路问题（HC）,实例：图G=(V,E)。 问：G是否包含一条哈密顿回路，即是否有G的节点排列次序使得(vn,v1)E和(vI,vi+1)E，1in？这里n=|V|。 例7-2 哈密顿回路问题（HC）可以多项式变换为货郎担问题（TS）。 证明：函数f的定义十分简单。设G=为给定的HC的实例，|V|=n。对应的TS的实例有一个等于V的城市集合C，对任意两个城市i,j，若(i,j)E，则规定d(i,j)=1，否则d(i,j)=2。令界限B=|V|。,99 - 22,2019/5/6,容易（非形式地）看到，能够用一个多项式时间算法计算这个函数f。对于 个规定的耗费d(i,j)，只需要检查(i,j)是否是G中的一条边，所以f。 假设(1,2,.,n)是G中的一条哈密顿回路，那么(1,2，.,n)也是f(G)中的一条周游路线，并且这条周游路线的耗费为B=n，这是因为在这条周游路线中经过的城市之间每一段耗费对应G中一条边，从而耗费为1。反之，假设(1,2,.,n)是f(G)中的一条总耗费为不超过B的周游路线。因为任意两个城市之间的耗费不是1就是2，而在计算周游路线的总耗费时恰好是n个这样的耗费相加，所以根据B=n，每一对相继访问的城市间的耗费恰好为1。由的f(G)定义，得到(i,i+1),1in和(n,1)都是G的边，从而(1,2,.,n)是G的一条哈密顿回路。,99 - 23,2019/5/6,引理7-2,若L1 L2，L2 L3，则L1 L3。,99 - 24,2019/5/6,7.3 非确定型图灵机,为讨论NP问题，再引进一种虚设的计算模型，即非确定型图灵机。 定义7-6 一个k-带非确定型图灵机（NDTM）M可由下述7元组确定： M= 其中Q，T，I，b，q0和qr的定义与确定型图灵机相同（参看第5章定义5-3），而是： QTkA|AQ(TL，R，S)k。,99 - 25,2019/5/6,定义指出，非确定型图灵机，对于由一个状态与k个磁带符号所给定的序组，确定的下一动作不是唯一确定的，它将要在一个有穷集合A中选择（猜测），它在同一时刻里可以做多种运算。但要注意，一个NDTM机M只能在A中任意选择其下一个动作，然而不能选A以外的动作。 假定(q,(a1,d1),(a2,d2),.,(ak,dk)(q,a1,a2,.,ak)，并且非确定型图灵机M正处在状态q，且第i个磁头（1ik）正扫描着第i条磁带上符号ai的某一方格，则机器的下一动作可以进入状态q，并把ai变为ai，而各磁头的动作由di指定。,99 - 26,2019/5/6,图灵机的格局,定义7-7 称D=为k-带图灵机的一个格局，若每一个ai形为xqy，其中xy是在当前状态q下第i条带上的符号串（不计右端的空白符），q为机M的当前状态，q后面的第一个符号是M在第i条带的带头所扫描的方格符号。 若机M是确定型的且当前格局D不处于停机状态，则可由下一动作函数唯一地确定下一个格局D，并记为DMD，称为D转到D。 对于非确定型机M，从当前格局D可导致多于一个的下一格局（但仅有穷个），若D是其中之一，则记为DMD（或DD，若不引起混乱）。 若对某个k1，有c1c2ck或cl=ck，则可记作c1*ck。,99 - 27,2019/5/6,非确定型图灵机的作用,非确定型图灵机M可以用作一种语言L的识别器。对于语言L，我们可以构造一台非确定型图灵机M，让机器的带符包括该语言的字母表（输入字母表）以及伪空白符b和其它一些特定符号（辅助符号）。机器处于开始状态时，将输入w打印在第一条磁带的最左面部分上，此外全为空白，而其它的磁带此时全为空白；把各条磁带的磁头放在该磁带之最左一格上。称输入w被这台机器接受，仅当： * 其中a1（因此一切a2,.,ak）有停机状态qr于其中。,99 - 28,2019/5/6,定义7-8 对语言L，按上述方法构成的非确定型图灵机NDTM接受L，当且仅当对wL，NDTM可接受w，对wL，NDTM陷入不停机状态。非确定型图灵机NDTM接受语言L，记作L(NDTM)。,非确定型图灵机NDTM接受语言L,99 - 29,2019/5/6,例7-3 等分划问题,试设计一台NDTM，它接受了形如：,的字，其中i1，i2，.，ik为非负整数满足下述要求：有I1, 2,.,k使,换言之，字w被接受当且仅当用字w所表现的数列i1，i2，.，ik，可以被分割为两个子序列，各子序列的数之和相等。这个问题是所谓等分划问题，已经知道，它是一个NP完全问题。,99 - 30,2019/5/6,下面设计一台三带NDTM来接受所述的语言。这台NDTM的工作情况是：对输入磁带从左到右进行扫描，每次搜索全为0的一个磁带段0ij，并且不确定地在第2或第3磁带上增补选ij个0；当扫描到输入末端时，机器便核对第2磁带与第3磁带上0的个数，若相等则接受（注意，可能有许多情况导向了不相等，但我们关心的是：有一种选择导致相等）。设NDTM=，下一动作函数如表7-1所示。 下面给该机器输入1010010，我们从许多可能选择的计算中，列出两个可能的计算，其中的第一个导向了对该输入是接受的，而第二个计算不接受该输入。因此，按我们的定义，该机器接受1010010。,99 - 31,2019/5/6,表7-1 例7-3中非确定型图灵机M的下移函数,99 - 32,2019/5/6, 接受。, 停止，因无下一格局。,99 - 33,2019/5/6,NDTM的时空复杂性,定义7-9 称一台NDTM机M的时间复杂性是T(n)，假若对于任何长为n的可接受的输入w，都存在着一条导向接受指令的计算路，该计算路至多有T(n)步。称M的空间复杂性是S(n)，假若对于上述输入w，有一条导向接受指令的计算路，于其中在每一条带上至多有S(n)个相异的磁带方格被扫描过。,99 - 34,2019/5/6,例7-3的复杂性,例7-4 对于例7-3所设计的机器M，其时间复杂性为2n+2，而空间复杂性为n+1。对所述的空间复杂性是显然的，为了看出时间复杂性为2n+2，只须注意：当对输入扫描结束（共用n+1步）后，要回头对2、3磁带进行比较（不超过n+1步）。,99 - 35,2019/5/6,用DTM模拟NDTM,原则上，对于每一台NDTM机，都可以设计一台DTM机来模拟它，使得两者皆接受了同一语言。然而DTM的时间耗费要大得多，可以证明，这种模拟的时间耗费下界是指数型的。确切地说，设T(n)是“时间可构造的”函数（即存在一台DTM机，给出该机的任一输入n，机器将在第T(n)步停机），则对每一台为T(n)时间囿界的NDTM机M，可以找到一个常数cl和一台DTM机M使L(M)=L(M)且M的时间复杂性为O(cT(n)。 为了证明这个结果，可以用穷举算法来构造一台模拟M的DTM机M。首先，可以找到常数d，使得NDTM机M在任何情况下的下一动作,99 - 36,2019/5/6,的选择可能不超过d个。因此机器M的长度不超过T(n)的任何一条计算路都可用字母表=0，1，.，dn-1的长不超过T(n)的一个字来表现，这些字至多为(d+1)T(n)个。事实上，只有dT(n)个可将其按字母次序排列。对于长为n的输入x，DTM机M模拟NDTM如下，依次模拟上述w*为w，（即M在这次模拟中的计算路），如M中不存在如w所示的计算路或者w不是M接受x的计算路，则M去模拟w的下一个次序的字母所示的计算路。注意，M在每次模拟时要耗时O(T(n)，于是整个模拟至多耗费时间O(T(n)(d+1)T(n)（事实上为T(n)dT(n)）取c=2(d+1)即可。细节的叙述要用到T(n)的时间可构造性（因模拟w到长为T(n)止），这里就不再叙述了。这样我们就证了下述定理：,99 - 37,2019/5/6,定理7-1,如果取上述非确定型图灵机类为计算模型，则这个计算模型同已知的种种计算模型等价。 对于任一台NDTM时间囿界为T(n)且T(n)为时间可构造的机器M，都可以找到常数c1和DTM机M使L(M)=L(M)且M的时间下限为O(cT(n)。,然而，我们不知道有一个为NDTM在时间复杂性T(n) 里接受的语言L，一切DTM在时间复杂度T(n)都不能接受 它。,99 - 38,2019/5/6,定理7-2,若NDTM机M的空间复杂性为S(n)，且S(n)使空间可构造的，则存在一台DTM机M，它的空间复杂性是O(S3(n)且L(M)=L(M)。 所谓一个函数S(n)是空间可构造的，如果存在一台DTM机M，当给它一个长度为n的输入，M机将在它的一条带的第S(n)个方格上放置一个特殊的标记符号并且对任何带不会使用多于S(n)个方格。绝大多数函数，例如多项式、2n、n!、n1og(n+1)都是空间可构造的。,99 - 39,2019/5/6,定理7-3,设语言L可以为时间复杂性为T(n)的k-带NDTM机所接受，则L也可以被一台时间复杂性为0(T2(n)的单带NDTM机所接受。 这个定理使我们在讨论与非确定型图灵机有关问题时，可以只对单带机而言，于是便简单一些。,99 - 40,2019/5/6,7.4 NP类,有了非确定型图灵机这一计算模型，这里将讨论一个新的语言类NP类问题。 定义7-10 NPL0,1*|L为非确定图灵机在多项式时间内所接受。 因为确定型图灵机是非确定型图灵机的特殊情况，于是有： PNP 目前人们尚未证明P=NP，或P是NP的真子集。,99 - 41,2019/5/6,例7-5,无向图的团集问题属于NP类。 团集问题定义如下： 实例：图G=(V,E)和正整数J|v|。 问：G是否包含大小不小于J的团，即是否有子集VV，使得|V|J并且V中每两个节点都由E中的一条边连接着。,99 - 42,2019/5/6,首先对团集问题编码。设G=(V,E)，V=1,2,.,n，则表现团来问题的语言L由形如： k(i1,j1)(i2,j2).(im,jm) 组成，这里k2，ik,jkV且(ik,jk)E，k=1,2,.,m，如图7.4-1所示。 当k=3，可编码为： 3(1,2)(1,4)(2,3)(2,4)(3,4)(3,5)(4,5)。 当然可以用二进制编码，因为对于任意两种编码语言，可以在多项式时间内互相解释。 如下设计工台NDTM机M，输入长为n的串w： k(i1,j1)(i2,j2).(im,jm),99 - 43,2019/5/6,该机可在O(n3)时间内认知w，其构成是： (1)若kn，机M计算1步便停机在拒绝指令上. (2)kn，机M在G的一切k点子集中猜测（选择）一个k点团集，并对之进行验证。确切地悦，就是要验证所有猜测的k点子图的任何两个相异点间均有一条边连接。注意到一个k点团集共有：,条边，每验证一边可从头到尾看完字w（长度为n），故共用O(n3)步。 注意：这台NDTM的能力是它能同时“并行”地对一切可能的k点子图进行验证。若有k点团集存在，则接受w，否则拒绝，而时间复杂性仅为O(n3)。,99 - 44,2019/5/6,例7-6,命题逻辑的可满足问题是一个NP问题。,99 - 45,2019/5/6,首先把布尔式写成标准编码，例如：(Pl+P2)*Ps写成(1+2)3。 设L表示命题逻辑的可满足问题的语言，要证明LNP为此，可构造一台NDTM机M，其时间复杂性为O(n2)且L(M)=L。输入w的长为n： A1,A2,.,Am （1mn） 其中每一Ai为a1+a2+.+ak（1kn）而每一ai为j或 j。NDTM机M猜测（选择）一个满足指派（不超过2n种）。 只要有一个Ai=0，则拒绝w；当所有Ai=1，则接受w。而对每一个Ai，Ai=0 一切aj=0。对每一Ai核对是否为0要用O(n)步，于是核对是否w=0要用O(n2)步。这里之所以在步可以接受或拒绝，使因为我们使用了对于一切指派“并行”地处理这一不确定的过程。,99 - 46,2019/5/6,定理7-4,(1) SAT； (2) 团集问题； (3) 节点覆盖问题（VC）； (4) 哈密顿回路问题（HC）； (5) 图的m-可着色问题；,(6) 回路节点集问题； (7) 回路边集问题； (8) 有向图哈密顿回路问题； (9) 集合覆盖问题； (10) 恰当覆盖问题；,下面各问题都在NP中。,99 - 47,2019/5/6,实例：图G=(V,E)和正整数k|v|。 问：G是否有大小不超过k的节点覆盖，即是否有子集V使 得|V|k并且对每一条边(u,v)E，u和v中至少有一个属于V？,节点覆盖问题（VC）,回路节点集问题,实例：有向图G=(V,E)和正整数k|v|。 问：G是否有元素个数为k的回路节点集，即是否有SV, |S|k，使得G的每一条回路都有一个点在S中?,99 - 48,2019/5/6,回路边集问题,实例：向图G=(V,E)和正整数k|E|。 问：G是否有元素个数为k的回路边集，即是否有FE， |F|k，使得G的每一条回路都有一条边在F中?,有向图哈密顿回路问题,实例：有向图G=(V,E)。 问：G是否包含一条哈密顿回路，即是否有G的节点排列 次序使得E和E，1in？这里n=|V|。,99 - 49,2019/5/6,集合覆盖问题,实例：一族（有穷）集合S1,S2,.,Sn及正整数kn。 问：是否存在子族Si1,Si2,.,Sik使得,实例：一族（有穷）集合S1,S2,.,Sn及正整数mn。 问：是否存在子族Si1,Si2,.,Sim使得,恰当覆盖问题,且Sijsim=，jm,99 - 50,2019/5/6,7.5 NP完全问题与Cook定理,在NP类问题中，Cook首先发现可满足问题具有特殊的重要性质，之后人们又证明了有很多NP类中的问题，也具有同样的性质，于是形成了NP完全问题类。,99 - 51,2019/5/6,NP完全的定义,定义7-11 称L0NP为NP完全的（简称NPC），如果下述条件能满足：对于认识L0的时间复杂性为T(n)n的任一个确定算法，那么对每一个LNP都能找到一个时间复杂性为T(PL(n)的确定算法认识L，这里PL(n)是依赖于L的一个确定多项式。 上述定义有时称为广义NP完全的定义。在NP完全理论中常用以下另一种关于NP完全的定义，称为狭义NP完全。 定义7-12 称L0NP是NP完全的，如果对一切LNP都有 。,99 - 52,2019/5/6,定理7-5,若L0是狭义NP完全的，则L0是广义NP完全的。,证明：设L0为某一确定型图灵机A在时间T(n)n内所认识，不妨设T(n)为递增的。因L0为狭义NP完全，于是存在确定型图灵机M，它可以把LNP在多项式P(n)内将L翻译成L0。 构成一台新机器M*如下：输入wL，先用M将w译成w0L0（时间耗费界为P(|w|)，再将w0输入A并计算（时间花费界为T(|w0|)。因为M机输出w0时至少用过|w0|个磁带方格，故对应的计算步数不能少于|w0|，于是 |w0|P(|w|)。,99 - 53,2019/5/6,总之，新机M*认识L的时间上界应满足： P(|w|)+T(|w0|)P(|w|)+T(P(|w|) 此步因为T(n)是递增函数。再由T(n)n，可得： P(|w|)T(P(|w|) 综上可得： P(|w|)+T(|w0|)2T(P(|w|)T(2P(|w|) 即M*机可以在T(PL(n)内认识L，这里PL(n)=2P(n)，是与L有关的一个多项式，于是由定义7-11，L0是NP完全的。,但是以上定理7-5之逆，至今还没有肯定或否定的证明。,99 - 54,2019/5/6,定理7-6,我们以后谈到NP完全的，都是指定义7.5-2给出的狭义NP完全，由以上定理，当然也是广义NP完全的。 由NP完全的问题的定义，显然有： 定理7-6 设L0为任一NP完全的语言，那么 L0P P=NP 这个定理恰说明NP完全理论的重要性。人们只须对具体某个NP完全的问题深入研究，如果能肯定它是P类，则所有NP问题就都属于P类；反之如果能肯定它不是P类，则NP类就是P类的真扩集（或说P类是NP类的真子集）。 NP完全的问题存在吗？Cook在1971年首先回答了这个问题。,99 - 55,2019/5/6,证明：例7-6已证明了SATNP，故只须证明对每一个语言LNP， 。换言之，对于一台在多项式界时间内接受L的NDTM机M，对M的一个输入w，都有一个（依赖于L的）多项式界的算法来构成一个布尔式w0，使得w0可满足当且仅当M接受w，由定理7-3，我们可假定M是单带的。假定M有状态q1，q2，.，qs，磁带符号x1，x2，.，xs，M的时间复杂性为P(n)。 若给机M输入长为n的w，如M接受w，则M在P(n)步内接受停机，故至少存在一条计算路Q0 Ql . Qg，这里Q0是开始格局，Qg为接受格局，gP(n)。,Cook定理,定理7-7 命题逻辑的可满足问题是NP完全的。,99 - 56,2019/5/6,我们的目的是构造一个布尔式w0，它能“模拟”机M中所能进入的格局序列：即w0的变元的每个真(1)假(0)指派表现了M的至多一条计算路（也可能所表现的不是M的合法的计算路），w0取值1当且仅当指派表现了导致接受格局的计算路Q0，Q1，.，Qg。换言之，w0可满足当且仅当M接受w。我们先叙述一下w0中要用到的命题交元。 (1) C取值1当且仅当机M在瞬时t即第t步的第i个磁带方格内有符号xj，其中1iP(n）（这是因为机M的时间复杂性为P(n)，则磁带复杂性P(n)），1jm，0tP(n)。 (2) s取值1当且仅当机M在瞬时t处于状态qk，这里1ks，0tP(n)。 (3) H取值1当且仅当在瞬时t磁头扫描着第i个磁带方格,这里1iP(n)，0tP(n)。,99 - 57,2019/5/6,上述命题变元共有mP(n)2+sP(n)+P2(n)个，故阶为O(P2(n)。如果要用二进制数来编码表示这些命题变元，则至多用到Clog2n位的二进数即可，C为与P有关的常数（事实上，设P(n)为P0次多项式，则O(P2(n)=O(n2P0)，命C=2P0+1，则Clog2n位二进数可表示2Clog2n=nC=n2P0+1个十进制数）。 但我们下面仍用一个单独的符号表示一个命题变元。这样做将失去因子Clog2n，但这并不影响我们对问题的讨论，因为我们只需要一个多项式时间囿界的函数。 我们要以上述命题变元来构成w0，在构造中要用到一个谓词U(x1，x2，.，xr)，它取值为1当x1，x2，.，xr中恰有一个取值为1，U可表示为：,(7-1),99 - 58,2019/5/6,这个式子中的第一个因子说xi中至少有一个取值1，其余的r(r-1)/2个因子说没有两个相异的xi同时取值为1。注意，U的长度是： (r+(r-1)+5r(r-1)/2 即O(r2)（严格地说，因一个命题变元符号至多O(Clogr)二进制码表示，故U的长度至多为O(r3)）。 若M接受w，则存在一个接受w的计算路Q0，Q1，.，Qg。为使讨论简单，可不失一般地假定：不管M是否已进入接受格局，我们都让M继续“计算”下去，但对于已进入接受格局时，其下面的“计算”将不移动磁头也不改变已进入的接受状态，直到第P(n)个格局止。 下面，可用7个式子A，B，.，G来构成w0，它判断了：Q0，Q1，.，Qg是一条接受w的计算路，这里每个Qi长为P(n)，g=P(n)。,99 - 59,2019/5/6,判断Q0，Q1，.，QP(n)为一条接受w的计算路等同于判断下述7条事实： (1) 在每个格局Qi中，磁头只扫描着一个磁带方格。 (2) 每个格局Qi中的每一个磁带方格内只有一个磁带符号。 (3) 每个格局Qi中只有一个状态。 (4) 在该计算路中，从一格局到它的下一格局时，至多只能修改上一格局中被扫描方格内的符号。 (5) 该计算路各格局的状态，磁头位置以及磁带方格内的符号的变化符合M的下一动作函数的要求。 (6) Q0是机M在输入w0时的开始格局。 (7) 该计算路的最后一个格局的状态是停机状态。,99 - 60,2019/5/6,现在来构成与判断(1)(7)相应的布尔表达式AG。 (1) 令At=(H，H，.，H) At的意思是说:在瞬时t，M的磁头恰好扫描着某一磁带方格。则置A=A0A1.AP(n)表述了上述判断(1)。 注意：因用一个符号表示一个命题交元H，故A的长为O(P3(n)，而且可在O(P3(n)时间内（用一台DTM机）写下这个式子。 (2) 令Bit=(C，C，.，C) 它的意思是说：在瞬时t，第i个磁带方格内只有一个符号。则置,表述了上面判断(2)。,注意：因m为机M的磁带符号数为常数，故Bit与n无关。因而B的长是0(P2(n)。,99 - 61,2019/5/6,(3) 令,因S为机M的状态数是常数，故C的长为O(P(n)。,其中式子(CC)+H的意思是： 在瞬时t，磁头正扫描着第i个磁带方格（即H），或者 在瞬时t+1，第i个方格中的符号仍是瞬时t时的符号xj。,(4) 下面的D表述了在任一瞬时t，至多可以改变一个磁带方格中的内容：,注意：1iP(n)，1jm且1tP(n)，m为常量，故D的长为0(P2(n)。,99 - 62,2019/5/6,(5) 令,其中中的l遍及于当机器M扫描着xj且处于状态qk时所有可能的下一动作，即是说，对每一(qk,xj)，有一l值使xjl=x，qkl=q且il为i-1，i，i+1分别以d为L，S或R而定。为机M的下一动作函数。 注意：因为M是不确定的，故可能有多于一个的，但在任何情况下却只能有至多某一有穷常数C个。故Eijkt的长被一常数囿界而与n无关。 这里的Eijkt判断了下面的四个命题中（至少）有一个成立，,99 - 63,2019/5/6,在瞬时t第i号磁带方格中不是符号xj， 在瞬时t磁头并不扫描着第i号磁带方格， 在瞬时t，M没有处于状态k，或 M的下一格局是依据M的下一动作函数从上一格局而获得的。,置,注意：i，j，k，t的变化区域，可知E的长为O(P2(n)。,，则E表述了上述判断(5)。,99 - 64,2019/5/6,意思是在开始时其余磁带方格为空符号。这里不妨假定x1是空白符。显然，F的长度为0(P(n)。,(6) 令,这里，S(1,0)是说在瞬时0，M处于状态q1，而q1是M的开始状态。而H(1,0)说在瞬时0，M扫描着第1号方格。,意思是前n个磁带方格中打印着输入的字w。最后,(7) 取G=Ss,P(n)，这里qs是M的停机状态，则G说该计算路之最后一个格局是停机格局。,99 - 65,2019/5/6,令w0=ABCDEFG，注意上面的各个叙述，得w0的长为0(P3(n)。假若不是把一个命题看作一个单独的符号，而是用2进码来表示命题变元，则w0的长将为0(P3(n)logn)，可用cnP3(n)来囿界，换言之是多项式囿固界的。 显然，当已给定w和多项式P时，可用上述算法在cnP(n)步内写出输出w0。同时，下述事实也是完全明白的： 给定一个可接受的计算路Q0，Q1，.，Qg，可在w0中找到命题变元C(i,j,t)，S(k,t)与H(I,t)的指派使w0被满足；反之，若有一个使w0被满足的指派，则可由此找到可接受的计算路。故w0可满足 M接受wL。 最后，注意到上述构造中并未对语言L做任何限制，只是假定LNP。这样，便证明了：命题逻辑的可满足问题是NP完全的。,99 - 66,2019/5/6,Cook定理的重要意义,Cook定理是NP完全理论中非常重要得一个定理，这是因为： 首先，它以实例说明NP完全问题是存在的； 其次，它给出了判断某一其它NP问题（更确切地说是表现为这一类问题的语言）L0是否是NP完全的捷径（即不必按定义7-12证明），即只须证明：,这是因为：所有LNP， ，再由上式和多项式变换的传递性（引理7-2）可得：,一旦证明了L0是NP完全的，则它又可发挥SAT同样的作用。,99 - 67,2019/5/6,NP完全性的证明过程,从现在起判定问题的NP完全性的证明过程将由下述三步组成： 证明属于NP； 选择一个已知的NP完全问题； 构造从到的多项式变换函数f。,99 - 68,2019/5/6,7.6 强NP完全问题,在实际中，绝大多数判定问题的描述都或多或少地包含有一些数字型参 数和分量。进而，对这类判定问题中的大部分而言，其求解的难易程度、相 应求解算法的时间复杂性等，常常都受到判定问题任一具体实例中所含数字 参数的值的大小的严重影响。特别是其中出现的最大的整数的具体值，该值 的大小往往会使判定问题相应实例求解的难易性，或所用求解算法的时间复 杂性函数发生某种质的变化。对于这样的判定问题，仅仅使用表示其某个 实例I的输入长度的函数LenghI就无法全面客观地衡量实例I的大小己求解 的困难程度。为此，人们就引入了另外一个函数Max：DZ+，并通常 MaxI的值为I中所出现的最大整数的具体值。利用函数Length和Max，我 们就可以给出另一类比NP完全问题还要难于求解的问题的定义，即所谓的 强NP完全问题。,99 - 69,2019/5/6,伪多项式时间算法,定义7.6-1 如果解问题的算法的时间复杂性函数不超过两 个变量LengthI和MaxI的多项式函数,则称这个算法是关于 的伪多项式时间算法。,根据定义，任何多项式时间算法也是伪多项式时间算法，因为它的运算时间不超过只是LengthI的多项式。但是，实际中的还有许多不是多项式时间算法的伪多项式时间算法。我们用下述解整数背包问题的方法来加以说明。,99 - 70,2019/5/6,整数背包问题,实例：给定整数c1,c2,cn以及整数b。 问：是否存在整数x1,x2,xn0，使得 ？,已经证明该判定问题是NP完全的（参见8.2.1节，令cjaj，j1,2,n）。现给出求解它的一个伪多项式时间算法。先构造一个有向图G(c1,c2,cn,b)(V,E)如下： V0,1,2,b， E|0mkb，且对某个jn，k-mcj。 于是G有b+1个结点，O(nb)条边。显然这一构造过程可在O(nb)时间内完成。下面我们证明图G(c1,c2,cn,b)有一条从0到b的通路当且仅当上述整数背包问题的判定问题的实例(c1,c2,cn,b)有一个解。,99 - 71,2019/5/6,设(0=i0,i1,i2,im=b)是G中的一条通路，考虑序列(y1,y2, ,ym)(i1-i0,i2-i1,im-im-1)。则由G的定义知y1,y2,ym全 在c1,c2,cm之中，且 ，从而有非负整数解，即将xj 取成cj在(y1,y2,ym)中出现的次数。,反之，如果对于非负整数x1,x2,xn有 ，那么通过取,我们就会在G(c1,c2,cn,b)中重新找到一条从0到b的通路，这条通路是(0=i0,i1,i2,im=b)，其中 。,99 - 72,2019/5/6,对于上述构造的图G，利用图论中寻找通路的算法，我们可以 在O(nb)时间内确定是否存在一条从0到b的通路。,综上所述，我们已经证明了整数背包问题的任何实例(c1,c2, ,cn,b)均能用上述的算法在O(nb)时间内解决。显然这是一个伪多项式算法。,关于强NP完全性与伪多项式算法之间的关系，我们有以下结论。,99 - 73,2019/5/6,定理7.6-1,除非PNP，不然任何强NP完全问题都不会有伪多项式时间 算法。,证明：设为强NP完全问题，换言之，对于某个多项式p(n)，p(n)是NP完全的。此外设有一个伪多项式时间算法A，它能在某个双变元多项式q(LengthI,MaxI)的时间内求解的任何实例I。于是，A就在多项式q(n,p(n)时间内求解了NP完全问题p(n)。除非NNP，则由NP完全的定义知这是不可能的。 因此，证明一个问题是强NP完全的，不仅排除了求解它的多项式时间算法的存在性，而且也排除了其伪多项式时间算法的存在性。基于上述定理，我们也可以将强NP完全问题定义为这样一些NP完全的问题：对于它们，伪多项式时间算法的存在性将意味着PNP。,99 - 74,2019/5/6,基于多项式变换，我们在上节中指出了证明某一问题为NP完 全的一种简便而直接的方法。对于强NP完全问题，我们自然希望 也能有这样一个好的证明方法。这就要用到下列关于伪多项式变 换的概念。 令和表示任意两个判定问题，实例集合分别为D和 D，“是”的集合分别为Y和Y，并且分别规定函数Max, Length和Max,Length。从到的伪多项式交换是一个满足 下述条件的函数f：DD： (a) 对于所有的ID，IY当且仅当f(I)Y； (b) 能够在两个变量MaxI和LengthI的多项式时间内计算f； (c) 存在多项式q1使得对所有的ID， q1(Lengthf(I)LengthI； (d) 存在两个变量的多项式q2使得对所有的ID， Maxf(I)q2(MaxI,LengthI)。,99 - 75,2019/5/6,定理7.6-2,如果是强NP完全的，NP，并且存在一个从到的伪 多项式变换，那么是强NP完全的。,证明：设f是这样一个伪多项式变换，q1和q2是定义中所规定的两个函数。不失一般性，我们可以假定q1和q2只有正整数系数，因为可以修改这些多项式，只要不减少它们的值。因为是强NP完全的，所以有一个多项式P使得p是NP完全的。而且，我们可以选取P使得它只含有正整数系数，因为如果p0是任意一个整系数多项式，对所有x都有p0(x)p(x)，那末p0将包含p的所有实例，从而只要p是NP完全的，p0也一定是NP完全的。设p1是如下定义的多项式 p1(x)q2(p(q1(x),q1(x),99 - 76,2019/5/6,我们断言，当限制在p的实例上时，函数f变成从p到p1 的多项式变换，于是证明了p1是NP完全的。首先让我们来看f 把p的每一个实例I映射到p1的一个实例。根据p的定义和 q1,q2所满足的不等式，对p的每一个实例I， Maxf(I)q2(MaxI,LengthI) q2(p(LengthI),LengthI) q2(p(q1(Lengthf(I),q1(Lengthf(I) p1(Lengthf(I) 于是f(I)是p1的一个实例。其次，根据伪多项式变换的定义 中的条件(a)和(b)，以及p的每一个实例I都满足 MaxIp(LengthI)， 可立即推出f符合多项式变换的其余要求。因此p1是NP完全 的，从而得证是强Np完全的。,99 - 77,2019/5/6,结论,这个定理不仅告诉我们在证明某一新问题的强NP完全性 时，并非一定要处理另一已知为强NP完全的问题的具体例子问 题p。而且，象定理7.6-2的结论一样，它给我们提供了一个利 用伪多项式变换来证明强NP完全性的直接而简便的，类似于NP完 全情形的方法。,99 - 78,2019/5/6,7.7 Co-NP类问题,在前面讨论的问题类特别是P和NP的定义中，我们只考虑 求解或检验判定问题回答为“是”的实例所需的时间，而对于那 些答案为“否”的实例，情况如何呢？能否用同样的方法，在相 同的时间界内求解回答为“否”的实例呢？回答这些问题可从更 一般的角度进行分析，我们有如下定义。,定义7.7-1 对任一判定问题(D,