文档介绍：1 计算理论 2 主要内容萨维奇定理 PSPACE 类 PSPACE 完全性 TQBF 问题博弈的必胜策略广义地理学 L 类 NL 类 NL 完全性 NL 等于 coNL 空间复杂度定义定义令M是一个在所有输入上都停机的确定型图灵机。 M 的空间复杂度是一个函数 f : N?N,其中 f (n ) 是 M 在任何长为 n 的输入上扫描带方格的最大数。若 M 的空间复杂度为 f(n),也称 M 在空间 f(n)内运。如果 M是对所有输入在所有分支上都停机的非确定型图灵机, 则定义它的空间复杂度 f (n)为 M 在任何长为 n 的输入上,在任何计算分支上所扫描的带方格的最大数。通常用渐进记法估计图灵机的空间复杂度。空间复杂性类定义定义令 f : N?R +是一个函数, 空间复杂性类 SPACE( f(n )) 和 NSPACE( f(n ))定义如下: SPACE( f(n )) ={ L | L是被 O(f(n )) 空间的确定型图灵机判定的语言} NSPACE( f(n )) = { L | L是被 O(f(n )) 空间的非确定型图灵机判定的语言} 证明用线性空间算法能求解 SAT 问题。 M 1 = “对输入<?>,?是布尔公式: 1) 对于?中变量 x 1 , …, x m的每个真值赋值: 2)计算?在该真值赋值下的值。 3) 若?的值为 1,则接受;否则拒绝。”显然机器 M 1是在线性空间内运行,因为每一次循环都可以复用带子上的同一部分。该机器只需存储当前的真值赋值,这只需消耗 O(m ) 空间。因为变量数 m 最多是输入长度 n,所以该机器在空间 O(n ) 内运行。例: 令 ALL NFA = { <A> | A 是一个 NFA 且 L(A) = ?*} 首先给出非确定型线性空间算法来判定该语言的补 ALL NFA 。算法的思想是利用非确定性猜测一个被 NFA 拒绝的字符串,然后用线性空间跟踪该 NFA ,看它在特定时刻处在什么状态。需要注意的是,此时还不知道该语言是否在 NP 或 coNP 中。 N=“对于输入<M>,M是 NFA : 1) 置标记于 NFA 的起始状态。 2) 重复执行下面的语句 2 q 次,这里 q是M的状态数。 3) 非确定地选择一个输入符号并移动标记到 M的相应状态,来模拟读取那个符号。 4) 如果步骤 2 和3 表明 M拒绝某些字符串,即如果在某一时刻所有标记都不落在 M的接受状态上,则接受;否则拒绝。”例:语言的非确定性空间复杂性 7 如果 M 拒绝某个字符串,则它必定拒绝一个长度不超过 2 q 的字符串,因为在任何被拒绝的更长的字符串中,上面算法中所描述的标记的位置分布必定重复出现。介于两次重复出现之间的那一段字符串可以删去,从而得到更短的被拒绝的字符串。所以 N 可判定 ALL NFA 的补。该算法仅需要的空间是用来存放标记的位置和重复计数器,这在线性空间就可以得到解决。因此,该算法在非确定的空间 O(n ) 内运行。萨维奇定理定理定理对于任何函数 f : N?R + ,其中 f(n)?n, NSPACE( f(n ) ) ? SPACE( f 2(n ) ) 给定 NTM 的两个格局 c 1和c 2,以及一个整数 t,要求判定该 NTM 能否在 t 步内从 c 1 变到 c 2,称该问题为可产生性问题。如果 c 1是起始格局, c 2 是接受格局, t 是非确定型机器所使用的最大步数, 那么通过求解可产生问题,就能够判断机器是否接受输入。可以用一个确定的递归算法求解可产生问题。运算过程如下: 寻找一个中间格局 c m,递归地检查 c 1能否在 t /2 步内到达 c m,c m 能否在 t /2 步内到达 c 2,重复使用两次递归检查的空间可节省空间开销。递归的每一层需要 O(f(n ))空间来存储一个格局。递归的深度是 log t, t 是非确定型机器在所有分支上可能消耗的最大时间, t =2 O(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 上的格局 c