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

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

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

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的的 缩缩写，即非确定的多项式的意思。写，即非确定的多项式的

5、意思。现在学习的是第3页，共99页99-42023/2/27 1971年年S.Cook发发表表了了“The Complexity of Theorem Proving Procedures”这这篇篇著著名名论论文文，1972年年R.Karp发发表表了了“Reducibilty Among Combinatorial Prob1ems”，从从此此奠奠定定了了NP完完全全理理论论的的基基础础。NP完完全全理理论论指指出出在在NP类类中中有有一一些些问问题题具具有有以以下下性性质质：若若其其中中一一个个问问题题获获得得多多项项式式算算法法，则则这这一一类类问问题题就就全全部部获获得得了了多多项项式式

6、算算法法；反反之之，若若能能证证明明其其中中一一个个问问题题是是多多项项式式时时间间内内不不可可解解的的，则则这这-类类问问题题就就全全部部是是多多项项式式时时间间内内不不可可解解的的。这这类类问问题题将将称称之之为为NP完完全全问问题题。NP完完全全理理论论不不打打算算找找出出这这一一类类问问题题的的算算法法，仅仅仅仅着着眼于证明这一类问题的等价性，即证明它们的难度相当。眼于证明这一类问题的等价性，即证明它们的难度相当。NP完完全全理理论论还还很很年年轻轻，有有许许多多问问题题等等待待人人们们研研究究。例例如如，“NPNPP P”还还是相反是相反“P P是是NPNP的真子集的真子集”。这个问

7、题是当代计算机科学中的一大难题。这个问题是当代计算机科学中的一大难题。现在学习的是第4页，共99页99-52023/2/277.1 7.1 判定问题、语言和编码判定问题、语言和编码 我我们们讨讨论论的的几几种种计计算算模模型型，都都可可以以认认为为是是语语言言的的接接受受器或函数的计算器。器或函数的计算器。为为讨讨论论问问题题简简明明，本本章章只只讨讨论论语语言言的的识识别别问问题题。这这是是因因为为象象图图论论、数数论论、逻逻辑辑和和规规划划中中的的种种种种问问题题常常常常可可以以表表示示为为语语言言的的识识别别问问题题。其其它它的的计计算算问问题题往往往往都都有有对对应应的的判判定定问问题

8、题。这这种种问问题题只只有有两两个个可可能能的的解解，或或者者回回答答“是是”，或者回答或者回答“否否”。现在学习的是第5页，共99页99-62023/2/27判定问题判定问题 定义定义7-17-1 判定问题判定问题 是由是由实数集合实数集合D D 和和“是是”的实例子集的实例子集Y Y D D 组成。组成。但但是是，我我们们感感兴兴趣趣的的多多数数判判定定问问题题具具有有相相当当数数量量的的附附加加结结构构，在在描描述述判判定定问问题题时时，要要强强调调这这些些附附加加结结构构。我我们们用用来来规规定定问问题题的的标标准准格格式式由由两两部部分分组组成成。第第一一部部分分用用各各种种分分量量

9、，如如集集合合、图图、函函数数、数数字字等等规规定定该该问问题题的的一一般般实实例例。第第二二部部分分陈陈述述根根据据这这个个一一般般实实例例提提出出的的是是-否否问问题题。规规定定D D 和和Y Y 的的方方法法是是明明显显的的，一一个个实实例例属属于于D D 当当且且仅仅当当它它可可以以通通过过用用规规定定类类型型的的具具体体对对象象替替换换一一般般实实例例中中的的所所有有分分量量得得到到，而而这这个个实实例例属属于于Y Y 当当且且仅仅当当具具体体到到这这个个实实例例时时，对对所陈述的问题的回答为所陈述的问题的回答为“是是”。现在学习的是第6页，共99页99-72023/2/27货郎担问

