计算理论导引8空间复杂性

《计算理论导引8空间复杂性》由会员分享，可在线阅读，更多相关《计算理论导引8空间复杂性（48页珍藏版）》请在金锄头文库上搜索。

1、1,计算理论,第8章 空间复杂度,2,主要内容,8.1 萨维奇定理 8.2 PSPACE 类 8.3 PSPACE 完全性 8.3.1 TQBF问题 8.3.2 博弈的必胜策略 8.3.3 广义地理学 8.4 L 类 NL 类 8.5 NL 完全性 8.6 NL 等于 coNL,空间复杂度,如果 M 是对所有输入在所有分支上都停机的非确定型图灵机，则定义它的空间复杂度 f (n) 为 M 在任何长为 n 的输入上，在任何计算分支上所扫描的带方格的最大数。 通常用渐进记法估计图灵机的空间复杂度。,空间复杂性类,定义8.2,令 f : NR+是一个函数，空间复杂性类 SPACE(f(n)和 NSP

2、ACE(f(n)定义如下：,SPACE(f(n) = L | L是被 O(f(n) 空间的确定型图灵机判定的语言 NSPACE(f(n) = L | L是被 O(f(n) 空间的非确定型图灵机判定的语言,例8.3,例8.3 证明用线性空间算法能求解 SAT 问题。,M1 = “对输入， 是布尔公式： 1) 对于 中变量 x1 , , xm 的每个真值赋值： 2) 计算 在该真值赋值下的值。 3) 若 的值为 1，则接受；否则拒绝。”,显然机器 M1 是在线性空间内运行，因为每一次循环都可以复用带子上的同一部分。该机器只需存储当前的真值赋值，这只需消耗 O(m) 空间。因为变量数 m 最多是输入

3、长度 n，所以该机器在空间 O(n) 内运行。,例：语言的非确定性空间复杂性,例8.4 令 ALLNFA | A 是一个 NFA 且 L(A) = * ,首先给出非确定型线性空间算法来判定该语言的补 ALLNFA 。 算法的思想是利用非确定性猜测一个被 NFA 拒绝的字符串，然后用线性空间跟踪该 NFA，看它在特定时刻处在什么状态。 需要注意的是，此时还不知道该语言是否在 NP 或 coNP 中。,N“对于输入 ，M 是 NFA： 1) 置标记于 NFA 的起始状态。 2) 重复执行下面的语句 2q 次，这里 q 是 M 的状态数。 3) 非确定地选择一个输入符号并移动标记到 M 的相 应状态

4、，来模拟读取那个符号。 4) 如果步骤 2 和 3 表明 M 拒绝某些字符串，即如果在某一时刻所有标记都不落在 M 的接受状态上，则接受；否则拒绝。”,例：语言的非确定性空间复杂性,7,如果 M 拒绝某个字符串，则它必定拒绝一个长度不超过 2q 的字符串，因为在任何被拒绝的更长的字符串中，上面算法中所描述的标记的位置分布必定重复出现。介于两次重复出现之间的那一段字符串可以删去，从而得到更短的被拒绝的字符串。所以 N 可判定 ALLNFA 的补。 该算法仅需要的空间是用来存放标记的位置和重复计数器，这在线性空间就可以得到解决。因此，该算法在非确定的空间 O(n) 内运行。,萨维奇定理,给定 NT

