计算理论基础章7

7.1图灵机计算困难性量度7.1.1困难性的量度1．空间困难度2．时间困难性3．巡回困难性17.1.1困难性的量度1．空间困难度定义7-1令M是一个对于全部输入都停机的离线图灵机，s：NN是一个函数。假如对于每个长度为n的输入字，M在任一条存贮带（或工作带）上至多扫视s(n)个单元，那么称M是s(n)空间有界图灵机，或称M具有空间困难度s(n)。27.1.1困难性的量度2．时间困难性定义7-2设M是一个对于全部输入都停机的确定图灵机，t：NN是一个函数。假如对于每个长度为n的输入，M在停机前最多做t(n)动作（步骤），那么就称M是一个t(n)时间有界的图灵机，或称M具有时间困难度t(n)。37.1.1困难性的量度3．巡回困难性定义7-3TMM对于给定的输入w，其运行的周相为（0,i1）,（i1,i2）,（i2,i3）,…,（ir-2,ir-1），则称0，i1，i2，…，ir-1，是一个有限周相的划分，数r称为该划分的巡回数。47.1.2困难性量度的记法定义7-4设f和g是两个函数，f、g：NR+。假如

则称f(n)=O(g(n))。此时，g(n)是f(n)渐近增长的一个上界。57.1.2困难性量度的记法定义7-5设f和g是两个函数，f、g：NR+，称f(n)=o(g(n))，假如有

67.1.2困难性量度的记法【例7-3】不难验证下面各式具有o关系：n2=o(n3)n=o(nloglogn)nlogn=o(n2) 77.1.2困难性量度的记法87.1.3算法分析【例7-4】考虑接受语言L={WCWR|W{0|1}*}的图灵机的困难性。语言L具有时间困难度Ｏ(n)，因为存在一个图灵机M，它具有两条带，并把C左边的内容复制到其次条带上，然后当遇到C时，M其次带的读头向左，经过它刚刚复制的字符串，回至其次带的起先位置，向右比较输入带C右侧的字符和其次带的字符，假如每对字符都相同，且C左边的符号数相等，那么M接受。易见，假如输入长度是n，则M最多做n+1个动作。97.1.3算法分析【例7-4】考虑接受语言L={WCWR|W{0|1}*}的图灵机的困难性。存在另一个图灵机M2，它接受L，具有空间困难度log2n。M2用二条工作带来作二进制计数器，首先，检查输入，看看是否只出现一个C，以及C左边和右边的符号数是否相等。然后，逐个字符地比较C左边和右边的字，同时用上述计数器找出对应的符号，假如它们不一样，M2停机且不接受，假如全部的符号都一样，M2就接受。107.1.3算法分析【例7-5】

