计算的复杂性第七章完全问题优秀课件.ppt

《计算的复杂性第七章完全问题优秀课件.ppt》由会员分享，可在线阅读，更多相关《计算的复杂性第七章完全问题优秀课件.ppt（99页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、计算的复杂性第七章完全问题计算的复杂性第七章完全问题第1页，本讲稿共99页99-22022/11/29第第7 7章章 NPNP完全问题完全问题 判定问题、语言和编判定问题、语言和编 码码 多项式变换与可满足多项式变换与可满足性问题性问题 非确定型图灵机非确定型图灵机 NP类类NP完全问题与完全问题与Cook定理定理强强NP完全问题完全问题Co-NP类问题类问题NP困难问题困难问题 空间复杂性简介空间复杂性简介 第2页，本讲稿共99页99-32022/11/29序序 对对一一个个已已确确定定是是可可计计算算的的问问题题，人人们们总总试试图图寻寻求求实实现现它它的的最最优优算算法法。然而对有些问题

2、，这个工作难度很大，目前还不能做到这点。然而对有些问题，这个工作难度很大，目前还不能做到这点。目目前前人人们们已已经经证证明明了了一一些些问问题题，它它们们的的时时间间复复杂杂性性是是多多项项式式阶阶的的，这这只只须须设设计计一一个个实实现现它它的的时时间间复复杂杂性性是是多多项项式式阶阶的的算算法法即即可可，例例如如分分类类（又又称称排排序序）问问题题。这这样样一一类类问问题题将将被被称称之之为为P P类类问问题题。还还有有一一类类问问题题，人人们们已已经经设设计计出出实实现现它它的的时时间间复复杂杂性性为为指指数数阶阶的的算算法法，并并且且已已证证明明该该问问题题不不存存在在多多项项式式阶

3、阶的的算算法法，例例如如梵梵塔塔问问题题；这这样样一一类类问问题题人人们们称称之之为为顽顽型型问问题题。但但是是有有这这样样一一类类问问题题，人人们们目目前前已已设设计计的的实实现现它它的的算算法法其其时时间间复复杂杂性性为为指指数数阶阶的的，但但还还不不能能肯肯定定它它有有或或没没有有多多项项式式阶阶的的算算法法，例例如如第第6 6章章讨讨论论的的当当m m2 2时时任任意意图图的的m m-可可着着色色问问题题。为为研研究究这这类类问问题题，人人们们又又设设计计一一种种称称为为非非确确定定图图灵灵机机的的计计算算模模型型，这这些些问问题题对对应应一一个个非非确确定定的的图图灵灵机机，而而且且

4、可可以以在在多多项项式式时时间间内内完完成成计计算算。人人们们称称这这类类问问题题为为N NP P问问题题，N NP P是是N No on nd de et te er rm mi in ni is st ti ic c P Po ol ly yn no om mi ia al l的的缩缩写，即非确定的多项式的意思。写，即非确定的多项式的意思。第3页，本讲稿共99页99-42022/11/29 1971年年 S.Cook发发 表表 了了“The Complexity of Theorem Proving Procedures”这这篇篇著著名名论论文文，1972年年R.Karp发发表表了了“Re

5、ducibilty Among Combinatorial Prob1ems”，从从此此奠奠定定了了NP完完全全理理论论的的基基础础。NP完完全全理理论论指指出出在在NP类类中中有有一一些些问问题题具具有有以以下下性性质质：若若其其中中一一个个问问题题获获得得多多项项式式算算法法，则则这这一一类类问问题题就就全全部部获获得得了了多多项项式式算算法法；反反之之，若若能能证证明明其其中中一一个个问问题题是是多多项项式式时时间间内内不不可可解解的的，则则这这-类类问问题题就就全全部部是是多多项项式式时时间间内内不不可可解解的的。这这类类问问题题将将称称之之为为NP完完全全问问题题。NP完完全全理理论

6、论不不打打算算找找出出这这一一类类问问题题的的算算法法，仅仅仅仅着着眼眼于于证证明明这这一一类类问问题题的的等等价性，即证明它们的难度相当。价性，即证明它们的难度相当。NP完完全全理理论论还还很很年年轻轻，有有许许多多问问题题等等待待人人们们研研究究。例例如如，“NPNPP P”还还是是相相反反“P P是是NPNP的的真真子子集集”。这这个个问问题题是是当当代代计计算算机机科科学学中中的的一一大难题。大难题。第4页，本讲稿共99页99-52022/11/297.1 7.1 判定问题、语言和编码判定问题、语言和编码 我我们们讨讨论论的的几几种种计计算算模模型型，都都可可以以认认为为是是语语言言的

