欢迎来到天天文库
浏览记录
ID：38304837
大小：1.03 MB
页数：48页
时间：2019-06-08
《计算理论导引8空间复杂性》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、1计算理论第8章空间复杂度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:NN，其中f(n)是M在任何长为n的输入上扫描带方格的最大数。若M的空间复杂度为f(n)，也称M在空间f(n)内运。如果M是对所有输入在所有分支上都停机的非确定型图灵机，则定义它的空间复杂度f(n)为M在任何长为n的输入上，在任何计算分支上所扫描的带方格的最大数。通常用渐进记法
2、估计图灵机的空间复杂度。空间复杂性类定义8.2令f:NR+是一个函数，空间复杂性类SPACE(f(n))和NSPACE(f(n))定义如下：SPACE(f(n))={L
3、L是被O(f(n))空间的确定型图灵机判定的语言}NSPACE(f(n))={L
4、L是被O(f(n))空间的非确定型图灵机判定的语言}例8.3例8.3证明用线性空间算法能求解SAT问题。M1=“对输入<>，是布尔公式：1)对于中变量x1,…,xm的每个真值赋值：2)计算在该真值赋值下的值。3)若的值为1，则接受；否则拒绝。”显然机器M1是在线性空间内运行，因为每一次循环都可以复用带子上的同一部分。该机器
5、只需存储当前的真值赋值，这只需消耗O(m)空间。因为变量数m最多是输入长度n，所以该机器在空间O(n)内运行。例：语言的非确定性空间复杂性例8.4令ALLNFA＝{
6、A是一个NFA且L(A)=*}首先给出非确定型线性空间算法来判定该语言的补ALLNFA。算法的思想是利用非确定性猜测一个被NFA拒绝的字符串，然后用线性空间跟踪该NFA，看它在特定时刻处在什么状态。需要注意的是，此时还不知道该语言是否在NP或coNP中。N＝“对于输入，M是NFA：1)置标记于NFA的起始状态。2)重复执行下面的语句2q次，这里q是M的状态数。3)非确定地选择一个输入符号并移动标记到M的相
7、应状态，来模拟读取那个符号。4)如果步骤2和3表明M拒绝某些字符串，即如果在某一时刻所有标记都不落在M的接受状态上，则接受；否则拒绝。”例：语言的非确定性空间复杂性7如果M拒绝某个字符串，则它必定拒绝一个长度不超过2q的字符串，因为在任何被拒绝的更长的字符串中，上面算法中所描述的标记的位置分布必定重复出现。介于两次重复出现之间的那一段字符串可以删去，从而得到更短的被拒绝的字符串。所以N可判定ALLNFA的补。该算法仅需要的空间是用来存放标记的位置和重复计数器，这在线性空间就可以得到解决。因此，该算法在非确定的空间O(n)内运行。萨维奇定理定理8.5对于任何函数f:NR+，其中f(
8、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是非确定型机器在所有分支上可
9、能消耗的最大时间，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的规则
10、检查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，当它接受时，把带子清空并把读写头移到最左边的单元，从而进入称为caccept的格局。令cstart是N在w上的起始
此文档下载收益归作者所有
