1、126.1 图灵机计算复杂性量度 复杂性的量度 复杂性量度的记法 算法分析 复杂性类36.1 图灵机计算复杂性量度 6.1.1 复杂性的量度 1空间复杂度2时间复杂性3巡回复杂性46.1.1 复杂性的量度 1空间复杂度定义定义6-1 令M是一个对于所有输入都停机的离线图灵机，s：NN是一个函数。如果对于每个长度为n的输入字，M在任一条存贮带（或工作带）上至多扫视s(n) 个单元，那么称M是s(n)空间有界图灵机，或称M具有空间复杂度s(n)。56.1.1 复杂性的量度 2时间复杂性定义定义6-2 设M是一个对于所有输入都停机的确定图灵机，t：NN是一个函数。如果对于每个长度为n的输入，M在停机
2、前最多做t(n)动作（步骤），那么就称M是一个t(n)时间有界的图灵机，或称M具有时间复杂度t(n)。66.1.1 复杂性的量度 3巡回复杂性定义定义6-3 TM M对于给定的输入w ，其运行的周相为（0, i1）,（i1, i2）,（i2, i3）,（ir-2, ir-1），则称0，i1， i2，ir-1，是一个有限周相的划分，数r称为该划分的巡回数。76.1.2 复杂性量度的记法 定义定义6-4 设f和g是两个函数，f、g：NR+。如果 则称f(n)=O(g(n)。此时，g(n)是f(n)渐近增长的一个上界。86.1.2 复杂性量度的记法 定义定义6-5 设f和g是两个函数，f、g：NR+
3、，称f(n)=o(g(n)，如果有 96.1.2 复杂性量度的记法【例【例6-3】不难验证下面各式具有o关系： n2=o(n3) n=o(nloglogn) nlogn=o(n2) 106.1.2 复杂性量度的记法6-66-6116.1.3 算法分析 【例【例6-46-4】 考虑接受语言 L = WCWR |W0|1* 的图灵机的复杂性。语言L具有时间复杂度(n)，因为存在一个图灵机M，它具有两条带，并把C左边的内容复制到第二条带上，然后当遇到C时，M第二带的读头向左，经过它刚刚复制的字符串，回至第二带的开始位置，向右比较输入带C右侧的字符和第二带的字符，如果每对字符都相同，且C左边的符号数相
4、等，那么M接受。易见，如果输入长度是n，则M最多做n+1个动作。126.1.3 算法分析 【例【例6-46-4】 考虑接受语言 L = WCWR |W0|1* 的图灵机的复杂性。存在另一个图灵机M2，它接受L，具有空间复杂度log2n。M2用二条工作带来作二进制计数器，首先，检查输入，看看是否只出现一个C，以及C左边和右边的符号数是否相等。然后，逐个字符地比较C左边和右边的字，同时用上述计数器找出对应的符号，如果它们不一致，M2停机且不接受，如果所有的符号都一致，M2就接受。136.1.3 算法分析【例【例6-56-5】 自然数的二进制表示转变为一进制表示。图灵机T1的设计如下：设输入为：a0
5、a1a2an-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）。146.1.4 复杂性类 定义定义6-66-6 设t:NN是一个函数，定义时间复杂性类DTIME(t(n)为DTIME(t(n)=L|L是由一个由O(t(n)时间的图灵机识别的语言。 定义定义6-76-7
6、 设s:NN是一个函数，定义空间复杂性类DSPACE(s(n)为DSPACE(s(n)=L|L是由一个由O(s(n)空间的图灵机识别的语言。156.1.4 复杂性类 定义定义6-86-8 设t:NN是一个函数，定义非确定时间复杂性类NTIME(t(n)为NTIME(t(n)=L|L是由一个由O(t(n)时间的非确定图灵机识别的语言。 定义定义6-96-9 设s:NN是一个函数，定义非确定空间复杂性类NSPACE(s(n)为NSPACE(s(n)=L|L是由一个由O(s(n)空间的非确定图灵机识别的语言。166.2 复杂性问题的分类 类 可归约性 多项式时间归约 类176.2.1 P类 定义定义
7、6-126-12 P是确定型单带图灵机在多项式时间内可判定的语言类，即对于所有与确定型单带图灵机多项式等价的计算模型来说，P是不变的；P大致对应于在计算机上实际可解的问题类。186.2.1 P类 P表示确定的图灵机在多项式时间(步数)内可判定的语言类。这些语言对应的问题称为P类问题，这种语言称为多项式可判定的。 例如，判定一个有向图中的两个顶点之间是否存在有向路的问题；检查两个数是否互素的问题；判定一个字符串是否为一个上下文无关语言的句子的问题都是P类问题。196.2.1 P类 【例【例6-86-8】有向图中两个节点的连通性判定问题是P类问题。证明：设有向图G= ，s, t V，n=|V|。不
8、失一般性可设是简单图。下面是该问题的判定算法。步1 标记节点s;步2 重复步2.1直至不再有节点需要标记：步2.1 扫描G的所有边。如果找到一条边（u, v），u、vV，u被标记，而v未被标记，则标记v；步3 若t被标记，则接受；否则拒绝。 206.2.2 可归约性 如何确定一个问题是属于P类的，最直接的办法就是设计一个多项式时间算法来解决这个问题。 另一种办法就是将这个问题归约到一个已知的P类问题。216.2.2 可归约性 可归约性是一个功能强大的工具,它在可计算性理论中的两个主要应用,一是根据问题的不可解程度对可接受的语言进行分类,二是证明某些重要语言的不可判定性，即通过适当的归约如何来证
9、明一个给定的语言是不可判定的。226.2.2 可归约性 称一个语言A可归约到另一个语言B：如果存在一个算法可以判定某个句子属于语言B，则存在另一个算法来判定某个句子属于语言A。236.2.2 可归约性 称语言A是映射可归约（或m-可归约）到语言B（用AmB来表示）：当存在一个全可计算函数，对于任意的x*，有： 则函数被称为A与B之间的m-归约。 使用适当的m-归约可以解决许多不可判定问题的证明。246.2.2 可归约性 引理：如果L1 mL2，并且L1是不可判定的，则L2也是不可判定的。 证明：假设存在图灵机T2判定L2,并且从L1到L2的归约函数为 。计算(x)，然后使用T2 来验证是否有(
10、x)L2，从而判定xL1，或者x L1。由于L1是不可判定的，因此T2不可能存在，L2也不能被判定。256.2.2 可归约性 例：证明语言Lhalt-e=T:T(e)停机，即计算图灵机在空句子e上停机，是不可判定的。 语言Lhalt是已知的不可判定问题，上述问题的证明可以通过语言Lhaltm-归约到语言Lhalt-e来证明。 给定任意图灵机T和任意输入x，总是存在一个图灵机T ，在T 上运行空句子，即T (e)停机，当且仅当T(x)停机。具体做法如下：T 将x存储在内部(由于x是有限的，一定可以做到)，首先将x写到输入带上，然后开始模拟T，显然这种从到T 的转换是一个m-归约。266.2.2
11、可归约性 m-归约的性质： (1)m是自反的，传递的。对于所有的语言A，B，C *， (2)对于所有的语言对A，B *276.2.2 可归约性 (3)定理：任意语言B，B，B*，对于任意的可判定语言A，AmB。 证明：用y表示B中的一个句子，z表示Bc中的一个句子(根据B的定义，y和z必然存在)，定义函数f： 由于A是可判定的，f是全的可计算函数。又： ，因此f是A到B的m归约。286.2.3 多项式时间归约 定义定义6-156-15 称语言LA多项式时间映射可归约到语言LB，或简称为多项式时间可归约到LB，记为LAP LB， 若存在多项式时间可计算函数f：* *，对于每一个w，有wLA f(
12、w)LB 称函数f为LA到LB多项式时间归约。296.2.3 多项式时间归约 定理定理6-186-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、都是多项式时间可计算的，所以A也是多项式时间可完成的。 306.2.3 多项式时间归约 例：给定一个图G=(N,E),2可着色问题需要判定一个全函数f：N1,2,存在着：当E时，f(u)f(v)。 如果不想设计一个多项式时间算法来解决该问题，那么可以
13、将其多项式时间归约到一个已知的P类问题。 为每一个节点ni赋一个布尔变量xi，对每一条边(ui,vj)，有(xixj)和(xixj),即两个变量不能同时为true或同时为false。316.2.3 多项式时间归约 定理：任意语言B，B，B*，对于任意的P类中的语言A，APB。 证明：用y表示B中的一个句子，z表示Bc中的一个句子(根据B的定义，y和z必然存在)，定义函数f： 由于A是多项式时间可判定的，f是全的多项式时间可计算函数。又： ，因此f是A到B的多项式时间归约。326.2.4 NP类 定义定义6-13 6-13 语言L的验证机是一个算法V，这里A=w| 对某个字符串c，V接受其中，c
14、表示算法V所使用的附加信息 。例如Hamilton路问题中给定的一条路的信息，算法V可以判定c是否是Hamilton路。336.2.4 NP类 定义定义6-146-14 NP是具有多项式时间验证机的语言类。 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
15、的边，若都是G的边，则接受；否则拒绝。346.2.4 NP类 定理定理6-166-16 一个语言在NP中，当且仅当它能被某个非确定型多项式时间的图灵机判定。 证明：首先证明若LNP，则存在非确定型多项式时间的图灵机判定它。因为LNP，所以存在L的多项式时间的验证机V，构造非确定型图灵机N如下：设输入为w，步1 非确定地选择长为nk的字符串c；步2 在输入上运行V；步3 若V接受，则接受；否则拒绝。356.2.4 NP类下面证明若L有非确定型多项式时间的图灵机N接受它，则LNP。为此，构造多项式时间的验证机V如下：对于输入，步1 在输入w上模拟N，把c的每一个符号看作是对每一步所作的非确定性选择的描述；步2 若N的该计算分支接受，则接受；否则拒绝。366.2.4 NP类 由于确定的图灵机是一种特殊的不确定的图灵机，所以，所有的P类问题都是NP类问题。 但是，是否所有的NP类问题都是P类问题吗?也就是说，P=NP成立吗?这个问题是理论计算机科学和当代数学中悬而未决的问题之一。 如果这两类相等，那么所有的多项式可验证的问题都将是多项式可判定的。大多数研究人员相信它们不相等。