7、的接接受受器或函数的计算器。器或函数的计算器。为为讨讨论论问问题题简简明明，本本章章只只讨讨论论语语言言的的识识别别问问题题。这这是是因因为为象象图图论论、数数论论、逻逻辑辑和和规规划划中中的的种种种种问问题题常常常常可可以以表表示示为为语语言言的的识识别别问问题题。其其它它的的计计算算问问题题往往往往都都有有对对应应的的判判定定问问题题。这这种种问问题题只只有有两两个个可可能能的的解解，或或者者回回答答“是是”，或者回答，或者回答“否否”。第5页，本讲稿共99页99-62022/11/29判定问题判定问题 定定义义7-17-1 判判定定问问题题 是是由由实实数数集集合合D D 和和“是是”的

8、的实实例例子子集集Y Y D D 组成。组成。但但是是，我我们们感感兴兴趣趣的的多多数数判判定定问问题题具具有有相相当当数数量量的的附附加加结结构构，在在描描述述判判定定问问题题时时，要要强强调调这这些些附附加加结结构构。我我们们用用来来规规定定问问题题的的标标准准格格式式由由两两部部分分组组成成。第第一一部部分分用用各各种种分分量量，如如集集合合、图图、函函数数、数数字字等等规规定定该该问问题题的的一一般般实实例例。第第二二部部分分陈陈述述根根据据这这个个一一般般实实例例提提出出的的是是-否否问问题题。规规定定D D 和和Y Y 的的方方法法是是明明显显的的，一一个个实实例例属属于于D D

9、当当且且仅仅当当它它可可以以通通过过用用规规定定类类型型的的具具体体对对象象替替换换一一般般实实例例中中的的所所有有分分量量得得到到，而而这这个个实实例例属属于于Y Y 当当且且仅仅当当具具体体到到这这个个实实例例时时，对对所所陈陈述述的的问问题题的的回回答为答为“是是”。第6页，本讲稿共99页99-72022/11/29货郎担问题货郎担问题 实实例例：一一个个有有穷穷的的“城城市市”集集合合C=C=c c1 1,c,c2 2,c,cm m，对对于于每每一一对对城城市市c ci i,c,cj jCC有有“距距离离”d(cd(ci i,c,cj j)Z)Z+，以以及及界界限限BZBZ+（这这里里

10、Z Z+表示正整数集合）。表示正整数集合）。问问：是是否否有有经经过过C C中中所所有有城城市市的的“旅旅行行路路线线”，其其全全长长不不超超过过B B，即是否有，即是否有C C的一个排列次序的一个排列次序c 使得使得第7页，本讲稿共99页99-82022/11/29语言语言 我我们们只只考考虑虑判判定定问问题题的的原原因因是是因因为为它它们们有有一一个个非非常常自自然然的的、适适合合在在数数学学上上精精确确的的计计算算理理论论中中研研究究的的形形式式对对应应物物。这这个个对对应应物物叫叫做做“语言语言”，其定义如下：，其定义如下：定定义义7-27-2 对对于于任任意意有有穷穷符符号号集集合合

11、，我我们们用用*表表示示所所有有 的的有有穷穷字字符符串串组组成成的的集集合合。如如果果L L是是*的的一一个个子子集集，我我们们称称L L是是字字母母表表 上的上的语言语言。例例如如，如如果果=0,10,1，那那么么*由由空空字字符符串串“”，字字符符串串0 0、1 1、0000、0101、1010、1111、000000、001001以以及及所所有有其其它它0 0和和1 1的的有有穷穷字字符符串串组组成成。于于是是01,001,111,110101001,001,111,1101010是是0,10,1上上的的一一个个语语言言，由由所所有有完完全全平平方方数数的的二二进进制制表表示示组组成成

12、的的集集合合以以及及集集合合0,10,1*本本身身也也都都是是0,10,1上的语言。上的语言。第8页，本讲稿共99页99-92022/11/29编码编码 判判定定问问题题的的每每一一实实例例可可以以编编码码成成一一个个符符号号串串，这这样样就就将将判判定定问问题题重重新新描描述述为为一一个个语语言言的的识识别别问问题题。这这个个语语言言必必须须由由对对应的判定问题中回答应的判定问题中回答“是是”的一切实例编码的串组成。的一切实例编码的串组成。在在选选择择编编码码方方法法时时，必必须须慎慎重重，因因为为一一个个问问题题的的复复杂杂性性可可能能与与编编码码的的方方法法有有关关。由由于于问问题题的的