10、题货郎担问题 实实例例：一一个个有有穷穷的的“城城市市”集集合合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+（这这里里Z Z+表表示示正正整整数数集合）。集合）。问问：是是否否有有经经过过C C中中所所有有城城市市的的“旅旅行行路路线线”，其其全全长长不不超超过过B B，即即是否有是否有C C的一个排列次序的一个排列次序c 使得使得现在学习的是第7页，共99页99-82023/2/27语言语言 我我们们只只考考虑虑判判定定问问题题的的原原因因是是

11、因因为为它它们们有有一一个个非非常常自自然然的的、适适合合在在数数学学上上精精确确的的计计算算理理论论中中研研究究的的形形式式对对应应物物。这这个个对对应应物物叫叫做做“语言语言”，其定义如下：，其定义如下：定定义义7-27-2 对对于于任任意意有有穷穷符符号号集集合合，我我们们用用*表表示示所所有有 的的有有穷穷字字符符串组成的集合。如果串组成的集合。如果L L是是*的一个子集，我们称的一个子集，我们称L L是字母表是字母表 上的上的语言语言。例例如如，如如果果=0,10,1，那那么么*由由空空字字符符串串“”，字字符符串串0 0、1 1、0000、0101、1010、1111、000000

12、、001001以以及及所所有有其其它它0 0和和1 1的的有有穷穷字字符符串串组组成成。于于是是01,001,111,110101001,001,111,1101010是是0,10,1上上的的一一个个语语言言，由由所所有有完完全全平平方方数数的的二二进进制表示组成的集合以及集合制表示组成的集合以及集合0,10,1*本身也都是本身也都是0,10,1上的语言。上的语言。现在学习的是第8页，共99页99-92023/2/27编码编码 判判定定问问题题的的每每一一实实例例可可以以编编码码成成一一个个符符号号串串，这这样样就就将将判判定定问问题题重重新新描描述述为为一一个个语语言言的的识识别别问问题题。

13、这这个个语语言言必必须须由由对对应应的判定问题中回答的判定问题中回答“是是”的一切实例编码的串组成。的一切实例编码的串组成。在在选选择择编编码码方方法法时时，必必须须慎慎重重，因因为为一一个个问问题题的的复复杂杂性性可可能能与与编编码码的的方方法法有有关关。由由于于问问题题的的难难度度在在本本质质上上不不依依赖赖于于用用来来决决定定时时间间复复杂杂性性的的具具体体编编码码方方法法和和计计算算机机模模型型，因因此此很很难难想想象象一一个个“合合理的理的”编码方法与标准的编码方法之间的差异超过多项式。编码方法与标准的编码方法之间的差异超过多项式。现在学习的是第9页，共99页99-102023/2/

14、27编码的条件编码的条件l实实例例I I的的编编码码必必须须是是简简洁洁的的，不不能能“填填塞塞”不不必必要要的的信息或符号；信息或符号；lI I中中出出现现的的数数字字必必须须用用十十进进制制（或或二二进进制制、八八进进制制、以及以任何不等于以及以任何不等于1 1的数为基的进制）表示。的数为基的进制）表示。虽然不可能把我们在这里用虽然不可能把我们在这里用“合理的合理的”这个词表示的含义形式这个词表示的含义形式化，但是下述两个条件抓住了这个概念的主要内容：化，但是下述两个条件抓住了这个概念的主要内容：现在学习的是第10页，共99页99-112023/2/27编码的标准编码的标准 如如果果我我们

