计算复杂性

1第7章计算复杂性27.1图灵机计算复杂性量度7.1.1复杂性的量度1．空间复杂度2．时间复杂性3．巡回复杂性37.1.1复杂性的量度1．空间复杂度定义7-1令M是一个对于所有输入都停机的离线图灵机，s：NN是一个函数。如果对于每个长度为n的输入字，M在任一条存贮带（或工作带）上至多扫视s(n)个单元，那么称M是s(n)空间有界图灵机，或称M具有空间复杂度s(n)。47.1.1复杂性的量度2．时间复杂性定义7-2设M是一个对于所有输入都停机的确定图灵机，t：NN是一个函数。如果对于每个长度为n的输入，M在停机前最多做t(n)动作（步骤），那么就称M是一个t(n)时间有界的图灵机，或称M具有时间复杂度t(n)。57.1.1复杂性的量度3．巡回复杂性定义7-3TMM对于给定的输入w，其运行的周相为（0,i1）,（i1,i2）,（i2,i3）,…,（ir-2,ir-1）,（ir-1,），则称0，i1，i2，…，ir-1，是一个有限周相的划分，数r称为该划分的巡回数。67.1.2复杂性量度的记法定义7-4设f和g是两个函数，f、g：NR+。如果则称f(n)=O(g(n))。此时，g(n)是f(n)渐近增长的一个上界。77.1.2复杂性量度的记法定义7-5设f和g是两个函数，f、g：NR+，称f(n)=o(g(n))，如果有87.1.2复杂性量度的记法【例7-3】不难验证下面各式具有o关系：n2=o(n3)n=o(nloglogn)nlogn=o(n2)97.1.2复杂性量度的记法【例7-3】不难验证下面各式具有o关系：n2=o(n3)n=o(nloglogn)nlogn=o(n2)107.1.2复杂性量度的记法117.1.3算法分析【例7-4】考虑接受语言L={WCWR|W{0|1}*}的图灵机的复杂性。语言L具有时间复杂度Ｏ(n)，因为存在一个图灵机M，它具有两条带，并把C左边的内容复制到第二条带上，然后当遇到C时，M第二带的读头向左，经过它刚刚复制的字符串，回至第二带的开始位置，向右比较输入带C右侧的字符和第二带的字符，如果每对字符都相同，且C左边的符号数相等，那么M接受。易见，如果输入长度是n，则M最多做n+1个动作。127.1.3算法分析【例7-4】考虑接受语言L={WCWR|W{0|1}*}的图灵机的复杂性。存在另一个图灵机M2，它接受L，具有空间复杂度log2n。M2用二条工作带来作二进制计数器，首先，检查输入，看看是否只出现一个C，以及C左边和右边的符号数是否相等。然后，逐个字符地比较C左边和右边的字，同时用上述计数器找出对应的符号，如果它们不一致，M2停机且不接受，如果所有的符号都一致，M2就接受。137.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）。147.1.4复杂性类定义7-6设t:NN是一个函数，定义时间复杂性类DTIME(t(n))为DTIME(t(n))={L|L是由一个由O(t(n))时间的图灵机识别的语言}。定义7-7设s:NN是一个函数，定义空间复杂性类DSPACE(s(n))为DSPACE(s(n))={L|L是由一个由O(s(n))空间的图灵机识别的语言}。157.1.4复杂性类定义7-8设t:NN是一个函数，定义非确定时间复杂性类NTIME(t(n))为NTIME(t(n))={L|L是由一个由O(t(n))时间的非确定图灵机识别的语言}。定义7-9设s:NN是一个函数，定义非确定空间复杂性类NSPACE(s(n))为NSPACE(s(n))={L|L是由一个由O(s(n))空间的非确定图灵机识别的语言}。167.2线性加速和带压缩定理7-1如果L被一个具有k条工作带的s(n)空间有界图灵机接受，那么对于任意C0,L被一C·s(n)空间有界图灵机接受。定理7-2如果L在NSPACE(s(n))中，那么L在NSPACE(Cs(n))中，其中C0。定理7-3如果L被一个具有k条工作带的s(n)空间有界图灵机接受，那么它可以被一个具有一条工作带的空间有界图灵机接受。177.2线性加速和带压缩定理7-4[线性加速定理]如果L被一个具有k条工作带的t(n)时间有界图灵机M1接受，那么只要k1，且则L就可以被一个k带Ct(n)时间有界图灵机接受，这里C是大于0的任意数。∞=)n(tlim∞→n187.2线性加速和带压缩197.2线性加速和带压缩定理7-6如果L被多带TM在时间t(n)内接受，那么L可被一个单带TM在时间t2(n)内接受。定理7-7如果L被多带TM在时间t(n)内接受，那么L可被一个双带TM在时间t(n)log(t(n))内接受。207.3谱系定理定理7-8给定任何全递归的时间界限（空间界限）t(n)，存在一个递归语言L，它不在DTIME(t(n))(DSPACE(t(n)))中。217.3.1空间谱系定义7-10称一个函数s(n)是空间可构造的，如果有某个图灵机M，M是s(n)空间有界的，且对每个n，存在某个长度为n的输入，对于这个输入，M实际占用了s(n)个带单元。引理7-1如果L被一个s(n)≥log2n空间有界的TM接受，那么L被一个s(n)空间有界且对所有输入都能停机的TM接受。227.3.1空间谱系237.3.2时间谱系定义7-11称一个函数t(n)是时间可构造的，如果有某个多带图灵机M，M是t(n)时间有界的，且对每个n，都存在某个长度为n的输入，对于这个输入，M实际做了t(n)个动作。247.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))中。257.4复杂性量度间的关系及非确定谱系定理7-12[Savitch定理]如果L在NSPACE(s(n))中，那么L在DSPACE(s2(n))中。这里假定s(n)是完全空间可构造的，且s(n)≥log2n。【例7-7】NSPACE(logn)DSPACE(log2n)NSPACE(n2)DSPACE(n4)NSPACE(2n)DSPACE(4n)267.4复杂性量度间的关系及非确定谱系定理7-13如果0，且r≥0，那么NSPACE(nr)NSPACE())277.5间隙定理、加速定理引理7-3如果L被一个TMM接受，而Ｍ是a.e.s(n)空间有界的，那么可被一个s(n)空间有界的ＴＭ接受。引理7-4存在一个算法，对于给定的ＴＭＭ，输入长度为n和整数m，该算法能确定某个长度为n的输入，Ｍ使用单元的最大数目是否是m。287.5间隙定理、加速定理定理7-14给定任何一个全递归的函数g(n)≥n，存在一个全递归函数s(n)，使得DSPACE(s(n))=DSPACE(g(s(n)))，即在空间界限s(n)和g(s(n))之间有个“间隙”，没有任何语言的最小空间复杂度会在这个间隙内。297.5间隙定理、加速定理定理7-15[Blum加速定理]设r(n)是任意全递归函数，存在一个递归语言L，使得对于任何一个接受L的图灵机Mi，都存在一个图灵机Mj，Mj接受L，且对几乎所有的n，r(sj(n))≤si(n)。307.6P类与NP类7.6.1P类定义7-12P是确定型单带图灵机在多项式时间内可判定的语言类，即P=kk)DTIME(n317.6.2NP类定义7-13语言L的验证机是一个算法V，这里A={w|对某个字符串c，V接受w,c}其中，c表示算法V所使用的附加信息，例如Hamilton路问题中给定的一条路的信息，算法V可以判定c是否是Hamilton路。定义7-14NP是具有多项式时间验证机的语言类。327.6.2NP类定理7-16一个语言在NP中，当且仅当它能被某个非确定型多项式时间的图灵机判定。337.6.3NP完全性定理7-17[库克—列文定理]可满足问题属于P，当且仅当P=NP。定义7-15称语言LA多项式时间映射可归约到语言LB，或简称为多项式时间可归约到LB，记为LA≤PLB，若存在多项式时间可计算函数f：Σ*Σ*，对于每一个w，有wLAf(w)LB称函数f为LA到LB多项式时间归约。∈∈347.6.3NP完全性定理7-18若LA≤PLB，且LBP，则LAP。定义7-16语言L是NP完全的，若它满足下面两个条件：（1）LNP；（2）NP中的每个LA都多项式时间可归约为L。定理7-19[库克—列文定理]可满足问题SAT是NP完全的。推论7-33SAT是NP完全的。∈∈∈