13、难难度度在在本本质质上上不不依依赖赖于于用用来来决决定定时时间间复复杂杂性性的的具具体体编编码码方方法法和和计计算算机机模模型型，因因此此很很难难想想象象一一个个“合理的合理的”编码方法与标准的编码方法之间的差异超过多项式。编码方法与标准的编码方法之间的差异超过多项式。第9页，本讲稿共99页99-102022/11/29编码的条件编码的条件l实实例例I I的的编编码码必必须须是是简简洁洁的的，不不能能“填填塞塞”不不必必要要的信息或符号；的信息或符号；lI I中中出出现现的的数数字字必必须须用用十十进进制制（或或二二进进制制、八八进进制制、以及以任何不等于以及以任何不等于1 1的数为基的进制）

14、表示。的数为基的进制）表示。虽然不可能把我们在这里用虽然不可能把我们在这里用“合理的合理的”这个词表示的含义形式化，这个词表示的含义形式化，但是下述两个条件抓住了这个概念的主要内容：但是下述两个条件抓住了这个概念的主要内容：第10页，本讲稿共99页99-112022/11/29编码的标准编码的标准 如如果果我我们们规规定定只只使使用用满满足足这这些些条条件件的的编编码码方方法法，那那么么具具体体使使用用什什么么编编码码方方法法将将不不会会影影响响关关于于一一个个给给定定问问题题的的难难度度的的判判断断。为为此此，我我们们对问题的标准表示约定如下：对问题的标准表示约定如下：l整数用十进制表示；整