5、M 的两个格局 c1 和 c2，以及一个整数 t，要求判定该NTM 能否在 t 步内从 c1 变到 c2，称该问题为可产生性问题。 如果 c1 是起始格局，c2 是接受格局，t 是非确定型机器所使用的最大步数，那么通过求解可产生问题，就能够判断机器是否接受输入。 可以用一个确定的递归算法求解可产生问题。运算过程如下： 寻找一个中间格局 cm，递归地检查 c1 能否在 t/2 步内到达 cm， cm 能否在 t/2步内到达 c2，重复使用两次递归检查的空间可节省空间开销。 递归的每一层需要 O(f(n)空间来存储一个格局。递归的深度是 log t，t 是非确定型机器在所有分支上可能消耗的最大时间

6、，t=2O(f(n)，log t = O(f(n)。 因此模拟过程需要 O(f 2(n)。,萨维奇定理的证明,设 N 是在空间 f(n) 内判定语言 A 的 NTM。 构造一个判定 A 的确定型 TM M。机器 M 利用过程 CANYIELD，该过程检查 N 的一个格局能否在指定的步数内产生另一个格局。 设 w 是输入到 N 的字符串。对于 N 在 w 上的格局 c1、c2 以及整数 t，如果从格局 c1 出发，N 有一系列非确定的选择能使它在 t 步内进入格局 c2 ，则CANYIELD (c1 , c2 , t) 输出接受，否则，CANYIELD 输出拒绝。,CANYIELD = “对输入

7、 c1, c2 和 t： 1) 若 t=1，则直接检查是否有 c1=c2 ，或者根据 N 的规则检查 c1 能否在一步内产生c2。如果其中之一成立，则接受；如果两种情况都不成立，则拒绝。 2) 若 t 1，则对于 N 在 w上消耗空间 f(n) 的每一个格局cm： 3) 运行 CANYIELD (c1 , cm , t /2 )。 4) 运行 CANYIELD (cm , c2 , t /2 )。 5) 若第 3 和第 4 步都接受，则接受。 6) 若此时还没有接受，则拒绝。”,萨维奇定理的证明,现在定义 M 来模拟 N。首先修改 N，当它接受时，把带子清空并把读写头移到最左边的单元，从而进入

