文档介绍：Email:******@uestc.
11/15/2017
计算的复杂性
计算机科学与工程学院
顾小丰
第7章 NP完全问题
判定问题、语言和编 码
多项式变换与可满足 性问题
非确定型图灵机
NP类
NP完全问题与Cook 定理
强NP完全问题
Co-NP类问题
NP困难问题
空间复杂性简介
11/15/2017
99 - 2
序
对一个已确定是可计算的问题,人们总试图寻求实现它的最优算法。然而对有些问题,这个工作难度很大,目前还不能做到这点。
目前人们已经证明了一些问题,它们的时间复杂性是多项式阶
的,这只须设计一个实现它的时间复杂性是多项式阶的算法即可,例
如分类(又称排序)问题。这样一类问题将被称之为P类问题。还有一
类问题,人们已经设计出实现它的时间复杂性为指数阶的算法,并且
已证明该问题不存在多项式阶的算法,例如梵塔问题;这样一类问题
人们称之为顽型问题。但是有这样一类问题,人们目前已设计的实现
它的算法其时间复杂性为指数阶的,但还不能肯定它有或没有多项式
阶的算法,例如第6章讨论的当m>2时任意图的m-可着色问题。为研
究这类问题,人们又设计一种称为非确定图灵机的计算模型,这些问
题对应一个非确定的图灵机,而且可以在多项式时间内完成计算。人
们称这类问题为NP问题,NP是Nondeterministic Polynomial的缩
写,即非确定的多项式的意思。
11/15/2017
99 - 3
1971年S. Cook发表了“plexity of Theorem Proving Procedures”这篇著名论文,1972年R. Karp发表了“Reducibilty binatorial Prob1ems”,从此奠定了NP完全理论的基础。NP完全理论指出在NP类中有一些问题具有以下性质:若其中一个问题获得多项式算法,则这一类问题就全部获得了多项式算法;反之,若能证明其中一个问题是多项式时间内不可解的,则这-类问题就全部是多项式时间内不可解的。这类问题将称之为NP完全问题。NP完全理论不打算找出这一类问题的算法,仅仅着眼于证明这一类问题的等价性,即证明它们的难度相当。
NP完全理论还很年轻,有许多问题等待人们研究。例如,“NP=P”还是相反“P是NP的真子集”。这个问题是当代计算机科学中的一大难题。
11/15/2017
99 - 4
判定问题、语言和编码
我们讨论的几种计算模型,都可以认为是语言的接受器或函数的计算器。
为讨论问题简明,本章只讨论语言的识别问题。这是因为象图论、数论、逻辑和规划中的种种问题常常可以表示为语言的识别问题。其它的计算问题往往都有对应的判定问题。这种问题只有两个可能的解,或者回答“是”,或者回答“否”。
11/15/2017
99 - 5
判定问题
定义7-1 判定问题是由实数集合D和“是”的实例子集YD组成。
但是,我们感兴趣的多数判定问题具有相当数量的附加结构,在描述判定问题时,要强调这些附加结构。我们用来规定问题的标准格式由两部分组成。第一部分用各种分量,如集合、图、函数、数字等规定该问题的一般实例。第二部分陈述根据这个一般实例提出的是-否问题。规定D和Y的方法是明显的,一个实例属于D当且仅当它可以通过用规定类型的具体对象替换一般实例中的所有分量得到,而这个实例属于Y当且仅当具体到这个实例时,对所陈述的问题的回答为“是”。
11/15/2017
99 - 6
货郎担问题
实例:一个有穷的“城市”集合C={c1,c2,…,cm},对于每一对城市ci,cj∈C有“距离”d(ci,cj)∈Z+,以及界限B∈Z+(这里Z+表示正整数集合)。
问:是否有经过C中所有城市的“旅行路线”,其全长不超过B,即是否有C的一个排列次序<c(1),c(2),…,c(m)>使得
11/15/2017
99 - 7
语言
我们只考虑判定问题的原因是因为它们有一个非常自然的、适合在数学上精确的计算理论中研究的形式对应物。这个对应物叫做“语言”,其定义如下:
定义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}上的语言。
11/15/2017
99 - 8
编码
判定问题的每一实例可以编码成一个符号串,这样就将判定问题重新描述为一个语言的