15、数用十进制表示；l用用十十进进制制数数1,2,.,n1,2,.,n表表示示一一个个图图的的n n个个节节点点，用用(i(i1 1,i,i2 2)表表示示图图中中的的边边，其中其中i i1 1,i,i2 2分别是该边的两个端点；分别是该边的两个端点；l具具有有n n个个命命题题变变元元的的布布尔尔表表达达式式由由*（与与），+（或或），（非非）与与整整数数1,2,.,n1,2,.,n（命命题题变变元元）所所组组成成的的字字符符串串表表示示，其其中中*可可以以省省略略（但但不不引引起起混混淆淆），必必要要时时可可以以加加括括号号。例例如如，布布尔尔表表达达式式(P(P1 1+P+P2 2)*P)*

16、P3 3可可以以写写成：成：(1+2)3(1+2)3。第11页，本讲稿共99页99-122022/11/29 当当把把整整数数及及其其它它符符号号都都采采用用二二进进制制编编码码后后，一一个个问问题题的的判判定定过程就可以形式地描述如下：过程就可以形式地描述如下：已已知知 L L 00，11*，对对于于x0 x0，11*，若若xLxL则则回回答答“是是”；若；若x x L L，则回答，则回答“非非”。这里，这里，00，11*是指由有限个是指由有限个0 0和和1 1组成的串的集合。组成的串的集合。再次重申，再次重申，我们的讨论仅限于语言的识别我们的讨论仅限于语言的识别。第12页，本讲稿共99页9

17、9-132022/11/297.2 7.2 多项式变换与可满足性问题多项式变换与可满足性问题 定定义义7-37-3 P P LL0,10,1*|L|L为为确确定定图图灵灵机机在在多多项项式式时时间间内内所所接受接受。该怎义中符号该怎义中符号“”意义为意义为“定义为定义为”。定定义义7-47-4 f|f:0f|f:0，11*00，11*且且f f可可在在多多项项式式时时间间内内完成完成。这这个个定定义义是是说说，表表示示可可在在多多项项式式时时间间内内完完成成00，11*00，11*这一转换的集合。这一转换的集合。第13页，本讲稿共99页99-142022/11/29多项式变换多项式变换 定义定

18、义7-57-5 若若A A00，11*，B B00，11*且存在且存在f f使得使得x xA A f(x)f(x)B B成成立立，则则称称A A可可多多项项式式变变换换于于B B，记记作作 ，或或简简称称A A变变换换为为B B。符号符号 的的意意思思是是：存存在在一一台台确确定定图图灵灵机机M M，它它将将可可以以A A在多项式时间内转换为在多项式时间内转换为B B。第14页，本讲稿共99页99-152022/11/29引理引理7-17-1引理引理7-17-1 若若 ，B BP P，则，则A AP P。证明：证明：x xA A f(x)f(x)B B f f，所所以以由由f f产产生生的的输

19、输出出也也必必有有多多项项式式界界，设设为为多多项项式式g g。但但B B也也有有多多项项式式界，设为界，设为h h。对于输入。对于输入x x，先作用以，先作用以f f，接着解属于，接着解属于B B的问题，总共所需时间：的问题，总共所需时间：g(|x|)+h(g(|x|)g(|x|)+h(g(|x|)显然也是多项式，所以显然也是多项式，所以A AP P，这个过程可以用下图表示：，这个过程可以用下图表示：问题问题A A的输的输入入x x问题问题B B的输入的输入最长为最长为(g(|x|)(g(|x|)f f转换至多在转换至多在g(|x|)g(|x|)内将内将x x换成换成f(x)f(x)多项式多

20、项式h(g(|x|)h(g(|x|)内内求解求解B B输出问题输出问题B B的解的解第15页，本讲稿共99页99-162022/11/29可满足性问题可满足性问题 实实例例：集集合合L=AL=A，B B，.，A A，B B，.，c c1 1，c c2 2，.，c ck k是是L L的的有有限限子子集集，称称为为子子句句。每每个个c ci i中中不不出出现现L L中中的的互互补补对对（即（即x xc cI I则则x x c ci i），），i=1i=1，2 2，.，k k。问：问：是否存在一集合是否存在一集合S SL L，满足以下两个条件：，满足以下两个条件：1.1.s s中不包含互补对；中不包

21、含互补对；2.2.。第16页，本讲稿共99页99-172022/11/29 从从数数理理逻逻辑辑看看来来，设设U=uU=u1 1,u,u2 2,u,um m 是是一一个个布布尔尔变变量量集集合合。关关于于U U的的真真值值赋赋值值是是一一个个函函数数t t：UT,FUT,F。如如果果t(u)=Tt(u)=T，我我们们称称u u在在t t下下取取“真真值值”；如如果果t(u)=Ft(u)=F，我我们们称称u u取取“假假值值”。如如果果u u是是U U中中的的一一个个变变量量，那那么么u u和和u u是是U U上上的的文文字字。文文字字u u在在t t下下取取真真值值当当且且仅仅当当变变量量u

22、u在在t t下下取取真真值值；文文字字u u取取真真值值当当且且仅仅当变量当变量u u取假值。取假值。U U上的上的子句子句是是U U上的一个文字集合，例如，上的一个文字集合，例如，u u1 1u u2 2 u u8 8。它表示这些文字。它表示这些文字的析取，对于的析取，对于U U上的一个真值赋值，这个真值赋值上的一个真值赋值，这个真值赋值满足满足它当且仅当它至少有一个它当且仅当它至少有一个元素在这个赋值下取真值。除去元素在这个赋值下取真值。除去t(ut(u1 1)=F)=F，t(ut(u2 2)=T)=T和和t(ut(u8 8)=F)=F之外，之外，t t满足上面那满足上面那个子句。个子句。

23、U U上的上的子句类子句类C C是可满足的是可满足的当且仅当当且仅当存在关于存在关于U U的一个真值赋值同时满足的一个真值赋值同时满足C C中所有子句中所有子句。我们称这样一个真值赋值是。我们称这样一个真值赋值是满足满足C C的真值赋值的真值赋值。第17页，本讲稿共99页99-182022/11/29命题逻辑的可满足性问题命题逻辑的可满足性问题 实例实例：布尔变量集合布尔变量集合U以及以及U上的子句类上的子句类C。问：问：是否存在满足是否存在满足C的真值赋值？的真值赋值？例例如如，U=uU=u1 1,u,u2 2 和和C=uC=u1 1u u2 2，u u1 1u u2 2 是是SATSAT的

24、的一一个个实实例例，对对这这个个实实例例的的回回答答为为“是是”，t(ut(u1 1)=t(u)=t(u2 2)=T)=T给给出出一一个个满满足足的的真真值值赋赋值值。如如果果用用CCuu1 1u u2 2，u u1 1u u2 2,u u1 1 代代替替C C也也给给出出一一个实例，对这个实例的回答为个实例，对这个实例的回答为“否否”，CC不是可满足的。不是可满足的。可满足性问题常用符号可满足性问题常用符号SATSAT表示，它是表示，它是SatisfiabilitySatisfiability的缩写。的缩写。第18页，本讲稿共99页99-192022/11/29图的图的m-m-可着色问题可着

25、色问题 实实例例：无无向向连连通通图图G-(V,E)和和m种种不不同同的的颜颜色色，用用这这些些颜颜色色为为G的各节点着色，每个节点着一色。的各节点着色，每个节点着一色。问问：是是否否有有使使得得G中中任任何何一一条条边边的的两两个个节节点点的的颜颜色色不不同同的的着着色法。色法。例例7-17-1 图的图的m-可着色问题可以多项式变换为可着色问题可以多项式变换为SAT。证证明明：已已知知图图G的的节节点点数数为为n，c1，c2，.，cm表表示示m种种颜颜色色，设设第19页，本讲稿共99页99-202022/11/29 因因此此，G G的的每每一一种种着着色色方方案案对对应应于于给给mnmn个个

26、变变量量PPijij 的的一一种种赋值。但是必须满足条件：赋值。但是必须满足条件：(1)(1)每每个个节节点点至至少少有有一一种种颜颜色色，故故对对任任一一i i，有有子子句句P Pi1i1PPi2i2.P.Pimim；(2)(2)相相邻邻的的节节点点着着不不同同颜颜色色，故故对对图图G G的的任任意意一一对对相相邻邻节节点点(r,s)(r,s)，必有，必有P PrjrjP Psjsj，1jm1jm。于于是是图图G G可可m-m-着着色色的的充充要要条条件件是是可可对对变变量量P Pijij赋赋值值i=1,2,.,ni=1,2,.,n，j=1,2,.,mj=1,2,.,m，使得由，使得由(1)

27、(1)和和(2)(2)构成的所有子句取值为构成的所有子句取值为T T。转换步骤转换步骤(1)(1)，(2)(2)所需的时间有多项式的界。所需的时间有多项式的界。第20页，本讲稿共99页99-212022/11/29哈密顿回路问题（哈密顿回路问题（HCHC）实例：实例：图图G=(V,E)G=(V,E)。问问：G G是是否否包包含含一一条条哈哈密密顿顿回回路路，即即是是否否有有G G的的节节点点排排列列次次序序v 使使得得(v(vn n,v,v1 1)E)E和和(v(vI I,v,vi+1i+1)E)E，1i1in n？这这里里n=|V|n=|V|。例例7-27-2 哈哈密密顿顿回回路路问问题题（

28、HCHC）可可以以多多项项式式变变换换为为货货郎郎担担问问题题（TSTS）。）。证证明明：函函数数f f的的定定义义十十分分简简单单。设设G=G=为为给给定定的的HCHC的的实实例例，|V|=n|V|=n。对对应应的的TSTS的的实实例例有有一一个个等等于于V V的的城城市市集集合合C C，对对任任意意两两个个城城市市i,ji,j，若若(i,j)E(i,j)E，则则规规定定d(i,j)=1d(i,j)=1，否否则则d(i,j)=2d(i,j)=2。令界限令界限B=|V|B=|V|。第21页，本讲稿共99页99-222022/11/29 容容易易（非非形形式式地地）看看到到，能能够够用用一一个个

29、多多项项式式时时间间算算法法计计算算这这个个函函数数f f。对对于于 个个规规定定的的耗耗费费d(i,j)d(i,j)，只只需需要要检检查查(i,j)(i,j)是是否否是是G G中中的的一条边，所以一条边，所以ff。假假设设(1,2,.,n)(1,2,.,n)是是G G中中的的一一条条哈哈密密顿顿回回路路，那那么么(1,2(1,2，.,n).,n)也也是是f(G)f(G)中中的的一一条条周周游游路路线线，并并且且这这条条周周游游路路线线的的耗耗费费为为B=nB=n，这这是是因因为为在在这这条条周周游游路路线线中中经经过过的的城城市市之之间间每每一一段段耗耗费费对对应应G G中中一一条条边边，从

30、从而而耗耗费费为为1 1。反反之之，假假设设(1,2,.,n)(1,2,.,n)是是f(G)f(G)中中的的一一条条总总耗耗费费为为不不超超过过B B的的周周游游路路线线。因因为为任任意意两两个个城城市市之之间间的的耗耗费费不不是是1 1就就是是2 2，而而在在计计算算周周游游路路线线的的总总耗耗费费时时恰恰好好是是n n个个这这样样的的耗耗费费相相加加，所所以以根根据据B=nB=n，每每一一对对相相继继访访问问的的城城市市间间的的耗耗费费恰恰好好为为1 1。由由的的f(G)f(G)定定义义，得得到到(i,i+1),1i(i,i+1),1in n和和(n,1)(n,1)都是都是G G的边，从而

31、的边，从而(1,2,.,n)(1,2,.,n)是是G G的一条哈密顿回路。的一条哈密顿回路。第22页，本讲稿共99页99-232022/11/29引理引理7-2若L1 L2，L2 L3，则L1 L3。第23页，本讲稿共99页99-242022/11/297.3 7.3 非确定型图灵机非确定型图灵机 为为讨讨论论NPNP问问题题，再再引引进进一一种种虚虚设设的的计计算算模模型型，即即非非确确定定型型图图灵灵机。机。定定义义7-67-6 一一个个k-k-带带非非确确定定型型图图灵灵机机（NDTMNDTM）M M可可由由下下述述7 7元组确定：元组确定：M=QM=其其中中Q Q，T T，I I，b

32、b，q q0 0和和q qr r的的定定义义与与确确定定型型图图灵灵机机相相同同（参参看第看第5 5章定义章定义5-35-3），而），而是：是：QTQTk kA|AA|AQ(TLQ(TL，R R，S)S)k k。第24页，本讲稿共99页99-252022/11/29 定定义义指指出出，非非确确定定型型图图灵灵机机，对对于于由由一一个个状状态态与与k k个个磁磁带带符符号号所所给给定定的的序序组组，确确定定的的下下一一动动作作不不是是唯唯一一确确定定的的，它它将将要要在在一一个个有有穷穷集集合合A A中中选选择择（猜猜测测），它它在在同同一一时时刻刻里里可可以以做做多多种种运运算算。但但要要注注

33、意意，一一个个NDTMNDTM机机M M只只能能在在A A中中任任意意选选择择其其下下一一个个动动作，然而不能选作，然而不能选A A以外的动作。以外的动作。假假定定(q,(a(q,(a1 1,d,d1 1),(a),(a2 2,d,d2 2),.,(a),.,(ak k,d,dk k)(q,a)(q,a1 1,a,a2 2,.,a,.,ak k)，并并且且非非确确定定型型图图灵灵机机M M正正处处在在状状态态q q，且且第第i i个个磁磁头头（1ik1ik）正正扫扫描描着着第第i i条条磁磁带带上上符符号号a ai i的的某某一一方方格格，则则机机器器的的下下一一动动作作可可以进入状态以进入状

34、态qq，并把，并把a ai i变为变为aai i，而各磁头的动作由，而各磁头的动作由ddi i指定。指定。第25页，本讲稿共99页99-262022/11/29图灵机的格局图灵机的格局 定定义义7-77-7 称称D=aD=为为k-k-带带图图灵灵机机的的一一个个格格局局，若若每每一一个个a ai i形形为为xqyxqy，其其中中xyxy是是在在当当前前状状态态q q下下第第i i条条带带上上的的符符号号串串（不不计计右右端端的的空空白白符符），q q为为机机M M的的当当前前状状态态，q q后后面面的的第第一一个个符符号号是是M M在第在第i i条带的带头所扫描的方格符号。条带的带头所扫描的方

35、格符号。若若机机M M是是确确定定型型的的且且当当前前格格局局D D不不处处于于停停机机状状态态，则则可可由由下下一一动动作作函函数数唯一地确定下一个格局唯一地确定下一个格局DD，并记为，并记为DDM MDD，称为，称为D D转到转到DD。对对于于非非确确定定型型机机M M，从从当当前前格格局局D D可可导导致致多多于于一一个个的的下下一一格格局局（但但仅仅有有穷穷个个），若若DD是是其其中中之之一一，则则记记为为DDM MDD（或或DDDD，若不引起混乱）。，若不引起混乱）。若若对对某某个个k k1 1，有有c c1 1cc2 2cck k或或c cl l=c=ck k，则则可可记记作作c

36、c1 1*c ck k。第26页，本讲稿共99页99-272022/11/29非确定型图灵机的作用非确定型图灵机的作用 非非确确定定型型图图灵灵机机M M可可以以用用作作一一种种语语言言L L的的识识别别器器。对对于于语语言言L L，我我们们可可以以构构造造一一台台非非确确定定型型图图灵灵机机M M，让让机机器器的的带带符符包包括括该该语语言言的的字字母母表表（输输入入字字母母表表）以以及及伪伪空空白白符符b b和和其其它它一一些些特特定定符符号号（辅辅助助符符号号）。机机器器处处于于开开始始状状态态时时，将将输输入入w w打打印印在在第第一一条条磁磁带带的的最最左左面面部部分分上上，此此外外

37、全全为为空空白白，而而其其它它的的磁磁带带此此时时全全为为空空白白；把把各各条条磁磁带带的的磁磁头头放放在在该该磁磁带带之之最最左左一一格格上上。称称输输入入w w被被这这台台机机器器接受，仅当：接受，仅当：q*其中其中a a1 1（因此一切（因此一切a a2 2,.,a,.,ak k）有停机状态）有停机状态q qr r于其中。于其中。第27页，本讲稿共99页99-282022/11/29 定定义义7-87-8 对对语语言言L L，按按上上述述方方法法构构成成的的非非确确定定型型图图灵灵机机NDTMNDTM接接受受L L，当当且且仅仅当当对对wLwL，NDTMNDTM可可接接受受w w，对对w

38、 w L L，NDTMNDTM陷陷入入不不停停机机状状态态。非非确确定定型型图图灵灵机机NDTM接受语言接受语言L，记作，记作L(NDTM)L(NDTM)。非确定型图灵机非确定型图灵机NDTM接受语言接受语言L 第28页，本讲稿共99页99-292022/11/29例例7-3 7-3 等分划问题等分划问题试设计一台NDTM，它接受了形如：的的字字，其其中中i i1 1，i i2 2，.，i ik k为为非非负负整整数数满满足足下下述述要要求求：有有I I1,2,.,k1,2,.,k使使 换言之，字w被接受当且仅当用字w所表现的数列i1，i2，.，ik，可以被分割为两个子序列，各子序列的数之和相

39、等。这个问题是所谓等分划问题，已经知道，它是一个NP完全问题。第29页，本讲稿共99页99-302022/11/29 下下面面设设计计一一台台三三带带N ND DT TM M来来接接受受所所述述的的语语言言。这这台台N ND DT TM M的的工工作作情情况况是是：对对输输入入磁磁带带从从左左到到右右进进行行扫扫描描，每每次次搜搜索索全全为为0 0的的一一个个磁磁带带段段0 0i ij j，并并且且不不确确定定地地在在第第2 2或或第第3 3磁磁带带上上增增补补选选i ij j个个0 0；当当扫扫描描到到输输入入末末端端时时，机机器器便便核核对对第第2 2磁磁带带与与第第3 3磁磁带带上上0

40、0的的个个数数，若若相相等等则则接接受受（注注意意，可可能能有有许许多多情情况况导导向向了了不不相相等等，但但我我们们关关心心的的是是：有有 一一 种种 选选 择择 导导 致致 相相 等等）。设设N N D D T T M M=，下一动作函数，下一动作函数如表如表7-17-1所示。所示。下下面面给给该该机机器器输输入入10100101010010，我我们们从从许许多多可可能能选选择择的的计计算算中中，列列出出两两个个可可能能的的计计算算，其其中中的的第第一一个个导导向向了了对对该该输输入入是是接接受受的的，而而第第二二个个计计算算不不接接受受该该输输入入。因因此此，按按我我们们的的定定义义，该

41、该机机器器接接受受10100101010010。第30页，本讲稿共99页99-312022/11/29表表7-1 7-1 例例7-37-3中非确定型图灵机中非确定型图灵机M M的下移函数的下移函数 当前状态 当前带符 新带符及带头移动 新状态 说 明 带1 带2 带3 带1 带2 带3 q0 1 bb1,S$,R$,R q1 第1磁带不变，2、3磁带之左端打印上$，进入状态q1 q11bb1,R1,Rb,Sb,Sb,Sb,Sq2q3 在此开始选择：是把下一段0记在带2(q2)上呢？还是记在带3(q3)上？q201b bbbbbb0,R1,Sb,S 0,Rb,Sb,L b,Sb,Sb,L q2q

42、1q4 把所扫描的一段0复制到带2上，且当带1已扫描到1时便回到q1；若在带1上扫描到b，则去进行2、3带上0的个数的比较 q3 01bbbbbbb0,R1,Sb,Sb,Sb,Sb,L0,Rb,Sb,Lq3q1q4 与q2中在带2上的动作相似，但这次是在带3上进行 q4 bb0$0$b,Sb,S0,L$,S0,L$,Sq4q5 比较带2与带3上0的个数 q5 接受 第31页，本讲稿共99页99-322022/11/29q q 1q 10q 10q 101q 1010q 10100q 10100q 101001q 1010010q 1010010q01010010q001010010q$0010

43、10010q$00接受。接受。q q 1q 10q10q 101q 1010q 10100q 10100q 101001q 1010010q 1010010q0停止，因无下一格局。停止，因无下一格局。第32页，本讲稿共99页99-332022/11/29NDTMNDTM的时空复杂性的时空复杂性 定定义义7-97-9 称称一一台台NDTM机机M的的时时间间复复杂杂性性是是T(n)，假假若若对对于于任任何何长长为为n的的可可接接受受的的输输入入w，都都存存在在着着一一条条导导向向接接受受指指令令的的计计算算路路，该该计计算算路路至至多多有有T(n)步步。称称M的的空空间间复复杂杂性性是是S(n)，

44、假假若若对对于于上上述述输输入入w，有有一一条条导导向向接接受受指指令令的的计计算算路路，于于其其中中在每一条带上至多有在每一条带上至多有S(n)个相异的磁带方格被扫描过。个相异的磁带方格被扫描过。第33页，本讲稿共99页99-342022/11/29例例7-37-3的复杂性的复杂性 例7-4 对于例7-3所设计的机器M，其时间复杂性为2n+2，而空间复杂性为n+1。对所述的空间复杂性是显然的，为了看出时间复杂性为2n+2，只须注意：当对输入扫描结束（共用n+1步）后，要回头对2、3磁带进行比较（不超过n+1步）。第34页，本讲稿共99页99-352022/11/29用用DTM模拟模拟NDTM

45、 原原则则上上，对对于于每每一一台台NDTMNDTM机机，都都可可以以设设计计一一台台DTMDTM机机来来模模拟拟它它，使使得得两两者者皆皆接接受受了了同同一一语语言言。然然而而DTMDTM的的时时间间耗耗费费要要大大得得多多，可可以以证证明明，这这种种模模拟拟的的时时间间耗耗费费下下界界是是指指数数型型的的。确确切切地地说说，设设T(n)T(n)是是“时时间间可可构构造造的的”函函数数（即即存存在在一一台台DTMDTM机机，给给出出该该机机的的任任一一输输入入n n，机机器器将将在在第第T(n)T(n)步步停停机机），则则对对每每一一台台为为T(n)T(n)时时间间囿囿界界的的NDTMNDT

46、M机机M M，可可以以找找到到一一个个常常数数c cl l和一台和一台DTMDTM机机MM使使L(M)=L(M)L(M)=L(M)且且MM的时间复杂性为的时间复杂性为O(cO(cT(n)T(n)。为为了了证证明明这这个个结结果果，可可以以用用穷穷举举算算法法来来构构造造一一台台模模拟拟M M的的DTMDTM机机MM。首首先先，可以找到常数可以找到常数d d，使得，使得NDTMNDTM机机M M在任何情况下的下一动作在任何情况下的下一动作第35页，本讲稿共99页99-362022/11/29的的选选择择可可能能不不超超过过d d个个。因因此此机机器器M M的的长长度度不不超超过过T(n)T(n)

47、的的任任何何一一条条计计算算路路都都可可用用字字母母表表=0=0，1 1，.，d dn-1n-1 的的长长不不超超过过T(n)T(n)的的一一个个字字来来表表现现，这这些些字字至至多多为为(d+1)(d+1)T(n)T(n)个个。事事实实上上，只只有有d dT(n)T(n)个个可可将将其其按按字字母母次次序序排排列列。对对于于长长为为n n的的输输入入x x，DTMDTM机机MM模模拟拟NDTMNDTM如如下下，依依次次模模拟拟上上述述ww*为为w w，（即即MM在在这这次次模模拟拟中中的的计计算算路路），如如M M中中不不存存在在如如w w所所示示的的计计算算路路或或者者w w不不是是M M

48、接接受受x x的的计计算算路路，则则MM去去模模拟拟w w的的下下一一个个次次序序的的字字母母所所示示的的计计算算路路。注注意意，MM在在每每次次模模拟拟时时要要耗耗时时O(T(n)O(T(n)，于于是是整整个个模模拟拟至至多多耗耗费费时时间间O(T(n)(d+1)O(T(n)(d+1)T(n)T(n)（事事实实上上为为T(n)dT(n)dT(n)T(n)）取取c=2(d+1)c=2(d+1)即即可可。细细节节的的叙叙述述要要用用到到T(n)T(n)的的时时间间可可构构造造性性（因因模模拟拟w w到长为到长为T(n)T(n)止），这里就不再叙述了。这样我们就证了下述定理：止），这里就不再叙述了

49、。这样我们就证了下述定理：第36页，本讲稿共99页99-372022/11/29定理定理7-17-11.如如果果取取上上述述非非确确定定型型图图灵灵机机类类为为计计算算模模型型，则则这这个个计计算算模模型同已知的种种计算模型等价。型同已知的种种计算模型等价。2.对对于于任任一一台台NDTM时时间间囿囿界界为为T(n)且且T(n)为为时时间间可可构构造造的的机机器器M，都都可可以以找找到到常常数数c1和和DTM机机M使使L(M)=L(M)且且M的时间下限为的时间下限为O(cT(n)。然而，我们不知道有一个为然而，我们不知道有一个为NDTM在时间复杂性在时间复杂性T(n)里接受的语言里接受的语言L

50、，一切，一切DTM在时间复杂度在时间复杂度T(n)都不能接受都不能接受它。它。第37页，本讲稿共99页99-382022/11/29定理定理7-27-2 若若NDTMNDTM机机M M的的空空间间复复杂杂性性为为S(n)S(n)，且且S(n)S(n)使使空空间间可可构构造造的的，则则存存在在一一台台DTMDTM机机MM，它它的的空空间间复复杂杂性性是是O O(S(S3 3(n)(n)且且L(M)=L(M)L(M)=L(M)。所所谓谓一一个个函函数数S(n)是是空空间间可可构构造造的的，如如果果存存在在一一台台DTM机机M，当当给给它它一一个个长长度度为为n的的输输入入，M机机将将在在它它的的一