资源描述
17.1 图灵机计算复杂性量度n7.1.1 复杂性的量度q1空间复杂度q2时间复杂性q3巡回复杂性27.1.1 复杂性的量度q1空间复杂度定义定义7-1 令M是一个对于所有输入都停机的离线图灵机,s:NN是一个函数。如果对于每个长度为n的输入字,M在任一条存贮带(或工作带)上至多扫视s(n)个单元,那么称M是s(n)空间有界图灵机,或称M具有空间复杂度s(n)。37.1.1 复杂性的量度q2时间复杂性定义定义7-2 设M是一个对于所有输入都停机的确定图灵机,t:NN是一个函数。如果对于每个长度为n的输入,M在停机前最多做t(n)动作(步骤),那么就称M是一个t(n)时间有界的图灵机,或称M具有时间复杂度t(n)。47.1.1 复杂性的量度n3巡回复杂性定义定义7-3 TM M对于给定的输入w,其运行的周相为(0,i1),(i1,i2),(i2,i3),(ir-2,ir-1),则称0,i1,i2,ir-1,是一个有限周相的划分,数r称为该划分的巡回数。57.1.2 复杂性量度的记法 n定义定义7-4 设f和g是两个函数,f、g:NR+。如果n n则称f(n)=O(g(n)。此时,g(n)是f(n)渐近增长的一个上界。67.1.2 复杂性量度的记法n定义定义7-5 设f和g是两个函数,f、g:NR+,称f(n)=o(g(n),如果有n 77.1.2 复杂性量度的记法【例例7-3】不难验证下面各式具有o关系:nn2=o(n3)nn=o(nloglogn)nnlogn=o(n2)87.1.2 复杂性量度的记法97.1.3 算法分析【例例7-47-4】考虑接受语言 L=WCWR|W0|1*的图灵机的复杂性。语言L具有时间复杂度(n),因为存在一个图灵机M,它具有两条带,并把C左边的内容复制到第二条带上,然后当遇到C时,M第二带的读头向左,经过它刚刚复制的字符串,回至第二带的开始位置,向右比较输入带C右侧的字符和第二带的字符,如果每对字符都相同,且C左边的符号数相等,那么M接受。易见,如果输入长度是n,则M最多做n+1个动作。107.1.3 算法分析【例例7-47-4】考虑接受语言 L=WCWR|W0|1*的图灵机的复杂性。存在另一个图灵机M2,它接受L,具有空间复杂度log2n。M2用二条工作带来作二进制计数器,首先,检查输入,看看是否只出现一个C,以及C左边和右边的符号数是否相等。然后,逐个字符地比较C左边和右边的字,同时用上述计数器找出对应的符号,如果它们不一致,M2停机且不接受,如果所有的符号都一致,M2就接受。117.1.3 算法分析【例例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)。127.1.4 复杂性类 n定义定义7-67-6 设t:NN是一个函数,定义时间复杂性类DTIME(t(n)为DTIME(t(n)=L|L是由一个由O(t(n)时间的图灵机识别的语言。n定义定义7-77-7 设s:NN是一个函数,定义空间复杂性类DSPACE(s(n)为DSPACE(s(n)=L|L是一个由O(s(n)空间的图灵机识别的语言。137.1.4 复杂性类 n定义定义7-87-8 设t:NN是一个函数,定义非确定时间复杂性类NTIME(t(n)为NTIME(t(n)=L|L是一个由O(t(n)时间的非确定图灵机识别的语言。n定义定义7-97-9 设s:NN是一个函数,定义非确定空间复杂性类NSPACE(s(n)为NSPACE(s(n)=L|L是由一个由O(s(n)空间的非确定图灵机识别的语言。147.2 线性加速和带压缩定理定理7-47-4线性加速定理线性加速定理 如果L被一个具有k条工作带的t(n)时间有界图灵机M1接受,那么只要k1,且 ,则L就可以被一个k带C t(n)时间有界图灵机接受,这里C是大于0的任意数。157.2 线性加速和带压缩定理定理7-5 如果对于K1和某个常数C,L被一个k带Cn时间有界的TM接受,那么对于任意 0,L被一个k带(1+)n时间有界TM接受。167.2 线性加速和带压缩定理定理7-6 7-6 如果L被多带TM在时间t(n)内接受,那么L可被一个单带TM在时间t2(n)内接受。177.2 线性加速和带压缩定理7-7 如果L被 多带TM在时间t(n)内接受,那么L可被一个双带TM在时间t(n)log(t(n)内接受。187.3 谱系定理 n任何谱系中都有一些“间隙”,即存在一个函数t(n),使得 DTIME(t2(n)=DTIME(t(n)n对于任何全递归函数f,都有一个时间复杂度tf(n),使得DTIME(tf(n)=DTIME(f(tf(n)n存在一个无穷序列的TM,它们都识别L,而其中每一个TM运行起来都比前面的快得多。197.3 谱系定理定理7-8 给定任何全递归的时间界限(空间界限)t(n),存在一个递归语言L,它不在DTIME(t(n)(DSPACE(t(n)中。证明:采用对角线方法,证明关于时间的结果。对于空间的结果采用类似的方法可以证明。因为t(n)是全递归的,故存在一个能停机的TM M来计算它。我们来构造一个TM ,它接受一个语言 0|1*,是递归的,但不在DTIME(t(n)中。M207.3 谱系定理设Xi是在0|1*正则顺序中第i个字符串,我们可以将具有任意带字母表的排成序列1,M2,Mi,现定义Xi|Mi 在t(|Xi|)个动作内不接受i,我们可以断言L是递归的。为识别L,执行下面算法:给定一个长度为n 的输入w,在 上模拟M,用以计算t(n),然后确定w 是否在L中。写成二进制形式的整数i是某个多带TM Mi的标记。在 上对Mi模拟t(n)个动作,如果Mi停机但不接受,或超过t(n)个动作还没接受,则接受w。MM217.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)时间有界的假定必是错误的。定理得证。n对于任何递归的时间或空间复杂度函数f(n),总有一个f(n),使得某个语言是在由f(n)定义的复杂性类中,而不在f(n)定义的类中。227.3 谱系定理定义定义7-10 称一个函数s(n)是空间可构造的,如果有某个图灵机M,M是s(n)空间有界的,且对每个n,存在某个长度为n 的输入,对于这个输入,M实际占用了s(n)个带单元。237.3 谱系定理n空间可构造函数集包括logn、nk、2n、n!,如果s1(n)、s2(n)是空间可构造的,那么s1(n)+s2(n)、2s1(n)、和s1(n)s2(n)也是空间可构造的,因此空间可构造函数是相当丰富的。n 247.3 谱系定理引理7-1 如果L被一个s(n)log2n空间有界的TM 接受,那么L被一个s(n)空间有界且对所有输入都能停机的TM接受。257.3 谱系定理定理7-9 如果s2(n)是一个完全空间可构造的函数,且s1(n)和s2(n)都至少是log2n,那么有一个语言,它在DSPACE(s2(n)中,而不在DSPACE(s1(n)中。0)n(s)n(s21ninf267.3 谱系定理定义定义7-117-11 称一个函数t(n)是时间可构造的,如果有某个多带图灵机M,M是t(n)时间有界的,且对每个n,都存在某个长度为n 的输入,对于这个输入,M实际做了t(n)个动作。277.3 谱系定理定理定理7-10 如果t2(n)是一个完全空间可构造的函数,那么有一个语言,它在DTIME(t2(n)中,而不在DTIME(t1(n)中。0)n(t)n(tlog)n(t211ninf287.3 谱系定理证明:用对角线的方法证明。构造一个t2(n)时间有界的TM M,其操作如下:因为t2(n)是一个完全空间可构造的函数,故存在一个TM M,对于任何 输入长度为n的符号串,这个TM都恰好用t2(n)时间。M首先模拟这个TM的各个动作,并将步数记录在附加带上。然后把输入w作为一个TM 的编码,并在这个输入上模拟 ,因为M的带数目是个固定的数,故对于某些w,M将比 有更多的带。用二条带可以模拟,但要损失一个因子log t(n),而且因为有许多带符号,它们必需用某个固定数目的符号进行编码,故M对的t1(n)个动作的模拟,需要C t1(n)log t1(n)时间。这里C是一个与M有关的常数。MMM297.3 谱系定理M接受w,仅当对 的模拟完成且拒绝,即有L(M)=w|以w编码为标记的TM Mw在t1(n)步停机且拒绝w。若存在TM M1,使得(M1)=L(M),且是t1(n)有界的,则必存在一个输入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)中。M307.4 复杂性量度间的关系及非确定谱系定理定理7-117-11(1)如果在DTIME(f(n)中,那么在DSPACE(f(n)中。(2)如果在DSPACE(f(n)中,且f(n)log2n,那么有某个常数C(它依赖于),使得是在DTIME(f(n)中。(3)如果L在NTIME(f(n)中,那么有某个常数C,它依赖于L,使得L在DTIME(Cf(n)中。317.4 复杂性量度间的关系及非确定谱系定理定理7-12Savitch定理定理如果L在NSPACE(s(n)中,那么L在DSPACE(s2(n)中。这里假定s(n)是完全空间可构造的,且s(n)log2n。n这个定理中,对于s(n)log2n 时,要求s(n)是完全空间可构造的;若s(n)n 而且s(n)不是完全空间可构造的,Savitch定理仍然成立。327.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情况下,也有类似的结果。利用确定时间情况下的转换结果,我们可以证明DTIME(n2)DTIME(n2n)337.4 复杂性量度间的关系及非确定谱系定理定理7-13如果 0,且r0,那么NSPACE(nr)NSPACE(nr+)34 7.5 间隙定理、加速定理 定理定理7-14 给定任何一个全递归的函数g(n)n,存在一个全递归函数s(n),使得DSPACE(s(n)=DSPACE(g(s(n),即在空间界限s(n)和g(s(n)之间有个“间隙”,没有任何语言的最小空间复杂度会在这个间隙内。357.5 间隙定理、加速定理 定理定理7-15 Blum 7-15 Blum 加速定理加速定理 设r(n)是任意全递归函数,存在一个递归语言L,使得对于任何一个接受L的图灵机Mi,都存在一个图灵机Mj,Mj接受L,且对几乎所有的n,r(sj(n)si(n)。367.6 类与类n类n类n完全性377.6.1 P类 定义定义7-127-12 P是确定型单带图灵机在多项式时间内可判定的语言类,即q对于所有与确定型单带图灵机多项式等价的计算模型来说,P是不变的;qP大致对应于在计算机上实际可解的问题类。387.6.1 P类【例【例7-87-8】有向图中两个节点的连通性判定问题是P类问题。证明:设有向图G=,s,t V,n=|V|。不失一般性可设是简单图。下面是该问题的判定算法。步1 标记节点s;步2 重复步2.1直至不再有节点需要标记:步2.1 扫描G的所有边。如果找到一条边(u,v),u、vV,u被标记,而v未被标记,则标记v;步3 若t被标记,则接受;否则拒绝。397.6.2 NP类定义定义7-13 7-13 语言L的验证机是一个算法V,这里A=w|对某个字符串c,V接受其中,c表示算法V所使用的附加信息。例如Hamilton路问题中给定的一条路的信息,算法V可以判定c是否是Hamilton路。407.6.2 NP类定义定义7-147-14 NP是具有多项式时间验证机的语言类。Hamilton路问题,它的验证机设计如下:对于输入图G,节点s、t,步1 写一列m 个数,v1,v2,vm,m是G的节点数,列中的每一数,都是从1到m中非确定挑选的;步2 在列中检查重复性,若发现重复,则拒绝;步3 检查s=v1,t=vm是否成立。若有一个不成立,则拒绝;步4 对于i=1,2,m-1,检查(vi,vi+1)是否是G的边,若都是G的边,则接受;否则拒绝。417.6.2 NP类定理定理7-167-16 一个语言在NP中,当且仅当它能被某个非确定型多项式时间的图灵机判定。证明:首先证明若LNP,则存在非确定型多项式时间的图灵机判定它。因为LNP,所以存在L的多项式时间的验证机V,构造非确定型图灵机N如下:设输入为w,步1 非确定地选择长为nk的字符串c;步2 在输入上运行V;步3 若V接受,则接受;否则拒绝。427.6.2 NP类下面证明若L有非确定型多项式时间的图灵机N接受它,则LNP。为此,构造多项式时间的验证机V如下:对于输入,步1 在输入w上模拟N,把c的每一个符号看作是对每一步所作的非确定性选择的描述;步2 若N的该计算分支接受,则接受;否则拒绝。437.6.3 NP完全性 n可满足问题可满足问题:判定一个布尔表示式是否可满判定一个布尔表示式是否可满足足.定理定理7-17 7-17 库克库克列文定理列文定理 可满足问题属于,当且仅当=。447.6.3 NP完全性 定义定义7-157-15 称语言LA多项式时间映射可归约到语言LB,或简称为多项式时间可归约到LB,记为LAP LB,若存在多项式时间可计算函数f:*,对于每一个w,有wLA f(w)LB称函数f为LA到LB多项式时间归约。457.6.3 完全性定理定理7-187-18 若APB,且BP,则AP。证明:设M是判定B的多项式 时间算法,f是从A到B的多项式时间归约。判定A的多项式时间算法A如下:对于输入w,步1 计算f(w);步2 在输入f(w)上运行M,输出M的输出。因为wA f(w)B,又f、都是多项式时间可计算的,所以A也是多项式时间可完成的。467.6.3 完全性定义定义7-167-16 语言L是NP完全的,若它满足下面两个条件:(1)LNP;(2)NP中的每个LA都多项式时间可归约为L。477.6.3 完全性定理定理7-19 7-19 库克库克列文定理列文定理 可满足问题是完全的。证明:首先证明SAT属于NP。因为对于任何命题变元不确定的选取,都可以在非确定型多项式时间内得到一个赋值,当赋值满足公式时接受。下面证明NP中的每一个语言都可以多项式时间归约到SAT。487.6.3 完全性n从NP中任取一个语言L,设MN=Q,q0,B,F是nk多项式时间内判定L的非确定型图灵机,其中k是常数。对于MN的任意输入w,在多式时间内构造公式,使得wLSAT。设f是由w到的归约,下面开始描述归约f。497.6.3 完全性考虑MN在w上的执行过程。定义MN在w上的画面是一张nknk表格,其中行代表MN在输入上的一个计算分支的瞬时描述。并约定每一个ID都以“#”开始和结束。当然画面的第一行是初始ID,每一行都根据MN的转移函数从上一行得到,如果画面的某一行是接受ID,则称该画面是接受的。我们把画面nknk个的格子中每一格称为一个单元。第i行第j列的单元称为celli,j,它应包含C=Q#中的一个符号。定义变量xi,j,s 507.6.3 完全性(1ink,1jnk,sC)表示单元中的内容。xi,j,s=1,意味着celli,j包含s。现在设计公式,使得变量的一个满足赋值确实对应MN在上的一个接受画面。为此要满足以下4点:(1)每个单元只能包含一个符号;(2)第一行为初始ID(3)存在接受ID(4)表的每一行都对应于从上一行的ID、按照MN的规则、合法转移得到ID。事实上,从IDi变化到IDi+1只有六个单元可能变化,517.6.3 完全性527.6.3 完全性537.6.3 完全性547.6.3 完全性现在证明上面由w到的映射可以在多项式内完成。画面是一个nknk的表格,所以它包含n2k个单元,每个单元有与它相关的l个变量,l=|C|,因为l只依赖于MN,所以变量的总数是O(n2k)。对画面的每个单元,公式cell包含固定长度的公式片段,故长度为O(n2k),start对顶行的每个单元包含一个片段,所以长度为O(nk),move和accept对画面的每个单元包含固定长度的公式片段,所以它们的长度为O(n2k),于是总长度为O(n2k),因此可在多项式时间内从w生成,所以,SAT是NP完全性问题。定理得证。557.6.3 完全性n3SAT问题:在布尔公式中,我们将布尔变量或其非称为文字,将由三个文字构成的子句组成的合取范式称为3SAT问题。推论推论7-3 3SAT是NP完全的。n这个推论的证明有两种方式,一种方式是证明SAT多项式时间归约到3SAT;另一种方式是仿上面定理的方法,直接产生每个子句有三个文字的合取范氏形式的公式。567.6.3 完全性n顶点覆盖问题:若G是无向图,则G的顶点覆盖问题是节点的一个最小子集,使得G的每条边都与子集的节点之一关联。n顶点覆盖问题是NP完全的,我们可以给出一个3SAT到这个问题的多项式时间内运算的归约,即把布尔公式映射为,其中G是一个图,k是一个正数,表示G的顶点覆盖子集的节点数。为此,577.6.3 完全性(1)对于中的每个布尔变元x对应G的一条边,边的两个顶点记为x和 。当x赋值为TRUE时,表示对应的覆盖选择x;当x赋值为TRUE时,表示对应的覆盖选择 。(2)子句中的三个文字对应于G的三个节点,这三节点相互连接,并分别于(1)中具有相同标记的节点相连。xx587.6.3 完全性597.6.3 完全性不难证明 可满足当且仅当G中有k=m+2l个节点的顶点覆盖,其中m 是的变元数,l是子句数。607.6.3 完全性n子集和问题:有一个数集x1,x2,xk和一个目标数t,判定数集是否包含一个加起来等于t的子集。617.6.3 完全性nHamilton 路径问题:图G=(V,E),求一条路径,每个节点在其中出现且只出现一次。
展开阅读全文