自然数的二进制表示转变为一进制表示。图灵机T1的设计如下：设输入为：a0a1a2…an-1(ai{0,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困难性类定义7-6设t:NN是一个函数，定义时间困难性类DTIME(t(n))为 DTIME(t(n))={L|L是由一个由O(t(n))时间的图灵机识别的语言}。定义7-7设s:NN是一个函数，定义空间困难性类DSPACE(s(n))为 DSPACE(s(n))={L|L是一个由O(s(n))空间的图灵机识别的语言}。127.1.4困难性类定义7-8设t:NN是一个函数，定义非确定时间困难性类NTIME(t(n))为 NTIME(t(n))={L|L是一个由O(t(n))时间的非确定图灵机识别的语言}。定义7-9设s:NN是一个函数，定义非确定空间困难性类NSPACE(s(n))为 NSPACE(s(n))={L|L是由一个由O(s(n))空间的非确定图灵机识别的语言}。137.2线性加速和带压缩定理7-4[线性加速定理]假如L被一个具有k条工作带的t(n)时间有界图灵机M1接受，那么只要k>1，且，则L就可以被一个k带Ct(n)时间有界图灵机接受，这里C是大于0的随意数。147.2线性加速和带压缩定理

7-5假如对于K>1和某个常数C，L被一个k带Cn时间有界的TM接受，那么对于随意>0，L被一个k带(1+)n时间有界TM接受。157.2线性加速和带压缩定理7-6假如L被多带TM在时间t(n)内接受，那么L可被一个单带TM在时间t2(n)内接受。167.2线性加速和带压缩定理7-7假如L被

多带TM在时间t(n)内接受，那么L可被一个双带TM在时间 t(n)log(t(n))内接受。177.3谱系定理任何谱系中都有一些“间隙”，即存在一个函数t(n)，使得 DTIME(t2(n))=DTIME(t(n))对于任何全递归函数f，都有一个时间困难度tf(n)，使得 DTIME(tf(n))=DTIME(f(tf(n)))存在一个无穷序列的TM，它们都识别L，而其中每一个TM运行起来都比前面的快得多。187.3谱系定理定理7-8给定任何全递归的时间界限（空间界限）t(n)，存在一个递归语言L，它不在DTIME(t(n))(DSPACE(t(n)))中。证明：接受对角线方法，证明关于时间的结果。对于空间的结果接受类似的方法可以证明。因为t(n)是全递归的，故存在一个能停机的TMM来计算它。我们来构造一个TM，它接受一个语言Ｌ{0|1}*，Ｌ是递归的，但不在DTIME(t(n))中。197.3谱系定理设Xi是在{0|1}*正则依次中第i个字符串，我们可以将具有随意带字母表的ＴＭ排成序列 Ｍ1,M2,…,Mi,…现定义Ｌ＝{Xi|Mi在t(|Xi|)个动作内不接受Ｘi}，我们可以断言L是递归的。为识别L，执行下面算法：给定一个长度为n的输入w，在上模拟M，用以计算t(n)，然后确定w是否在L中。写成二进制形式的整数i是某个多带TMMi的标记。在上对Mi模拟t(n)个动作，假如Mi停机但不接受，或超过t(n)个动作还没接受，则接受w。207.3谱系定理假定L=L(Ml)且Ml是t(n)时间有界的，假如XlL，则Ml在t(n)时间内接受Xl，这里n=|Xl|，XlL。与此产生冲突。假如XlL，那么Ml不接受Xl，故依据L的定义，XlL，也产生冲突。两种假设都产生冲突，故Ml是t(n)时间有界的假定必是错误的。定理得证。■对于任何递归的时间或空间困难度函数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谱系定理空间可构造函数集包括logn、nk、2n、n!，假如s1(n)、s2(n)是空间可构造的，那么s1(n)+s2(n)、2s1(n)、和s1(n)·s2(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称一个函数t(n)是时间可构造的，假如有某个多带图灵机M，M是t(n)时间有界的，且对每个n，都存在某个长度为n的输入，对于这个输入，M实际做了t(n)个动作。267.3谱系定理定理7-10假如t2(n)是一个完全空间可构造的函数，那么有一个语言，它在DTIME(t2(n))中，而不在DTIME(t1(n))中。277.3谱系定理证明：用对角线的方法证明。构造一个t2(n)时间有界的TMM，其操作如下：因为t2(n)是一个完全空间可构造的函数，故存在一个TMM，对于任何输入长度为n的符号串，这个TM都恰好用t2(n)时间。M首先模拟这个TM的各个动作，并将步数记录在附加带上。然后把输入w作为一个TM的编码，并在这个输入上模拟，因为M的带数目是个固定的数，故对于某些w，M将比有更多的带。用二条带可以模拟，但要损失一个因子logt(n)，而且因为有很多带符号，它们必需用某个固定数目的符号进行编码，故M对的t1(n)个动作的模拟，须要Ct1(n)logt1(n)时间。这里C是一个与M有关的常数。287.3谱系定理M接受w，仅当对的模拟完成且拒绝，即有L(M)={w|以w编码为标记的TMMw在t1(n)步停机且拒绝w}。若存在TMM1，使得Ｌ(M1)=L(M),且是t1(n)有界的，则必存在一个输入w∈L(M)，它充分长，令n=|w|，有 Ct1(n)logt1(n)≤t2(n)且w的编码是Ｍ1的标记。此时，w被M1接受，当且仅当它被M1拒绝。因而L(M)在DTIME(t2(n))中，而不在DTIME(t1(n))中。297.4困难性量度间的关系及非确定谱系定理7-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))中。307.4困难性量度间的关系及非确定谱系定理7-12[Savitch定理]假如L在NSPACE(s(n))中，那么L在DSPACE(s2(n))中。这里假定s(n)是完全空间可构造的，且s(n)≥log2n。这个定理中，对于s(n)≥log2n时，要求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状况下，也有类似的结果。利用确定时间状况下的转换结果，我们可以证明 DTIME(n2)DTIME(n2n)327.4困难性量度间的关系及非确定谱系定理7-13假如>0，且r≥0,那么 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))之间有个“间隙”，没有任何语言的最小空间困难度会在这个间隙内。347.5间隙定理、加速定理定理7-15[Blum加速定理]设r(n)是随意全递归函数，存在一个递归语言L，使得对于任何一个接受L的图灵机Mi，都存在一个图灵机Mj，Mj接受L，且对几乎全部的n，r(sj(n))≤si(n)。357.6Ｐ类与ＮＰ类Ｐ类ＮＰ类ＮＰ完全性367.6.1P类定义7-12P是确定型单带图灵机在多项式时间内可判定的语言类，即对于全部与确定型单带图灵机多项式等价的计算模型来说，P是不变的；P大致对应于在计算机上实际可解的问题类。377.6.1P类【例7-8】有向图中两个节点的连通性判定问题是P类问题。证明：设有向图G=<V,E>，s,t∈V，n=|V|。不失一般性可设Ｇ是简洁图。下面是该问题的判定算法。步1标记节点s;步2重复步2.1直至不再有节点须要标记：步2.1扫描G的全部边。假如找到一条边（u,v），u、v∈V，u被标记，而v未被标记，则标记v；步3若t被标记，则接受；否则拒绝。387.6.2NP类定义7-13语言L的验证机是一个算法V，这里 A={w|对某个字符串c，V接受<w,c>}其中，c表示算法V所运用的附加信息。例如Hamilton路问题中给定的一条路的信息，算法V可以判定c是否是Hamilton路。397.6.2NP类定义7-14NP是具有多项式时间验证机的语言类。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的边，则接受；否则拒绝。407.6.2NP类定理7-16一个语言在NP中，当且仅当它能被某个非确定型多项式时间的图灵机判定。证明：首先证明若L∈NP，则存在非确定型多项式时间的图灵机判定它。因为L∈NP，所以存在L的多项式时间的验证机V，构造非确定型图灵机N如下：设输入为w，步1非确定地选择长为nk的字符串c；步2在输入<w，c>上运行V；步3若V接受，则接受；否则拒绝。417.6.2NP类下面证明若L有非确定型多项式时间的图灵机N接受它，则L∈NP。为此，构造多项式时间的验证机V如下：对于输入<w，c>，步1在输入w上模拟N，把c的每一个符号看作是对每一步所作的非确定性选择的描述；步2若N的该计算分支接受，则接受；否则拒绝。427.6.3NP完全性可满足问题:判定一个布尔表示式是否可满足.定理7-17[库克—列文定理]可满足问题属于Ｐ，当且仅当Ｐ=ＮＰ。437.6.3NP完全性定义7-15