15、们规规定定只只使使用用满满足足这这些些条条件件的的编编码码方方法法，那那么么具具体体使使用用什什么么编编码码方方法法将将不会影响关于一个给定问题的难度的判断。为此，我们对问题的标准表示约定如下：不会影响关于一个给定问题的难度的判断。为此，我们对问题的标准表示约定如下：l整数用十进制表示；整数用十进制表示；l用用十十进进制制数数1,2,.,n1,2,.,n表表示示一一个个图图的的n n个个节节点点，用用(i(i1 1,i,i2 2)表表示示图图中中的的边边，其中其中i i1 1,i,i2 2分别是该边的两个端点；分别是该边的两个端点；l具具有有n n个个命命题题变变元元的的布布尔尔表表达达式式由

16、由*（与与），+（或或），（非非）与与整整数数1,2,.,n1,2,.,n（命命题题变变元元）所所组组成成的的字字符符串串表表示示，其其中中*可可以以省省略略（但但不不引引起起混混淆淆），必必要要时时可可以以加加括括号号。例例如如，布布尔尔表表达达式式(P(P1 1+P+P2 2)*P)*P3 3可可以以写写成成：(1+2)3(1+2)3。现在学习的是第11页，共99页99-122023/2/27 当当把把整整数数及及其其它它符符号号都都采采用用二二进进制制编编码码后后，一一个个问问题题的的判判定定过程就可以形式地描述如下：过程就可以形式地描述如下：已已知知 L L 00，11*，对对于于x0

17、 x0，11*，若若xLxL则则回回答答“是是”；若；若x x L L，则回答，则回答“非非”。这里，这里，00，11*是指由有限个是指由有限个0 0和和1 1组成的串的集合。组成的串的集合。再次重申，再次重申，我们的讨论仅限于语言的识别我们的讨论仅限于语言的识别。现在学习的是第12页，共99页99-132023/2/277.2 7.2 多项式变换与可满足性问题多项式变换与可满足性问题 定定义义7-37-3 P P LL0,10,1*|L|L为为确确定定图图灵灵机机在在多多项项式式时时间间内内所接受所接受。该怎义中符号该怎义中符号“”意义为意义为“定义为定义为”。定定义义7-47-4 f|f:

18、0f|f:0，11*00，11*且且f f可可在在多多项项式式时时间间内内完成完成。这这个个定定义义是是说说，表表示示可可在在多多项项式式时时间间内内完完成成00，11*00，11*这一转换的集合。这一转换的集合。现在学习的是第13页，共99页99-142023/2/27多项式变换多项式变换 定义定义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

19、，它它将将可以可以A A在多项式时间内转换为在多项式时间内转换为B B。现在学习的是第14页，共99页99-152023/2/27引理引理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产产生生的的输输出出也也必必有有多多项项式式界界，设设为为多多项项式式g g。但但B B也也有有多多项项式式界界，设设为为h h。对对于于输输入入x x，先先作作用用以以f f，接接着着解解属属于于B B的的问问题题，总总共共所所需需时时间：间：g(|x|)+h(g(|x|)g(|x|)+h(g(|x|)显然

20、也是多项式，所以显然也是多项式，所以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)多项式多项式h(g(|x|)h(g(|x|)内内求解求解B B输出问题输出问题B B的解的解现在学习的是第15页，共99页99-162023/2/27可满足性问题可满足性问题 实实例例：集集合合L=AL=A，B B，.，A A，B B，.，c c1 1，c c2 2，.，c ck k是是L L的的有有限限子子集集

21、，称称为为子子句句。每每个个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中不包含互补对；中不包含互补对；2.2.。现在学习的是第16页，共99页99-172023/2/27 从从数数理理逻逻辑辑看看来来，设设U=uU=u1 1,u,u2 2,u,um m 是是一一个个布布尔尔变变量量集集合合。关关于于U U的的真真值值赋赋值值是是一一个个函函数数t t：UT,FUT,F。如如果果t(u)=Tt

22、(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 u在在t t下下取取真真值值；文文字字u u取取真值当且仅当变量真值当且仅当变量u u取假值。取假值。U U上的上的子句子句是是U U上的一个文字集合，例如，上的一个文字集合，例如，u u1 1u u2 2 u u8 8。它表示这些文。它表示这些文字的析取，对于字的析取，对于U U上的一个真值赋值

23、，这个真值赋值上的一个真值赋值，这个真值赋值满足满足它当且仅当它至少有一它当且仅当它至少有一个元素在这个赋值下取真值。除去个元素在这个赋值下取真值。除去t(ut(u1 1)=F)=F，t(ut(u2 2)=T)=T和和t(ut(u8 8)=F)=F之外，之外，t t满足满足上面那个子句。上面那个子句。U U上的上的子句类子句类C C是可满足的是可满足的当且仅当当且仅当存在关于存在关于U U的一个真值赋的一个真值赋值同时满足值同时满足C C中所有子句中所有子句。我们称这样一个真值赋值是。我们称这样一个真值赋值是满足满足C C的真值赋值的真值赋值。现在学习的是第17页，共99页99-182023/

24、2/27命题逻辑的可满足性问题命题逻辑的可满足性问题 实例实例：布尔变量集合布尔变量集合U以及以及U上的子句类上的子句类C。问：问：是否存在满足是否存在满足C的真值赋值？的真值赋值？例例如如，U=uU=u1 1,u,u2 2 和和C=uC=u1 1u u2 2，u u1 1u u2 2 是是SATSAT的的一一个个实实例例，对对这这个个实实例例的的回回答答为为“是是”，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也也给给出出一一个个实实例，对这

25、个实例的回答为例，对这个实例的回答为“否否”，CC不是可满足的。不是可满足的。可满足性问题常用符号可满足性问题常用符号SATSAT表示，它是表示，它是SatisfiabilitySatisfiability的缩写。的缩写。现在学习的是第18页，共99页99-192023/2/27图的图的m-m-可着色问题可着色问题 实实例例：无无向向连连通通图图G-(V,E)和和m种种不不同同的的颜颜色色，用用这这些些颜颜色色为为G的各节点着色，每个节点着一色。的各节点着色，每个节点着一色。问问：是是否否有有使使得得G中中任任何何一一条条边边的的两两个个节节点点的的颜颜色色不不同同的的着色法。着色法。例例7-

26、17-1 图的图的m-可着色问题可以多项式变换为可着色问题可以多项式变换为SAT。证证明明：已已知知图图G的的节节点点数数为为n，c1，c2，.，cm表表示示m种种颜颜色色，设设现在学习的是第19页，共99页99-202023/2/27 因因此此，G G的的每每一一种种着着色色方方案案对对应应于于给给mnmn个个变变量量PPijij 的的一一种种赋值。但是必须满足条件：赋值。但是必须满足条件：(1)(1)每每个个节节点点至至少少有有一一种种颜颜色色，故故对对任任一一i i，有有子子句句P Pi1i1PPi2i2.P.Pimim；(2)(2)相相邻邻的的节节点点着着不不同同颜颜色色，故故对对图图

27、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)(1)和和(2)(2)构构成成的的所所有有子子句句取取值为值为T T。转换步骤转换步骤(1)(1)，(2)(2)所需的时间有多项式的界。所需的时间有多项式的界。现在学习的是第20页，共99页99-212023/2/27哈密顿回路问题（哈密顿回路问题（HCHC）

28、实例：实例：图图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，1i1i n n？这这 里里n=|V|n=|V|。例例7-27-2 哈哈密密顿顿回回路路问问题题（HCHC）可可以以多多项项式式变变换换为为货货郎郎担担问问题题（TSTS）。）。证证明明：函函数数f f的的定定义义十十分分简简单单。设设G=G=为为给给定定的的HCHC的的实实例例，|V|=n|V|=n。对对应应的的TSTS的的实实例例有有一一个个

29、等等于于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-222023/2/27 容容易易（非非形形式式地地）看看到到，能能够够用用一一个个多多项项式式时时间间算算法法计计算算这这个个函函数数f f。对对于于 个个规规定定的的耗耗费费d(i,j)d(i,j)，只只需需要要检检查查(i,j)(i,j)是是否否是是G G中中的一条边，所以的一条边，所以ff。假假设设(1,2,.,n)(1

30、,2,.,n)是是G G中中的的一一条条哈哈密密顿顿回回路路，那那么么(1,2(1,2，.,n).,n)也也是是f(G)f(G)中中的的一一条条周周游游路路线线，并并且且这这条条周周游游路路线线的的耗耗费费为为B=nB=n，这这是是因因为为在在这这条条周周游游路路线线中中经经过过的的城城市市之之间间每每一一段段耗耗费费对对应应G G中中一一条条边边，从从而而耗耗费费为为1 1。反反之之，假假设设(1,2,.,n)(1,2,.,n)是是f(G)f(G)中中的的一一条条总总耗耗费费为为不不超超过过B B的的周周游游路路线线。因因为为任任意意两两个个城城市市之之间间的的耗耗费费不不是是1 1就就是是

31、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的边，从而的边，从而(1,2,.,n)(1,2,.,n)是是G G的一条哈密顿回路。的一条哈密顿回路。现在学习的是第22页，共99页99-232023/2/27引理引理7-2若若L L1 1 L L2 2，L L2 2 L L3 3，则，则L L1 1 L

32、 L3 3。现在学习的是第23页，共99页99-242023/2/277.3 7.3 非确定型图灵机非确定型图灵机 为为讨讨论论NPNP问问题题，再再引引进进一一种种虚虚设设的的计计算算模模型型，即即非非确确定定型图灵机。型图灵机。定定义义7-67-6 一一个个k-k-带带非非确确定定型型图图灵灵机机（NDTMNDTM）M M可可由由下下述述7 7元组确定：元组确定：M=QM=其其中中Q Q，T T，I I，b b，q q0 0和和q qr r的的定定义义与与确确定定型型图图灵灵机机相相同同（参参看看第第5 5章定义章定义5-35-3），而），而是：是：QTQTk kA|AA|AQ(TLQ(T

33、L，R R，S)S)k k。现在学习的是第24页，共99页99-252023/2/27 定定义义指指出出，非非确确定定型型图图灵灵机机，对对于于由由一一个个状状态态与与k k个个磁磁带带符符号号所所给给定定的的序序组组，确确定定的的下下一一动动作作不不是是唯唯一一确确定定的的，它它将将要要在在一一个个有有穷穷集集合合A A中中选选择择（猜猜测测），它它在在同同一一时时刻刻里里可可以以做做多多种种运运算算。但但要要注注意意，一一个个NDTMNDTM机机M M只只能能在在A A中中任任意意选选择择其其下下一一个个动动作作，然然而而不能选不能选A A以外的动作。以外的动作。假假定定(q,(a(q,(

34、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的的某某一一方方格格，则则机机器器的的下下一一动动作作可可以以进进入入状状态态qq，并并把把a ai i变变为为aai i，而而各各磁磁头头的的动动作作由由ddi i指定。指定。现在学习的是第25页，共99页99-262023

35、/2/27图灵机的格局图灵机的格局 定定义义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条带的带头所扫描的方格符号。条带的带头所扫描的方格符号。若若机机M M是是确确定定型型的的且且当当前前格格局局D D不不处处于于停停机机状状态态，则则可可由由下下一一动动作作函函数数唯唯一一地地确确

36、定定下下一一个个格格局局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 c1 1*c ck k。现在学习的是第26页，共99页99-272023/2/27非确定型图灵机的作用非确定型图灵机的作用 非非确确定定型型图图灵灵机机M

37、 M可可以以用用作作一一种种语语言言L L的的识识别别器器。对对于于语语言言L L，我我们们可可以以构构造造一一台台非非确确定定型型图图灵灵机机M M，让让机机器器的的带带符符包包括括该该语语言言的的字字母母表表（输输入入字字母母表表）以以及及伪伪空空白白符符b b和和其其它它一一些些特特定定符符号号（辅辅助助符符号号）。机机器器处处于于开开始始状状态态时时，将将输输入入w w打打印印在在第第一一条条磁磁带带的的最最左左面面部部分分上上，此此外外全全为为空空白白，而而其其它它的的磁磁带带此此时时全全为为空空白白；把把各各条条磁磁带带的的磁磁头头放放在在该该磁磁带带之之最最左左一一格格上上。称称

38、输输入入w w被这台机器接受，仅当：被这台机器接受，仅当：q*其中其中a a1 1（因此一切（因此一切a a2 2,.,a,.,ak k）有停机状态）有停机状态q qr r于其中。于其中。现在学习的是第27页，共99页99-282023/2/27 定定义义7-87-8 对对语语言言L L，按按上上述述方方法法构构成成的的非非确确定定型型图图灵灵机机NDTMNDTM接接受受L L，当当且且仅仅当当对对wLwL，NDTMNDTM可可接接受受w w，对对w w L L，NDTMNDTM陷陷入入不不停停机机状状态态。非非确确定定型型图图灵灵机机NDTM接受语言接受语言L，记作，记作L(NDTM)L(N

39、DTM)。非确定型图灵机非确定型图灵机NDTM接受语言接受语言L 现在学习的是第28页，共99页99-292023/2/27例例7-3 7-3 等分划问题等分划问题试设计一台试设计一台NDTMNDTM，它接受了形如：，它接受了形如：的的字字，其其中中i i1 1，i i2 2，.，i ik k为为非非负负整整数数满满足足下下述述要要求求：有有I I1,2,.,k1,2,.,k使使 换换言言之之，字字w w被被接接受受当当且且仅仅当当用用字字w w所所表表现现的的数数列列i i1 1，i i2 2，.，i ik k，可可以以被被分分割割为为两两个个子子序序列列，各各子子序序列列的的数数之之和和相

40、相等等。这这个个问问题题是所谓是所谓等分划问题等分划问题，已经知道，它是一个，已经知道，它是一个NPNP完全问题。完全问题。现在学习的是第29页，共99页99-302023/2/27 下下面面设设计计一一台台三三带带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；当当扫扫描描到到输输入入末末端端时时，机

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

42、算不不接接受受该该输输入入。因因此此，按按我我们们的的定定义义，该该机机器器接接受受10100101010010。现在学习的是第30页，共99页99-312023/2/27表表7-1 7-1 例例7-37-3中非确定型图灵机中非确定型图灵机M M的下移函数的下移函数 当前状态 当前带符 新带符及带头移动 新状态 说 明 带1 带2 带3 带1 带2 带3 q0 1 bb1,S$,R$,Rq1 第1磁带不变，2、3磁带之左端打印上$，进入状态q1 q11bb1,R1,Rb,Sb,Sb,Sb,Sq2q3 在此开始选择：是把下一段0记在带2(q2)上呢？还是记在带3(q3)上？q201b bbbbb

43、b0,R1,Sb,S 0,Rb,Sb,L b,Sb,Sb,L q2q1q4 把所扫描的一段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-322023/2/27q q 1q 10q 10q 101q 1010q 10100q 10100q 101001q 10100

44、10q 1010010q01010010q001010010q$001010010q$00接受。接受。q q 1q 10q10q 101q 1010q 10100q 10100q 101001q 1010010q 1010010q0停止，因无下一格局。停止，因无下一格局。现在学习的是第32页，共99页99-332023/2/27NDTMNDTM的时空复杂性的时空复杂性 定定义义7-97-9 称称一一台台NDTM机机M的的时时间间复复杂杂性性是是T(n)，假假若若对对于于任任何何长长为为n的的可可接接受受的的输输入入w，都都存存在在着着一一条条导导向向接接受受指指令令的的计计算算路路，该该计计算

45、算路路至至多多有有T(n)步步。称称M的的空空间间复复杂杂性性是是S(n)，假假若若对对于于上上述述输输入入w，有有一一条条导导向向接接受受指指令令的的计计算算路路，于于其其中在每一条带上至多有中在每一条带上至多有S(n)个相异的磁带方格被扫描过。个相异的磁带方格被扫描过。现在学习的是第33页，共99页99-342023/2/27例例7-37-3的复杂性的复杂性 例例7-47-4 对对于于例例7-37-3所所设设计计的的机机器器M M，其其时时间间复复杂杂性性为为2n+22n+2，而而空空间间复复杂杂性性为为n+1n+1。对对所所述述的的空空间间复复杂杂性性是是显显然然的的，为为了了看看出出时

46、时间间复复杂杂性性为为2n+22n+2，只只须须注注意意：当当对对输输入入扫扫描描结结束束（共共用用n+1n+1步）后，要回头对步）后，要回头对2 2、3 3磁带进行比较（不超过磁带进行比较（不超过n+1n+1步）。步）。现在学习的是第34页，共99页99-352023/2/27用用DTM模拟模拟NDTM 原原则则上上，对对于于每每一一台台NDTMNDTM机机，都都可可以以设设计计一一台台DTMDTM机机来来模模拟拟它它，使使得得两两者者皆皆接接受受了了同同一一语语言言。然然而而DTMDTM的的时时间间耗耗费费要要大大得得多多，可可以以证证明明，这这种种模模拟拟的的时时间间耗耗费费下下界界是是

47、指指数数型型的的。确确切切地地说说，设设T(n)T(n)是是“时时间间可可构构造造的的”函函数数（即即存存在在一一台台DTMDTM机机，给给出出该该机机的的任任一一输输入入n n，机机器器将将在在第第T(n)T(n)步步停停机机），则则对对每每一一台台为为T(n)T(n)时时间间囿囿界界的的NDTMNDTM机机M M，可可以以找找到到一一个个常常数数c cl l和一台和一台DTMDTM机机MM使使L(M)=L(M)L(M)=L(M)且且MM的时间复杂性为的时间复杂性为O(cO(cT(n)T(n)。为为了了证证明明这这个个结结果果，可可以以用用穷穷举举算算法法来来构构造造一一台台模模拟拟M M的

48、的DTMDTM机机MM。首先，可以找到常数首先，可以找到常数d d，使得，使得NDTMNDTM机机M M在任何情况下的下一动作在任何情况下的下一动作现在学习的是第35页，共99页99-362023/2/27的的选选择择可可能能不不超超过过d d个个。因因此此机机器器M M的的长长度度不不超超过过T(n)T(n)的的任任何何一一条条计计算算路路都都可可用用字字母母表表=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)个个可可将将其

49、其按按字字母母次次序序排排列列。对对于于长长为为n n的的输输入入x x，DTMDTM机机MM模模拟拟NDTMNDTM如如下下，依依次次模模拟拟上上述述ww*为为w w，（即即MM在在这这次次模模拟拟中中的的计计算算路路），如如M M中中不不存存在在如如w w所所示示的的计计算算路路或或者者w w不不是是M M接接受受x x的的计计算算路路，则则MM去去模模拟拟w w的的下下一一个个次次序序的的字字母母所所示示的的计计算算路路。注注意意，MM在在每每次次模模拟拟时时要要耗耗时时O(T(n)O(T(n)，于于是是整整个个模模拟拟至至多多耗耗费费时时间间O(T(n)(d+1)O(T(n)(d+1)

50、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)止），这里就不再叙述了。这样我们就证了下述定理：止），这里就不再叙述了。这样我们就证了下述定理：现在学习的是第36页，共99页99-372023/2/27定理定理7-17-11.如如果果取取上上述述非非确确定定型型图图灵灵机机类类为为计计算算模模型型，则则这这个个计计算算模模型同已知的种种计算模型等价。型同已知的种种计算模型等价。2.对对于于任任一一台台