8、称为 caccept 的格局。 令 cstart 是 N 在 w 上的起始格局。选一个常数 d，使得 N 在 f(n) 空间上的格局数不超过 2df(n) ，其中 n 是 w 的长度。 2df(n) 是 N 在所有分支上的运行时间的上界。 M“对输入 w： 1) 输出 CANYIELD (cstart， caccept，2df(n) )的结果。” 算法 CANYIELD 显然求解了可产生性问题，因此 M 正确地模拟 N。 下面需要分析 M，确信它在 O(f(n)空间内运行。 CANYIELD 在递归调用自己时，它都把所处的步骤号、c1、c2 和 t 的都存储在栈中，所以递归调用时返回时能恢复这

9、些值。因此在递归的每一层需要增加 O(f(n) 空间。 此外，递归的每一层把 t 的值减小一半。开始时 t 等于2df(n) ，所以递归的深度是 O(log 2df(n) 或 O(f(n) ，因此共消耗空间是 O(f2(n) 。,11,主要内容,8.1 萨维奇定理 8.2 PSPACE 类 8.3 PSPACE 完全性 8.3.1 TQBF 问题 8.3.2 博弈的必胜策略 8.3.3 广义地理学 8.4 L 类 NL 类 8.5 NL 完全性 8.6 NL 等于 coNL,PSPACE 类,PSPACE 类的非确定型版本 NPSPACE，可以类似地用NSPACE 类来定义。 然而，任何多项式

10、的平方仍是多项式，根据萨维奇定理，则NPSPACE = PSPACE 。 在例8.3和8.4中，已经说明了 SAT 属于 SPACE(n)， ALLNFA 属于 coNSPACE(n) ，而根据萨维奇定理，确定型空间复杂度对补运算封闭，所以 ALLNFA 也属于 SPACE(n2) 。因此 SAT 和ALLNFA 这两个语言都在 PSPACE 中。,PSPACE 类,考察 PSPACE 与 P 和 NP 的关系。 显而易见，P PSPACE，因为运行快的机器不可能消耗大量的空间。更精确地说，当 t(n)n 时，由于在每个计算步上最多能访问一个新单元，因此，任何在时间 t(n) 内运行的机器最多

11、能消耗 t(n) 的空间。 类似地，NP NPSPACE ，所以 NP PSPACE 。 反过来，根据图灵机的空间复杂性可以界定它的时间复杂性。 对于 f (n )n ，通过简单推广引理5.7 的证明可知，一个消耗f(n) 空间的 TM 至多有 f(n)2O(f(n) 个不同的格局，也必定在时间 f(n)2O(f(n) 内运行，得出： PSPACE EXPTIME = k TIME(2nk),P NP PSPACE=NPSPACE EXPTIME,14,主要内容,8.1 萨维奇定理 8.2 PSPACE 类 8.3 PSPACE 完全性 8.3.1 TQBF 问题 8.3.2 博弈的必胜策略

12、8.3.3 广义地理学 8.4 L 类 NL 类 8.5 NL 完全性 8.6 NL 等于 coNL,PSPACE 完全性,TQBF 问题,量词： 、 对于自然数，语句 x x+1x 为真。 y y+y=y 为假。 辖域：量词的作用范围。 前束范式： 形如 = Q1x1 Q2 x2 Qk xk B， Qi 为或 量词化布尔公式：带量词的布尔公式（必须是前束范式）。 全量词化：公式中的每个变量都出现在某一量词的辖域中。 TQBF 问题就是要判定一个全量词化的布尔公式是真是假。 TQBF=| 是真的全量词化的布尔公式,TQBF 问题,证明思路 (1) 为了证明TQBF属于PSPACE，给出一个简单

13、的算法。该算法首先给变量赋值，然后递归地计算公式在这些值下的真值。从这些信息中算法就能确定原量化公式的真值。 (2) 为了证明PSPACE中的每个语言A在多项式时间内可归约到TQBF，从判定 A 的多项式空间界限图灵机开始。然后给出多项式时间归约，它把一个字符串映射为一个量词化的布尔公式， 模拟机器对这个输入的计算。公式为真的充分必要条件是机器接受。 改用一种与萨维奇定理的证明相关的技术来构造公式。该公式把画面分成两半，利用全称量词的功能，用公式的同一部分来代表每一半。结果产生短得多的公式。,TQBF 问题,首先，给出一个判定 TQBF 的多项式空间算法： T “对输入 ， 是一个全量词化的布

14、尔公式： 1) 若 不含量词，则它是一个只有常数的表达式。计算 的值，若为真，则接受；否则，拒绝。 2) 若 等于 x ，在 上递归地调用 T，首先用 0 替换 x，然后用 1 替换 x。只要有一个结果是接受，则接受；否则，拒绝。 3) 若 等于 x ，在 上递归地调用 T，首先用 0 替换 x，然后用 1 替换 x。若两个结果都能接受，则接受；否则，拒绝。” 算法 T 显然判定 TQBF 。 空间复杂性：它递归的深度最多等于变量的个数。在每一层只需存储一个变量的值，所以全部空间消耗是 O(m)，其中 m 是 中出现的变量的个数。因此 T 在线性空间内运行。,TQBF 问题,下面，证明 TQB

15、F 是 PSPACE 难的。 设 A 是一个由 TM M 在 nk 空间内判定的语言，k 是某个常数。 下面给出一个从 A 到 TQBF 的多项式时间归约。该归约把字符串 w 映射为一个量词化的布尔公式 ， 为真当且仅当 M 接受 w。 为了说明怎样构造 ，需解决一个更一般的问题。利用两个代表格局的变量集合 c1 和 c2 及一个数 t 0，构造一个公式 c1, c2 , t。如果把 c1 和c2 赋为实际的格局，则该公式为真当且仅当 M 能够在最多 t 步内从 c1到达 c2。然后，可以令 是公式 cstart , caccept, h，其中 h= 2df(n) ，d 是一个选取的常数，使得

16、 M 在长为 n 的输入上可能的格局数不超过 2df (n) 。这里，令f(n)=nk。为了方便，假设 t 是 2 的幂。 类似库克-列文定理的证明，该公式对带单元的内容编码。对应于单元的可能设置，每个单元有几个相关的变量，每个带符号和状态有一个变量。每个格局有nk个单元，所以用 O(nk) 个变量编码。,TQBF问题,若 t=1，则容易构造 c1, c2 , t。 设计公式，使之表达要么 c1 等于 c2，要么 c1能在 M 的一步内变到 c2 。 为了表达相等性，使用一个布尔表达式来表示：代表 c1 的每一个变量与代表 c2 的相应变量包含同样的布尔值。 为表达第二种可能性，采用库克-列文定理的证明中给出的技巧，构造布尔表达式表示，代表 c1 的每个三元组的值能正确产生相应的 c2 的三元组的值，从而就能够表达 c1 在 M