计算理论第6章 复杂性问题的分类.

《计算理论第6章 复杂性问题的分类.》由会员分享，可在线阅读，更多相关《计算理论第6章 复杂性问题的分类.（36页珍藏版）》请在金锄头文库上搜索。

1、第6章 复杂性问题的分类 杨 莹，冷芳玲 1 6.1 图灵机计算复杂性量度 复杂性的量度 复杂性量度的记法 算法分析 复杂性类 2 6.1 图灵机计算复杂性量度 6.1.1 复杂性的量度 1空间复杂度 2时间复杂性 3巡回复杂性 3 6.1.1 复杂性的量度 1空间复杂度 定义6-1 令M是一个对于所有输入都停机的离 线图灵机，s：NN是一个函数。如果对于 每个长度为n的输入字，M在任一条存贮带（ 或工作带）上至多扫视s(n) 个单元，那么称 M是s(n)空间有界图灵机，或称M具有空间复 杂度s(n)。 4 6.1.1 复杂性的量度 2时间复杂性 定义6-2 设M是一个对于所有输入都停机的 确

2、定图灵机，t：NN是一个函数。如果对 于每个长度为n的输入，M在停机前最多做 t(n)动作（步骤），那么就称M是一个t(n)时 间有界的图灵机，或称M具有时间复杂度t(n) 。 5 6.1.1 复杂性的量度 3巡回复杂性 定义6-3 TM M对于给定的输入w ，其运行 的周相为（0, i1）,（i1, i2）,（i2, i3）,（ir- 2, ir-1），则称0，i1， i2，ir-1，是一个有 限周相的划分，数r称为该划分的巡回数。 6 6.1.2 复杂性量度的记法 定义6-4 设f和g是两个函数，f、g：NR+。 如果 则称f(n)=O(g(n)。此时，g(n)是f(n)渐近增长 的一个上

3、界。 7 6.1.2 复杂性量度的记法 定义6-5 设f和g是两个函数，f、g：NR+，称 f(n)=o(g(n)，如果有 8 6.1.2 复杂性量度的记法 【例6-3】不难验证下面各式具有o关系： n2=o(n3) n=o(nloglogn) nlogn=o(n2) 9 6.1.2 复杂性量度的记法 6-6 10 6.1.3 算法分析 【例6-4】 考虑接受语言 L = WCWR |W0|1* 的图灵机的复杂性。 语言L具有时间复杂度(n)，因为存在一个图灵 机M，它具有两条带，并把C左边的内容复制到 第二条带上，然后当遇到C时，M第二带的读头 向左，经过它刚刚复制的字符串，回至第二带 的开

4、始位置，向右比较输入带C右侧的字符和 第二带的字符，如果每对字符都相同，且C左 边的符号数相等，那么M接受。易见，如果输 入长度是n，则M最多做n+1个动作。 11 6.1.3 算法分析 【例6-4】 考虑接受语言 L = WCWR |W0|1* 的图灵机的复杂性。 存在另一个图灵机M2，它接受L，具有空间复杂 度log2n。M2用二条工作带来作二进制计数器 ，首先，检查输入，看看是否只出现一个C， 以及C左边和右边的符号数是否相等。然后， 逐个字符地比较C左边和右边的字，同时用上 述计数器找出对应的符号，如果它们不一致， M2停机且不接受，如果所有的符号都一致， M2就接受。 12 6.1.

5、3 算法分析 【例6-5】 自然数的二进制表示转变为一进制表示。 图灵机T1的设计如下：设输入为：a0a1a2an-1(ai0,1)，则 输出为am，其中m=ai2i (i:0n-1) 。T1有两条工作带x 和y，T1的工作过程如下： （1）在x上写一个a； （2）若输入为空格，则停机； （3）若输入为1，工作带x的内容送至输出带，并把x的 内容在y上抄两遍，然后用y 的内容覆盖原x的内容，清 除y；否则若输入符号为0时，只把x的内容在y上抄两 遍，然后用y 的内容覆盖原x的内容； （4）转至步（2）。 13 6.1.4 复杂性类 定义6-6 设t:NN是一个函数，定义时间复 杂性类DTIME

6、(t(n)为 DTIME(t(n)=L|L是由一个由O(t(n)时间的 图灵机识别的语言。 定义6-7 设s:NN是一个函数，定义空间复 杂性类DSPACE(s(n)为 DSPACE(s(n)=L|L是由一个由O(s(n)空间 的图灵机识别的语言。 14 6.1.4 复杂性类 定义6-8 设t:NN是一个函数，定义非确定 时间复杂性类NTIME(t(n)为 NTIME(t(n)=L|L是由一个由O(t(n)时间的 非确定图灵机识别的语言。 定义6-9 设s:NN是一个函数，定义非确定 空间复杂性类NSPACE(s(n)为 NSPACE(s(n)=L|L是由一个由O(s(n)空间 的非确定图灵机

7、识别的语言。 15 6.2 复杂性问题的分类 类 可归约性 多项式时间归约 类 16 6.2.1 P类 定义6-12 P是确定型单带图灵机在多项式时间 内可判定的语言类，即 对于所有与确定型单带图灵机多项式等价的计算模 型来说，P是不变的； P大致对应于在计算机上实际可解的问题类。 17 6.2.1 P类 P表示确定的图灵机在多项式时间(步数) 内可判定的语言类。这些语言对应的问题 称为P类问题，这种语言称为多项式可判 定的。 例如，判定一个有向图中的两个顶点之间 是否存在有向路的问题；检查两个数是否 互素的问题；判定一个字符串是否为一个 上下文无关语言的句子的问题都是P类问 题。 18 6.

8、2.1 P类 【例6-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被标记，则接受；否则拒绝。 19 6.2.2 可归约性 如何确定一个问题是属于P类的，最直接 的办法就是设计一个多项式时间算法来解 决这个问题。 另一种办法就是将这个问题归约到一个已 知的P类问题。 20 6.2.2 可归约性 可归约性是一个功能

9、强大的工具,它在可 计算性理论中的两个主要应用,一是根据 问题的不可解程度对可接受的语言进行分 类,二是证明某些重要语言的不可判定性 ，即通过适当的归约如何来证明一个给定 的语言是不可判定的。 21 6.2.2 可归约性 称一个语言A可归约到另一个语言B：如 果存在一个算法可以判定某个句子属于语 言B，则存在另一个算法来判定某个句子 属于语言A。 22 6.2.2 可归约性 称语言A是映射可归约（或m-可归约）到 语言B（用AmB来表示）：当存在一个 全可计算函数，对于任意的x*，有 ： 则函数被称为A与B之间的m-归约。 使用适当的m-归约可以解决许多不可判 定问题的证明。 23 6.2.2

10、 可归约性 引理：如果L1 mL2，并且L1是不可判定 的，则L2也是不可判定的。 证明：假设存在图灵机T2判定L2,并且从L1 到L2的归约函数为 。计算(x)，然后使 用T2 来验证是否有(x)L2，从而判定 xL1，或者xL1。由于L1是不可判定的， 因此T2不可能存在，L2也不能被判定。 24 6.2.2 可归约性 例：证明语言Lhalt-e=T:T(e)停机，即计算图灵 机在空句子e上停机，是不可判定的。 语言Lhalt是已知的不可判定问题，上述问题的证 明可以通过语言Lhaltm-归约到语言Lhalt-e来证明 。 给定任意图灵机T和任意输入x，总是存在一个 图灵机T ，在T 上运

11、行空句子，即T (e) 停机，当且仅当T(x)停机。具体做法如下：T 将x存储在内部(由于x是有限的，一定可以做 到)，首先将x写到输入带上，然后开始模拟T， 显然这种从到T 的转换是一个m-归约 。 25 6.2.2 可归约性 m-归约的性质： (1)m是自反的，传递的。对于所有的语 言A，B，C *， (2)对于所有的语言对A，B * 26 6.2.2 可归约性 (3)定理：任意语言B，B，B*，对于任 意的可判定语言A，AmB。 证明：用y表示B中的一个句子，z表示Bc中的一 个句子(根据B的定义，y和z必然存在)，定义函 数f： 由于A是可判定的，f是全的可计算函数。又： ，因此f是A

12、到B的m归约。 27 6.2.3 多项式时间归约 定义6-15 称语言LA多项式时间映射可归 约到语言LB，或简称为多项式时间可归约 到LB，记为 LAP LB， 若存在多项式时间可计算函数f：* * ，对于每一个w，有 wLA f(w)LB 称函数f为LA到LB多项式时间归约。 28 6.2.3 多项式时间归约 定理6-18A与B是两个语言，若APB，且 BP，则AP。 证明：设M是判定B的多项式 时间算法，f是从A到 B的多项式时间归约。判定A的多项式时间算法A如 下： 对于输入w， 步1 计算f(w)； 步2 在输入f(w)上运行M，输出M的输出。 因为wA f(w) B，又f、都是多项

13、式时间可计 算的，所以A也是多项式时间可完成的。 29 6.2.3 多项式时间归约 例：给定一个图G=(N,E),2可着色问题需要判 定一个全函数f：N1,2,存在着：当 E时，f(u)f(v)。 如果不想设计一个多项式时间算法来解决该问 题，那么可以将其多项式时间归约到一个已知 的P类问题。 为每一个节点ni赋一个布尔变量xi，对每一条边 (ui,vj)，有(xixj)和(xixj),即两个变量不 能同时为true或同时为false。 30 6.2.3 多项式时间归约 定理：任意语言B，B，B*，对于任意 的P类中的语言A，APB。 证明：用y表示B中的一个句子，z表示Bc中的一 个句子(根

14、据B的定义，y和z必然存在)，定义函 数f： 由于A是多项式时间可判定的，f是全的多项式 时间可计算函数。又： ， 因此f是A到B的多项式时间归约。 31 6.2.4 NP类 定义6-13 语言L的验证机是一个算法V，这里 A=w| 对某个字符串c，V接受 其中，c表示算法V所使用的附加信息 。 例如Hamilton路问题中给定的一条路的信息，算 法V可以判定c是否是Hamilton路。 32 6.2.4 NP类 定义6-14 NP是具有多项式时间验证机的语言类。 NP类是重要的，因为它包含许多具有实际意义的问题 。如前面的Hamilton路问题，它的验证机设计如下： 对于输入图G，节点s、t

15、， 步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的边，则接受；否则拒绝。 33 6.2.4 NP类 定理6-16 一个语言在NP中，当且仅当它能 被某个非确定型多项式时间的图灵机判定。 证明：首先证明若LNP，则存在非确定型 多项式时间的图灵机判定它。因为LNP， 所以存在L的多项式时间的验证机V，构造非 确定型图灵机N如下：设输入为w， 步1 非确定地选择长为nk的字符串c； 步2 在输入上运行V； 步3 若V接受，则接受；否则拒绝。 34 6.2.4 NP类 下面证明若L有非确定型多项式时间的图灵 机N接受它，则LNP。为此，构造多项 式时间的验证机V如下： 对于输入， 步1 在输入w上模拟N，把c的每一个符号 看作是对每一步所作的非确定性选择的描 述； 步2 若N的该计算分支接受，则接受