把logn通改成logn否则容易误解-Read.DOCVIP

第8章 空间复杂性 (学生讨论用ＰPT素材) 作为教学科研的基本训练的一个重要环节，学生应该能根据教材，作出有自己特色的PPT发言稿. 这里提供一些素材，试图减小学生的工作难度。 PPT不能仅仅是剪报。一份好的讨论班PPT 应该有同学的理解和创新. (素材节选自教材 但不能代替教材) 从素材作PPT一般 需要用 读 --减 ---加 三个过程。 先充分阅读理解 教材， 从此素材中删去次要语句， 增加自己的心得，理解方法，解释和图形。 PPT应该突出思路，突出要点, 适当的比喻可以帮助理解。 定义8.1 令M是—个在所有输入上都停机的确定型图灵机。M的空间复杂度(space complexity) 是一个函数f ：N→N，其中f (n)是M在任何长为n的输入上扫描带方格的最大数。若M的空间复杂度为，则称M在空间内运行。 定义8.2 令f ：N→R+是一个函数。空间复杂性类SPACE（）和NSPACE（）定义如下： SPACE() = {L|L是被O(f (n))空间的确定型图灵机判定的语言} NSPACE() = {L|L是被O(f (n))空间的非确定型图灵机判定的语言} 例8.3 第7章介绍了NP完全问题SAT，现在证明用线性空间算法能求解SAT问题。因为SAT是NP完全的，所以SAT不能用多项式时间算法求解，更不能用线性时间算法求解。因为空间可以重用，而时间不能，所以空间的能力显得比时间强得多。 Ml＝“对输入＜φ＞，φ是布尔公式： 1）对于φ中变量x1，x2…，x m的每个真值赋值 2） 计算φ在该真值赋值下的值。 3）若φ的值为l，则接受；否则拒绝。” 显然机器M1是在线性空间内运行，这是因为每一次循环都可以复用带子上的同一部分。该机器只需存储当前的真值赋值，则只需要消耗O (m)空间。因为变量数m最多等于输入长度n，所以该机器在空间O(n)内运行。 例8.4 这个例子分析了一个语言的非确定性空间复杂性。在下一小节将说明测定非确定性空间复杂性后，对于测定它的确定性空间复杂性是有很大帮助的。下面分析判定一个非确定型有穷自动机是否接受所有字符串的问题。令 首先给出一个非确定型线性空间算法来判定该语言的补。算法的思想是非确定性猜测一个被NFA拒绝的字符串，然后用线性空间跟踪该NFA，看它在特定时刻会处在什么状态。需要注意的是此时还不知道该语言是否在NP或coNP中。 N=“对于输入M，M是一个NFA： 1）置标记于NFA的起始状态。 2）重复执行下面的语句2q次，这里q是M的状态数。 3） 非确定地选择一个输入符号并移动标记到M的相应状态，来模拟读取那个符号。 4）如果步骤2步骤3表明M拒绝某些字符串，即如果在某一时刻所有标记都不落在M的接受状态上，则接受；否则拒绝。” 8.1 萨维奇定理 定理8.5萨维奇定理 对于任何在8.4节，证明只要f (n)≥log( n)萨维奇定理就能成立。函数f：N 在8.4节，证明只要f (n)≥log( n)萨维奇定理就能成立。 证明思路：需要确定地模拟一个空间的NTM。最简单的方法就是逐个地尝试NTM的所有计算分支。这种模拟要求记录当前正在尝试的是哪一个分支，以便能够过渡到下一个分支。但是消耗空间的一个分支可能运行步，每一步都可能是非确定的选择。顺序地考察每一个分支要求记录某个具体分支上所做的所有选择，以便能找到下一个分支。所以该方法可能会用掉空间，超过了空间。 考虑到更具—般性的问题，这里采用了另一种不同的方法。给定NTM的两个格局c1和c2，以及一个整数t，要求判定该NTM能否在t步内从c1变到c2，称该问题为可产生性问题(yieldability problem)。如果令c1是起始格局，c2是接受格局，t是非确定型机器所使用的最大步数，那么通过求解可产生性问题，就能够判定机器是否接受输入。 下面给出一个确定的递归算法来求解可产生性问题。它的运算过程为：寻找一个中间格局cm，递归地检查c1能否在t/2步内到达cm，以及cm能否在t/2步内到达c2。重复使用两次递归检查的空间即可显著节省空间开销。 该算法需要用来存储递归栈的空间。递归的每一层需要空间来存储一个格局。递归的深度是logt，这里t是非确定型机器在所有分支上可能消耗的最大时间。因为，所以logt=。因此确定的模拟过程需要空间。 证明 设N是在空间f (n)内判定语言A的NTM。构造一个判定A的确定型TM M。机器M使用过程CANYIELD，该过程检查N的一个格局能否在指定的步数内产生另一个格局，它求解了在证明思路中所描述的可产生性问题。 设w是输入到N的字符串。对于N在w上的格局c1，c2以及整数t，如果从格局c1出发，N有一系列非确定的选择能使它在t步内进入格局c2，则输出接受，否则，