《计算理论基础章优秀PPT.ppt》由会员分享,可在线阅读,更多相关《计算理论基础章优秀PPT.ppt(61页珍藏版)》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、7.1 图灵机计算困难性量度n7.1.1 困难性的量度n1空间困难度n2时间困难性n3巡回困难性17.1.1 困难性的量度q1空间困难度q定义7-1 令M是一个对于全部输入都停机的离线图灵机,s:NN是一个函数。假如对于每个长度为n的输入字,M在任一条存贮带(或工作带)上至多扫视s(n)个单元,那么称M是s(n)空间有界图灵机,或称M具有空间困难度s(n)。27.1.1 困难性的量度q2时间困难性q定义7-2 设M是一个对于全部输入都停机的确定图灵机,t:NN是一个函数。假如对于每个长度为n的输入,M在停机前最多做t(n)动作(步骤),那么就称M是一个t(n)时间有界的图灵机,或称M具有时间困
2、难度t(n)。37.1.1 困难性的量度n3巡回困难性n定义7-3 TM M对于给定的输入w,其运行的周相为(0,i1),(i1,i2),(i2,i3),(ir-2,ir-1),则称0,i1,i2,ir-1,是一个有限周相的划分,数r称为该划分的巡回数。47.1.2 困难性量度的记法 n定义定义7-4设设f和和g是两个函数,是两个函数,f、g:NR+。假如。假如nn则称则称f(n)=O(g(n)。此时,。此时,g(n)是是f(n)渐近增长的一个渐近增长的一个上界。上界。57.1.2 困难性量度的记法n定义定义7-5设设f和和g是两个函数,是两个函数,f、g:NR+,称,称f(n)=o(g(n)
3、,假如有,假如有n67.1.2 困难性量度的记法【例例7-3】不难验证下面各式具有o关系:nn2=o(n3)nn=o(nloglogn)nnlogn=o(n2)77.1.2 困难性量度的记法87.1.3 算法分析【例【例7-47-4】考虑接受语言考虑接受语言 L=WCWR|W0|1*L=WCWR|W0|1*的图灵机的困难性。的图灵机的困难性。语言语言L L具有时间困难度具有时间困难度(n)(n),因为存在一个图灵机,因为存在一个图灵机M M,它具有两条带,并把,它具有两条带,并把C C左边的内容复制到其次条带左边的内容复制到其次条带上,然后当遇到上,然后当遇到C C时,时,M M其次带的读头向
4、左,经过它其次带的读头向左,经过它刚刚复制的字符串,回至其次带的起先位置,向右刚刚复制的字符串,回至其次带的起先位置,向右比较输入带比较输入带C C右侧的字符和其次带的字符,假如每对右侧的字符和其次带的字符,假如每对字符都相同,且字符都相同,且C C左边的符号数相等,那么左边的符号数相等,那么M M接受。接受。易见,假如输入长度是易见,假如输入长度是n n,则,则M M最多做最多做n+1n+1个动作。个动作。97.1.3 算法分析【例【例7-47-4】考虑接受语言考虑接受语言 L=WCWR L=WCWR|W0|1*|W0|1*的图灵机的困难性。的图灵机的困难性。存在另一个图灵机存在另一个图灵机
5、M2M2,它接受,它接受L L,具有空间,具有空间困难度困难度log2nlog2n。M2M2用二条工作带来作二进制用二条工作带来作二进制计数器,首先,检查输入,看看是否只出现计数器,首先,检查输入,看看是否只出现一个一个C C,以及,以及C C左边和右边的符号数是否相等。左边和右边的符号数是否相等。然后,逐个字符地比较然后,逐个字符地比较C C左边和右边的字,同左边和右边的字,同时用上述计数器找出对应的符号,假如它们时用上述计数器找出对应的符号,假如它们不一样,不一样,M2M2停机且不接受,假如全部的符号停机且不接受,假如全部的符号都一样,都一样,M2M2就接受。就接受。107.1.3 算法分
6、析【例例7-57-5】自然数的二进制表示转变为一进制表示。图灵机T1的设计如下:设输入为:a0a1a2an-1(ai0,1),则输出为am,其中m=。T1有两条工作带x和y,T1的工作过程如下:(1)在x上写一个a;(2)若输入为空格,则停机;(3)若输入为1,工作带x的内容送至输出带,并把x的内容在y上抄两遍,然后用y 的内容覆盖原x的内容,清除y;否则若输入符号为0时,只把x的内容在y上抄两遍,然后用y 的内容覆盖原x的内容;(4)转至步(2)。117.1.4 困难性类 n定义定义7-6 7-6 设设t:Nt:N N N是一个函数,定义时间困难是一个函数,定义时间困难性类性类DTIME(t
7、(n)DTIME(t(n)为为nDTIME(t(n)=L|LDTIME(t(n)=L|L是由一个由是由一个由O(t(n)O(t(n)时间的图灵机识别的语言时间的图灵机识别的语言。n定义定义7-7 7-7 设设s:Ns:N N N是一个函数,定义空间困难是一个函数,定义空间困难性类性类DSPACE(s(n)DSPACE(s(n)为为nDSPACE(s(n)=L|LDSPACE(s(n)=L|L是一个由是一个由O(s(n)O(s(n)空间的图灵机识别的语言空间的图灵机识别的语言。127.1.4 困难性类 n定义定义7-8 7-8 设设t:Nt:N N N是一个函数,定义非确定时是一个函数,定义非确
8、定时间困难性类间困难性类NTIME(t(n)NTIME(t(n)为为nNTIME(t(n)=L|LNTIME(t(n)=L|L是一个由是一个由O(t(n)O(t(n)时间的非确定图灵机识别的语言时间的非确定图灵机识别的语言。n定义定义7-9 7-9 设设s:Ns:N N N是一个函数,定义非确定空是一个函数,定义非确定空间困难性类间困难性类NSPACE(s(n)NSPACE(s(n)为为nNSPACE(s(n)=L|LNSPACE(s(n)=L|L是由一个由是由一个由O(s(n)O(s(n)空间的非确定图灵机识别的语言空间的非确定图灵机识别的语言。137.2 线性加速和带压缩定理定理7-47-
9、4线性加速定理线性加速定理 假如假如L L被一个具有被一个具有k k条工作带的条工作带的t(n)t(n)时间有界图灵机时间有界图灵机M1M1接受,接受,那么只要那么只要k1k1,且,且 ,则则L L就可以被一个就可以被一个k k带带C t(n)C t(n)时间有界图灵机时间有界图灵机接受,这里接受,这里C C是大于是大于0 0的随意数。的随意数。147.2 线性加速和带压缩定理定理7-5假如对于假如对于K1和某个常数和某个常数C,L被一个被一个k带带Cn时间有界的时间有界的TM接受,那么对于随意接受,那么对于随意0,L被一个被一个k带带(1+)n时间有界时间有界TM接受。接受。157.2 线性
10、加速和带压缩定理定理7-6 7-6 假如假如L L被多带被多带TMTM在时间在时间t(n)t(n)内接受,内接受,那么那么L L可被一个单带可被一个单带TMTM在时间在时间t2(n)t2(n)内接受。内接受。167.2 线性加速和带压缩定理7-7 假如L被多带TM在时间t(n)内接受,那么L可被一个双带TM在时间t(n)log(t(n)内接受。177.3 谱系定理 n任何谱系中都有一些“间隙”,即存在一个函数t(n),使得 DTIME(t2(n)=DTIME(t(n)n对于任何全递归函数f,都有一个时间困难度tf(n),使得nDTIME(tf(n)=DTIME(f(tf(n)n存在一个无穷序列
11、的TM,它们都识别L,而其中每一个TM运行起来都比前面的快得多。187.3 谱系定理定理7-8 给定任何全递归的时间界限(空间界限)t(n),存在一个递归语言L,它不在DTIME(t(n)(DSPACE(t(n)中。证明:接受对角线方法,证明关于时间的结果。对于空间的结果接受类似的方法可以证明。因为t(n)是全递归的,故存在一个能停机的TM M来计算它。我们来构造一个TM ,它接受一个语言 0|1*,是递归的,但不在DTIME(t(n)中。197.3 谱系定理设Xi是在0|1*正则依次中第i个字符串,我们可以将具有随意带字母表的排成序列1,M2,Mi,现定义Xi|Mi 在t(|Xi|)个动作内
12、不接受i,我们可以断言L是递归的。为识别L,执行下面算法:给定一个长度为n 的输入w,在 上模拟M,用以计算t(n),然后确定w 是否在L中。写成二进制形式的整数i是某个多带TM Mi的标记。在 上对Mi模拟t(n)个动作,假如Mi停机但不接受,或超过t(n)个动作还没接受,则接受w。207.3 谱系定理假定L=L(Ml)且Ml是t(n)时间有界的,假如Xl L,则Ml在t(n)时间内接受Xl,这里n=|Xl|,Xl L。与此产生冲突。假如Xl L,那么Ml不接受Xl,故依据L的定义,Xl L,也产生冲突。两种假设都产生冲突,故Ml是t(n)时间有界的假定必是错误的。定理得证。对于任何递归的时
13、间或空间困难度函数f(n),总有一个f(n),使得某个语言是在由f(n)定义的困难性类中,而不在f(n)定义的类中。217.3 谱系定理定义定义7-10称一个函数称一个函数s(n)是空间可构造的,是空间可构造的,假如有某个图灵机假如有某个图灵机M,M是是s(n)空间有界的,空间有界的,且对每个且对每个n,存在某个长度为,存在某个长度为n的输入,对于的输入,对于这个输入,这个输入,M实际占用了实际占用了s(n)个带单元。个带单元。227.3 谱系定理n空间可构造函数集包括logn、nk、2n、n!,假如s1(n)、s2(n)是空间可构造的,那么s1(n)+s2(n)、2s1(n)、和s1(n)s
14、2(n)也是空间可构造的,因此空间可构造函数是相当丰富的。n 237.3 谱系定理引理7-1 假如L被一个s(n)log2n空间有界的TM 接受,那么L被一个s(n)空间有界且对全部输入都能停机的TM接受。247.3 谱系定理定理7-9 假如s2(n)是一个完全空间可构造的函数,且s1(n)和s2(n)都至少是log2n,那么有一个语言,它在DSPACE(s2(n)中,而不在DSPACE(s1(n)中。257.3 谱系定理定义定义7-11 7-11 称一个函数称一个函数t(n)t(n)是时间可构造的,是时间可构造的,假如有某个多带图灵机假如有某个多带图灵机M M,M M是是t(n)t(n)时间
15、有界时间有界的,且对每个的,且对每个n n,都存在某个长度为,都存在某个长度为n n 的输入,的输入,对于这个输入,对于这个输入,M M实际做了实际做了t(n)t(n)个动作。个动作。267.3 谱系定理定理定理7-10假如假如t2(n)是一个完全空间可构造是一个完全空间可构造的函数,的函数,那么有一个语言,它在那么有一个语言,它在DTIME(t2(n)中,而中,而不在不在DTIME(t1(n)中。中。277.3 谱系定理证明:用对角线的方法证明。构造一个t2(n)时间有界的TM M,其操作如下:因为t2(n)是一个完全空间可构造的函数,故存在一个TM M,对于任何 输入长度为n的符号串,这个
16、TM都恰好用t2(n)时间。M首先模拟这个TM的各个动作,并将步数记录在附加带上。然后把输入w作为一个TM 的编码,并在这个输入上模拟 ,因为M的带数目是个固定的数,故对于某些w,M将比 有更多的带。用二条带可以模拟,但要损失一个因子log t(n),而且因为有很多带符号,它们必需用某个固定数目的符号进行编码,故M对的t1(n)个动作的模拟,须要C t1(n)log t1(n)时间。这里C是一个与M有关的常数。287.3 谱系定理M接受w,仅当对 的模拟完成且拒绝,即有L(M)=w|以w编码为标记的TM Mw在t1(n)步停机且拒绝w。若存在TM M1,使得(M1)=L(M),且是t1(n)有
17、界的,则必存在一个输入w L(M),它充分长,令n=|w|,有C t1(n)log t1(n)t2(n)且w的编码是1的标记。此时,w被M1接受,当且仅当它被M1拒绝。因而L(M)在DTIME(t2(n)中,而不在DTIME(t1(n)中。297.4 困难性量度间的关系及非确定谱系定理定理7-117-11(1)(1)假如在假如在DTIME(f(n)DTIME(f(n)中,那么在中,那么在DSPACE(f(n)DSPACE(f(n)中。中。(2)(2)假如在假如在DSPACE(f(n)DSPACE(f(n)中,且中,且f(n)log2nf(n)log2n,那,那么有某个常数么有某个常数C C(它
18、依靠于),使得是在(它依靠于),使得是在DTIME(DTIME(f(n)f(n)中。中。(3)(3)假如假如L L在在NTIME(f(n)NTIME(f(n)中,那么有某个常数中,那么有某个常数C C,它依靠于它依靠于L L,使得,使得L L在在DTIME(Cf(n)DTIME(Cf(n)中。中。307.4 困难性量度间的关系及非确定谱系定理定理7-12Savitch定理定理假如假如L在在NSPACE(s(n)中,那么中,那么L在在DSPACE(s2(n)中。这里假定中。这里假定s(n)是完全空间可构造的,且是完全空间可构造的,且s(n)log2n。这个定理中,对于这个定理中,对于s(n)lo
19、g2n时,要求时,要求s(n)是完全空间可构造的;若是完全空间可构造的;若s(n)n而且而且s(n)不不是完全空间可构造的,是完全空间可构造的,Savitch定理仍旧成立。定理仍旧成立。317.4 困难性量度间的关系及非确定谱系引理引理7-2转换引理转换引理设设s1(n)、s2(n)和和f(n)是完全空是完全空间可构造的,且间可构造的,且s2(n)n,f(n)n,那么,由,那么,由NSPACE(s1(n)NSPACE(s2(n),可以推,可以推出出NSPACE(s1(f(n)NSPACE(s2(f(n)对于对于DSPACE、DTIME、NTIME状况下,也有类似状况下,也有类似的结果。利用确定
20、时间状况下的转换结果,我们的结果。利用确定时间状况下的转换结果,我们可以证明可以证明DTIME(n2)DTIME(n2n)327.4 困难性量度间的关系及非确定谱系定理定理7-13假如假如0,且,且r0,那么那么NSPACE(nr)NSPACE(nr+)33 7.5 间隙定理、加速定理 定理定理7-14给定任何一个全递归的函数给定任何一个全递归的函数g(n)n,存在一个全递归函数存在一个全递归函数s(n),使得,使得DSPACE(s(n)=DSPACE(g(s(n),即在空间界,即在空间界限限s(n)和和g(s(n)之间有个之间有个“间隙间隙”,没有任何语,没有任何语言的最小空间困难度会在这个
21、间隙内。言的最小空间困难度会在这个间隙内。347.5 间隙定理、加速定理 定理定理7-15 Blum 7-15 Blum 加速定理加速定理 设设r(n)r(n)是随意全递是随意全递归函数,存在一个递归语言归函数,存在一个递归语言L L,使得对于任何一,使得对于任何一个接受个接受L L的图灵机的图灵机MiMi,都存在一个图灵机,都存在一个图灵机MjMj,MjMj接受接受L L,且对几乎全部的,且对几乎全部的n n,r(sj(n)si(n)r(sj(n)si(n)。357.6 类与类n类n类n完全性367.6.1 P类 定义定义7-12 P7-12 P是确定型单带图灵机在多项式时间内可是确定型单带
22、图灵机在多项式时间内可判定的语言类,即判定的语言类,即对于全部与确定型单带图灵机多项式等价的计算模对于全部与确定型单带图灵机多项式等价的计算模型来说,型来说,P P是不变的;是不变的;P P大致对应于在计算机上实际可解的问题类。大致对应于在计算机上实际可解的问题类。377.6.1 P类【例【例7-87-8】有向图中两个节点的连通性判定问题是】有向图中两个节点的连通性判定问题是P P类问题。类问题。证明:设有向图证明:设有向图G=G=,s,t Vs,t V,n=|V|n=|V|。不。不失一般性可设是简洁图。下面是该问题的判定算失一般性可设是简洁图。下面是该问题的判定算法。法。步步1 1 标记节点
23、标记节点s;s;步步2 2 重复步重复步2.12.1直至不再有节点须要标记:直至不再有节点须要标记:步步2.1 2.1 扫描扫描G G的全部边。假如找到一条边(的全部边。假如找到一条边(u,vu,v),),u u、vVvV,u u被标记,而被标记,而v v未被标记,则标记未被标记,则标记v v;步步3 3 若若t t被标记,则接受;否则拒绝。被标记,则接受;否则拒绝。387.6.2 NP类定义定义7-13 7-13 语言语言L L的验证机是一个算法的验证机是一个算法V V,这里,这里A=w|A=w|对某个字符串对某个字符串c c,V V接受接受其中,其中,c c表示算法表示算法V V所运用的附
24、加信息所运用的附加信息 。例如例如HamiltonHamilton路问题中给定的一条路的信息,算法路问题中给定的一条路的信息,算法V V可以判定可以判定c c是否是是否是HamiltonHamilton路。路。397.6.2 NP类定义定义7-14 NP7-14 NP是具有多项式时间验证机的语言类。是具有多项式时间验证机的语言类。HamiltonHamilton路问题,它的验证机设计如下:路问题,它的验证机设计如下:对于输入图对于输入图G G,节点,节点s s、t t,步步1 1 写一列写一列m m 个数个数,v1,v2,vm,v1,v2,vm,m m是是G G的节点数,的节点数,列中的每一数
25、,都是从列中的每一数,都是从1 1到到m m中非确定选择的;中非确定选择的;步步2 2 在列中检查重复性,若发觉重复,则拒绝;在列中检查重复性,若发觉重复,则拒绝;步步3 3 检查检查s=v1,t=vms=v1,t=vm是否成立。若有一个不成立,是否成立。若有一个不成立,则拒绝;则拒绝;步步4 4 对于对于i=1,2,m-1i=1,2,m-1,检查,检查(vi,vi+1)(vi,vi+1)是否是是否是G G的的边,若都是边,若都是G G的边,则接受;否则拒绝。的边,则接受;否则拒绝。407.6.2 NP类定理定理7-167-16 一个语言在NP中,当且仅当它能被某个非确定型多项式时间的图灵机判
26、定。证明:首先证明若LNP,则存在非确定型多项式时间的图灵机判定它。因为LNP,所以存在L的多项式时间的验证机V,构造非确定型图灵机N如下:设输入为w,步1 非确定地选择长为nk的字符串c;步2 在输入上运行V;步3 若V接受,则接受;否则拒绝。417.6.2 NP类下面证明若L有非确定型多项式时间的图灵机N接受它,则LNP。为此,构造多项式时间的验证机V如下:对于输入,步1 在输入w上模拟N,把c的每一个符号看作是对每一步所作的非确定性选择的描述;步2 若N的该计算分支接受,则接受;否则拒绝。427.6.3 NP完全性 n可满足问题可满足问题:判定一个布尔表示式是否可满判定一个布尔表示式是否
27、可满足足.n定理定理7-17 7-17 库克库克列文定理列文定理 可满足问题属可满足问题属于,当且仅当于,当且仅当=。437.6.3 NP完全性 定义定义7-157-15 称语言LA多项式时间映射可归约到语言LB,或简称为多项式时间可归约到LB,记为LAP LB,若存在多项式时间可计算函数f:*,对于每一个w,有wLA f(w)LB称函数f为LA到LB多项式时间归约。447.6.3 完全性定理定理7-187-18 若APB,且BP,则AP。证明:设M是判定B的多项式 时间算法,f是从A到B的多项式时间归约。判定A的多项式时间算法A如下:对于输入w,步1 计算f(w);步2 在输入f(w)上运行
28、M,输出M的输出。因为wA f(w)B,又f、都是多项式时间可计算的,所以A也是多项式时间可完成的。457.6.3 完全性定义定义7-16 7-16 语言语言L L是是NPNP完全的,若它满足下面两完全的,若它满足下面两个条件:个条件:(1)LNP(1)LNP;(2)NP(2)NP中的每个中的每个LALA都多项式时间可归约为都多项式时间可归约为L L。467.6.3 完全性定理定理7-19 7-19 库克库克列文定理列文定理 可满足问题可满足问题是完全的。是完全的。证明证明:首先证明首先证明SATSAT属于属于NPNP。因为对于任何命题变。因为对于任何命题变元不确定的选取,都可以在非确定型多项
29、式时间元不确定的选取,都可以在非确定型多项式时间内得到一个赋值,当赋值满足公式时接受。内得到一个赋值,当赋值满足公式时接受。下面证明下面证明NPNP中的每一个语言都可以多项式时间归中的每一个语言都可以多项式时间归约到约到SATSAT。477.6.3 完全性n从NP中任取一个语言L,设nMN=Q,q0,B,F是nk多项式时间内判定L的非确定型图灵机,其中k是常数。对于MN的随意输入w,在多式时间内构造公式,使得wLSAT。设f是由w到的归约,下面起先描述归约f。487.6.3 完全性考虑MN在w上的执行过程。定义MN在w上的画面是一张nknk表格,其中行代表MN在输入上的一个计算分支的瞬时描述。
30、并约定每一个ID都以“#”起先和结束。当然画面的第一行是初始ID,每一行都依据MN的转移函数从上一行得到,假如画面的某一行是接受ID,则称该画面是接受的。我们把画面nknk个的格子中每一格称为一个单元。第i行第j列的单元称为celli,j,它应包含C=Q#中的一个符号。定义变量xi,j,s 497.6.3 完全性(1ink,1jnk,sC)表示单元中的内容。xi,j,s=1,意味着celli,j包含s。现在设计公式,使得变量的一个满足赋值的确对应MN在上的一个接受画面。为此要满足以下4点:(1)每个单元只能包含一个符号;(2)第一行为初始ID(3)存在接受ID(4)表的每一行都对应于从上一行的
31、ID、依据MN的规则、合法转移得到ID。事实上,从IDi变更到IDi+1只有六个单元可能变更,507.6.3 完全性517.6.3 完全性527.6.3 完全性537.6.3 完全性现在证明上面由w到的映射可以在多项式内完成。画面是一个nknk的表格,所以它包含n2k个单元,每个单元有与它相关的l个变量,l=|C|,因为l只依靠于MN,所以变量的总数是O(n2k)。对画面的每个单元,公式cell包含固定长度的公式片段,故长度为O(n2k),start对顶行的每个单元包含一个片段,所以长度为O(nk),move和accept对画面的每个单元包含固定长度的公式片段,所以它们的长度为O(n2k),于
32、是总长度为O(n2k),因此可在多项式时间内从w生成,所以,SAT是NP完全性问题。定理得证。547.6.3 完全性n3SAT问题:在布尔公式中,我们将布尔变量或其非称为文字,将由三个文字构成的子句组成的合取范式称为3SAT问题。n推论7-3 3SAT是NP完全的。n这个推论的证明有两种方式,一种方式是证明SAT多项式时间归约到3SAT;另一种方式是仿上面定理的方法,干脆产生每个子句有三个文字的合取范氏形式的公式。n557.6.3 完全性n顶点覆盖问题:若G是无向图,则G的顶点覆盖问题是节点的一个最小子集,使得G的每条边都与子集的节点之一关联。n顶点覆盖问题是NP完全的,我们可以给出一个3SA
33、T到这个问题的多项式时间内运算的归约,即把布尔公式映射为,其中G是一个图,k是一个正数,表示G的顶点覆盖子集的节点数。为此,567.6.3 完全性(1)对于中的每个布尔变元x对应G的一条边,边的两个顶点记为x和 。当x赋值为TRUE时,表示对应的覆盖选择x;当x赋值为TRUE时,表示对应的覆盖选择 。(2)子句中的三个文字对应于G的三个节点,这三节点相互连接,并分别于(1)中具有相同标记的节点相连。577.6.3 完全性587.6.3 完全性不难证明 可满足当且仅当G中有k=m+2l个节点的顶点覆盖,其中m 是的变元数,l是子句数。597.6.3 完全性n子集和问题:有一个数集x1,x2,xk和一个目标数t,判定数集是否包含一个加起来等于t的子集。607.6.3 完全性nHamilton 路径问题:图G=(V,E),求一条路径,每个节点在其中出现且只出现一次。61