称语言LA多项式时间映射可归约到语言LB，或简称为多项式时间可归约到LB，记为

LA≤PLB，若存在多项式时间可计算函数f：∑*∑*，对于每一个w，有

w∈LA≡f(w)∈LB称函数f为LA到LB多项式时间归约。447.6.3ＮＰ完全性定理7-18若ＬA≤PＬB，且ＬB∈P，则ＬA∈P。证明：设M是判定ＬB的多项式时间算法，f是从ＬA到ＬB的多项式时间归约。判定ＬA的多项式时间算法ＭA如下：对于输入w，步1计算f(w)；步2在输入f(w)上运行M，输出M的输出。因为w∈ＬA≡f(w)∈ＬB，又f、Ｍ都是多项式时间可计算的，所以ＭA也是多项式时间可完成的。457.6.3ＮＰ完全性定义7-16语言L是NP完全的，若它满足下面两个条件：(1)L∈NP；(2)NP中的每个LA都多项式时间可归约为L。467.6.3ＮＰ完全性定理7-19[库克—列文定理]可满足问题ＳＡＴ是ＮＰ完全的。证明:首先证明SAT属于NP。因为对于任何命题变元不确定的选取，都可以在非确定型多项式时间内得到一个赋值，当赋值满足公式时接受。下面证明NP中的每一个语言都可以多项式时间归约到SAT。477.6.3ＮＰ完全性从NP中任取一个语言L，设 MN={Q,∑,Γ,δ,q0,B,F}是nk多项式时间内判定L的非确定型图灵机，其中k是常数。对于MN的随意输入w，在多式时间内构造公式Φ，使得w∈L≡Φ∈SAT。设f是由w到Φ的归约，下面起先描述归约f。487.6.3ＮＰ完全性考虑MN在w上的执行过程。定义MN在w上的画面是一张nknk表格，其中行代表MN在输入上的一个计算分支的瞬时描述。并约定每一个ID都以“#”起先和结束。当然画面的第一行是初始ID，每一行都依据MN的转移函数从上一行得到，假如画面的某一行是接受ID，则称该画面是接受的。我们把画面nknk个的格子中每一格称为一个单元。第i行第j列的单元称为cell[i,j]，它应包含C=Q∪Γ∪{#}中的一个符号。定义变量xi,j,s497.6.3ＮＰ完全性（1≤i≤nk,1≤j≤nk,s∈C）表示单元中的内容。xi,j,s=1，意味着cell[i,j]包含s。现在设计公式Φ，使得变量的一个满足赋值的确对应MN在Φ上的一个接受画面。为此要满足以下4点：(1)每个单元只能包含一个符号；(2)第一行为初始ID(3)存在接受ID(4)表的每一行都对应于从上一行的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包含固定长度的公式片段，故