计算理论基础章7

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),求一条路径，每个节点在其中出现且只出现一次。