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

1计算理论2主要内容8.1萨维奇定理8.2PSPACE类8.3PSPACE完全性8.3.1TQBF问题8.3.2博弈的必胜策略8.3.3广义地理学8.4L类NL类8.5NL完全性8.6NL等于coNL空间复杂度定义8.1令M是一个在所有输入上都停机的确定型图灵机。M的空间复杂度是一个函数f:NN，其中f(n)是M在任何长为n的输入上扫描带方格的最大数。若M的空间复杂度为f(n)，也称M在空间f(n)内运。如果M是对所有输入在所有分支上都停机的非确定型图灵机，则定义它的空间复杂度f(n)为M在任何长为n的输入上，在任何计算分支上所扫描的带方格的最大数。通常用渐进记法估计图灵机的空间复杂度。空间复杂性类定义8.2令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))空间的非确定型图灵机判定的语言}例8.3例8.3证明用线性空间算法能求解SAT问题。M1=“对输入，是布尔公式：1)对于中变量x1,…,xm的每个真值赋值：2)计算在该真值赋值下的值。3)若的值为1，则接受；否则拒绝。”显然机器M1是在线性空间内运行，因为每一次循环都可以复用带子上的同一部分。该机器只需存储当前的真值赋值，这只需消耗O(m)空间。因为变量数m最多是输入长度n，所以该机器在空间O(n)内运行。例：语言的非确定性空间复杂性例8.4令ALLNFA＝{A|A是一个NFA且L(A)=*}首先给出非确定型线性空间算法来判定该语言的补ALLNFA。算法的思想是利用非确定性猜测一个被NFA拒绝的字符串，然后用线性空间跟踪该NFA，看它在特定时刻处在什么状态。需要注意的是，此时还不知道该语言是否在NP或coNP中。N＝“对于输入M，M是NFA：1)置标记于NFA的起始状态。2)重复执行下面的语句2q次，这里q是M的状态数。3)非确定地选择一个输入符号并移动标记到M的相应状态，来模拟读取那个符号。4)如果步骤2和3表明M拒绝某些字符串，即如果在某一时刻所有标记都不落在M的接受状态上，则接受；否则拒绝。”例：语言的非确定性空间复杂性7如果M拒绝某个字符串，则它必定拒绝一个长度不超过2q的字符串，因为在任何被拒绝的更长的字符串中，上面算法中所描述的标记的位置分布必定重复出现。介于两次重复出现之间的那一段字符串可以删去，从而得到更短的被拒绝的字符串。所以N可判定ALLNFA的补。该算法仅需要的空间是用来存放标记的位置和重复计数器，这在线性空间就可以得到解决。因此，该算法在非确定的空间O(n)内运行。萨维奇定理定理8.5对于任何函数f:NR+，其中f(n)n，NSPACE(f(n))SPACE(f2(n))给定NTM的两个格局c1和c2，以及一个整数t，要求判定该NTM能否在t步内从c1变到c2，称该问题为可产生性问题。如果c1是起始格局，c2是接受格局，t是非确定型机器所使用的最大步数，那么通过求解可产生问题，就能够判断机器是否接受输入。可以用一个确定的递归算法求解可产生问题。运算过程如下：寻找一个中间格局cm，递归地检查c1能否在t/2步内到达cm，cm能否在t/2步内到达c2，重复使用两次递归检查的空间可节省空间开销。递归的每一层需要O(f(n))空间来存储一个格局。递归的深度是logt，t是非确定型机器在所有分支上可能消耗的最大时间，t=2O(f(n))，logt=O(f(n))。因此模拟过程需要O(f2(n))。萨维奇定理的证明设N是在空间f(n)内判定语言A的NTM。构造一个判定A的确定型TMM。机器M利用过程CANYIELD，该过程检查N的一个格局能否在指定的步数内产生另一个格局。设w是输入到N的字符串。对于N在w上的格局c1、c2以及整数t，如果从格局c1出发，N有一系列非确定的选择能使它在t步内进入格局c2，则CANYIELD(c1,c2,t)输出接受，否则，CANYIELD输出拒绝。CANYIELD=“对输入c1,c2和t：1)若t=1，则直接检查是否有c1=c2，或者根据N的规则检查c1能否在一步内产生c2。如果其中之一成立，则接受；如果两种情况都不成立，则拒绝。2)若t1，则对于N在w上消耗空间f(n)的每一个格局cm：3)运行CANYIELD(c1,cm,t/2)。4)运行CANYIELD(cm,c2,t/2)。5)若第3和第4步都接受，则接受。6)若此时还没有接受，则拒绝。”萨维奇定理的证明现在定义M来模拟N。首先修改N，当它接受时，把带子清空并把读写头移到最左边的单元，从而进入称为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的都存储在栈中，所以递归调用时返回时能恢复这些值。因此在递归的每一层需要增加O(f(n))空间。此外，递归的每一层把t的值减小一半。开始时t等于2df(n)，所以递归的深度是O(log2df(n))或O(f(n))，因此共消耗空间是O(f2(n))。11主要内容8.1萨维奇定理8.2PSPACE类8.3PSPACE完全性8.3.1TQBF问题8.3.2博弈的必胜策略8.3.3广义地理学8.4L类NL类8.5NL完全性8.6NL等于coNLPSPACE类定义8.6PSPACE是在确定型图灵机上、在多项式空间内可判定的语言类。换言之，PSPACE＝∪kSPACE(nk)PSPACE类的非确定型版本NPSPACE，可以类似地用NSPACE类来定义。然而，任何多项式的平方仍是多项式，根据萨维奇定理，则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)内运行的机器最多能消耗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=∪kTIME(2nk)PNPPSPACE=NPSPACEEXPTIME14主要内容8.1萨维奇定理8.2PSPACE类8.3PSPACE完全性8.3.1TQBF问题8.3.2博弈的必胜策略8.3.3广义地理学8.4L类NL类8.5NL完全性8.6NL等于coNLPSPACE完全性定义8.7语言B是PSPACE完全的。若它满足下面两个条件：1)B属于PSPACE。2)PSPACE中的每一个语言A多项式时间可归约到B。若B只满足条件2，则称它为PSPACE难的。TQBF问题量词：、对于自然数，语句x[x+1x]为真。y[y+y=y]为假。辖域：量词的作用范围。前束范式：形如=Q1x1Q2x2…QkxkB，Qi为或量词化布尔公式：带量词的布尔公式（必须是前束范式）。全量词化：公式中的每个变量都出现在某一量词的辖域中。TQBF问题就是要判定一个全量词化的布尔公式是真是假。TQBF={|是真的全量词化的布尔公式}TQBF问题定理8.8TQBF是PSPACE完全的。证明思路(1)为了证明TQBF属于PSPACE，给出一个简单的算法。该算法首先给变量赋值，然后递归地计算公式在这些值下的真值。从这些信息中算法就能确定原量化公式的真值。(2)为了证明PSPACE中的每个语言A在多项式时间内可归约到TQBF，从判定A的多项式空间界限图灵机开始。然后给出多项式时间归约，它把一个字符串映射为一个量词化的布尔公式ф，ф模拟机器对这个输入的计算。公式为真的充分必要条件是机器接受。改用一种与萨维奇定理的证明相关的技术来构造公式。该公式把画面分成两半，利用全称量词的功能，用公式的同一部分来代表每一半。结果产生短得多的公式。TQBF问题首先，给出一个判定TQBF的多项式空间算法：T＝“对输入，是一个全量词化的布尔公式：1)若不含量词，则它是一个只有常数的表达式。计算的值，若为真，则接受；否则，拒绝。2)若等于x，在上递归地调用T，首先用0替换x，然后用1替换x。只要有一个结果是接受，则接受；否则，拒绝。3)若等于x，在上递归地调用T，首先用0替换x，然后用1替换x。若两个结果都能接受，则接受；否则，拒绝。”算法T显然判定TQBF。空间复杂性：它递归的深度最多等于变量的个数。在每一层只需存储一个变量的值，所以全部空间消耗是O(m)，其中m是中出现的变量的个数。因此T在线性空间内运行。TQBF问题下面，证明TQBF是PSPACE难的。设A是一个由TMM在nk空间内判定的语言，k是某个常数。下面给出一个从A到TQBF的多项式时间归约。该归约把字符串w映射为一个量词化的布尔公式，为真当且仅当M接受w。为了说明怎样构造，需解决一个更一般的问题。利用两个代表格局的变量集合c1和c2及一个数t0，构造一个公式c1,c2,t。如果把c1和c2赋为实际的格局，则该公式为真当且仅当M能够在最多t步内从c1到达c2。然后，可以令是公式cstart,caccept,h，其中h=2df(n)，d是一个选取的常数，使得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的一步内产生c2。若t1，递归的构造c1,c2,t。作为预演，先尝试一种不太好的想法，然后再修正它。令：c1,c2,t=m1[c1,m1,t/2m1,c2,t/2]符号m1表示M的一个格局。m1是x1,...,xf的缩写，其中l=O(nk)，x1,...,xf是对m1编码的变量。所以c1,c2,t的这个构造的含义是：如果存在某个中间格局m1，使得M在至多t/2步内从c1变到m1，并且在至多t/2步内从m1变到c2，那么M就能在至多t步内从c1变到c2。然后再递归地构造c1,m1,t/2和m1,c2,t/2这两个公式。TQBF问题公式c1,c2,t具有正确值。换言之，只要M能在t步内从c1变到c2，它就是TRUE。然而，它太长了。构造过程中涉及的递归的每一层都把t的值减小一半，却把公式的长度增加了大约一倍，最后导致公式的长度大约是t，开始时t=2df(n)，所以这种方法结出的公式是指数长的。为