Email：guxfuestc.edu.cn*顾顾 小小 丰丰第7章 NP完全问题电子科技大学计算机学院 顾小丰计算的复杂性第7章 NP完全问题 判定问题、语言和编码 多项式变换与可满足性问题 非确定型图灵机 NP类 NP完全问题与Cook定理 强NP完全问题 Co-NP类问题 NP困难问题 空间复杂性简介 Date2第7章 NP完全问题电子科技大学计算机学院 顾小丰计算的复杂性序对一个已确定是可计算的问题，人们总试图寻求实现它的最优算法 。然而对有些问题，这个工作难度很大，目前还不能做到这点。目前人们已经证明了一些问题，它们的时间复杂性是多项式阶 的，这只须设计一个实现它的时间复杂性是多项式阶的算法即可，例 如分类（又称排序）问题。这样一类问题将被称之为P类问题。还有一 类问题，人们已经设计出实现它的时间复杂性为指数阶的算法，并且 已证明该问题不存在多项式阶的算法，例如梵塔问题；这样一类问题 人们称之为顽型问题。但是有这样一类问题，人们目前已设计的实现 它的算法其时间复杂性为指数阶的，但还不能肯定它有或没有多项式 阶的算法，例如第6章讨论的当m2时任意图的m-可着色问题。为研 究这类问题，人们又设计一种称为非确定图灵机的计算模型，这些问 题对应一个非确定的图灵机，而且可以在多项式时间内完成计算。人 们称这类问题为NP问题，NP是Nondeterministic Polynomial的缩 写，即非确定的多项式的意思。 Date3第7章 NP完全问题电子科技大学计算机学院 顾小丰计算的复杂性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的真子集”。这个问题是当代计算机科学中的一大难题。 Date4第7章 NP完全问题电子科技大学计算机学院 顾小丰计算的复杂性7.1 判定问题、语言和编码 我们讨论的几种计算模型，都可以认为是语言的接受器或函数的计算器。为讨论问题简明，本章只讨论语言的识别问题。这是因为象图论、数论、逻辑和规划中的种种问题常常可以表示为语言的识别问题。其它的计算问题往往都有对应的判定问题。这种问题只有两个可能的解，或者回答“是”，或者回答“否”。Date5第7章 NP完全问题电子科技大学计算机学院 顾小丰计算的复杂性 判定问题定义7-1 判定问题是由实数集合D和“是”的实例子集YD组成。但是，我们感兴趣的多数判定问题具有相当数量的附加结构，在描述判定问题时，要强调这些附加结构。我们用来规定问题的标准格式由两部分组成。第一部分用各种分量，如集合、图、函数、数字等规定该问题的一般实例。第二部分陈述根据这个一般实例提出的是-否问题。规定D和Y的方法是明显的，一个实例属于D当且仅当它可以通过用规定类型的具体对象替换一般实例中的所有分量得到，而这个实例属于Y当且仅当具体到这个实例时，对所陈述的问题的回答为“是”。Date6第7章 NP完全问题电子科技大学计算机学院 顾小丰计算的复杂性 货郎担问题 实例：一个有穷的“城市”集合C=c1,c2,cm，对于每一对城市ci,cjC有“距离”d(ci,cj)Z+，以及界限BZ+（这里Z+表示正整数集合）。问：是否有经过C中所有城市的“旅行路线”，其全长不超过B，即是否有C的一个排列次序使得Date7第7章 NP完全问题电子科技大学计算机学院 顾小丰计算的复杂性语言我们只考虑判定问题的原因是因为它们有一个非常自然的、 适合在数学上精确的计算理论中研究的形式对应物。这个对应物叫 做“语言”，其定义如下：定义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上的语言。Date8第7章 NP完全问题电子科技大学计算机学院 顾小丰计算的复杂性 编码判定问题的每一实例可以编码成一个符号串，这样就将判定问题重新描述为一个语言的识别问题。这个语言必须 由对应的判定问题中回答“是”的一切实例编码的串组成。在选择编码方法时，必须慎重，因为一个问题的复杂性可能与编码的方法有关。由于问题的难度在本质上不依赖于用来决定时间复杂性的具体编码方法和计算机模型，因 此很难想象一个“合理的”编码方法与标准的编码方法之间的差异超过多项式。Date9第7章 NP完全问题电子科技大学计算机学院 顾小丰计算的复杂性 编码的条件v实例I的编码必须是简洁的，不能“填塞”不必要的信息或符号；vI中出现的数字必须用十进制（或二进制、八进制、以及以任何不等于1的数为基的进制）表示。 虽然不可能把我们在这里用“合理的”这个词表示的含义形式化，但是下述两个条件抓住了这个概念的主要内容：Date10第7章 NP完全问题电子科技大学计算机学院 顾小丰计算的复杂性 编码的标准如果我们规定只使用满足这些条件的编码方法，那么具体使用什么编码方法将不会影响关于一个给定问题的难度的判断。为此，我们对问题的标准表示约定如下： 整数用十进制表示； 用十进制数1,2,.,n表示一个图的n个节点，用(i1,i2)表示图中的边，其中i1,i2分别是该边的两个端点； 具有n个命题变元的布尔表达式由*（与），+（或），（非）与整数1,2,.,n（命题变元）所组成的字符串表示，其中*可以省略（但不引起混淆），必要时可以加括号。例如，布尔表达式(P1+P2)*P3可以写成：(1+2)3。Date11第7章 NP完全问题电子科技大学计算机学院 顾小丰计算的复杂性当把整数及其它符号都采用二进制编码后，一个问题的判定过程就可以形式地描述如下：已知 L0，1*，对于x0，1*，若xL则回答“是”；若xL，则回答“非”。这里，0，1*是指由有限个0和1组成的串的集合。再次重申，我们的讨论仅限于语言的识别。Date12第7章 NP完全问题电子科技大学计算机学院 顾小丰计算的复杂性7.2 多项式变换与可满足性问题 定义7-3 PL0,1*|L为确定图灵机在多项式时间内所接受。该怎义中符号“”意义为“定义为”。定义7-4 f|f:0，1*0，1*且f可在多项式时间内完成。这个定义是说，表示可在多项式时间内完成0，1*0，1*这一转换的集合。Date13第7章 NP完全问题电子科技大学计算机学院 顾小丰计算的复杂性 多项式变换定义7-5 若A0，1*，B0，1*且存在f使得xA f(x)B成立，则称A可多项式变换于B，记作 ，或简称A变换为B。符号 的意思是：存在一台确定图灵机M，它将可以A在多项式时间内转换为B。Date14第7章 NP完全问题电子科技大学计算机学院 顾小丰计算的复杂性 引理7-1引理7-1 若 ，BP，则AP。 证明：xA f(x)Bf，所以由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的解Date15第7章 NP完全问题电子科技大学计算机学院 顾小丰计算的复杂性可满足性问题 实例：集合L=A，B，.，A，B，.，c1，c2，.，ck是L的有限子集，称为子句。每个ci中不出现L中的互补对（即xcI则xci），i=1，2，.，k。问：是否存在一集合SL，满足以下两个条件：1. s中不包含互补对；2. 。 Date16第7章 NP完全问题电子科技大学计算机学院 顾小丰计算的复杂性从数理逻辑看来，设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的真值赋值。 Date17第7章 NP完全问题电子科技大学计算机学院 顾小丰计算的复杂性 命题逻辑的可满足性问题 实例：布尔变量集合U以及U上的子句类C。问：是否存在满足C的真值赋值？例如，U=u1,u2和C=u1u2，u1u2是SAT的一个实例，对这个实例的回答为“是”，t(u1)=t(u2)=T给出一个满足的真值赋值。如果用Cu1u2，u1u2, u1代替C也给出一个实例，对这个实例的回答为“否”，C不是可满足的。可满足性问题常用符号SAT表示，它是Satisfiability的缩写。Date18第7章 NP完全问题电子科技大学计算机学院 顾小丰计算的复杂性 图的m-可着色问题 实例：无向连通图G-(V,E)和m种不同的颜色，用这些颜色为G的各节点着色，每个节点着一色。问：是否有使得G中任何一条边的两个节点的颜色不同的着色法。例7-1 图的m-可着色问题可以多项式变换为SAT。证明：已知图G的节点数为n，c1，c2，.，cm表示m种颜色，设Date19第7章 NP完全问题电子科技大学计算机学院 顾小丰计算的复杂性因此，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)所需的时间有多项式的界。Date20第7章 NP完全问题电子科技大学计算机学院 顾小丰计算的复杂性 哈密顿回路问题（HC）实例：图G=(V,E)。问：G是否包含一条哈密顿回路，即是否有G的节点排列次序使得(vn,v1)E和(vI,vi+1)E，1i n？这里n=|V|。例7-2 哈密顿回路问题（HC）可以多项式变换为货郎 担问题（TS）。证明：函数f的定义十分简单。设G=为给定的HC