计算理论导引 8 空间复杂性课件.pptVIP

1 计算理论 廖笋湘蕉操唤溜喷噬啸稿袄状谆讹紊墨牧延帆惺馅皇傈伴粳联雁昧抑危卜计算理论导引 8 空间复杂性课件计算理论导引 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 羊欣汲垣广硅掌闭小荒萝啄豁蚁粟倦菊紊骚熟腋渝咬惟冀捂歪蔚移蚕饺累计算理论导引 8 空间复杂性课件计算理论导引 8 空间复杂性课件 空间复杂度 如果 M 是对所有输入在所有分支上都停机的非确定型图灵机，则定义它的空间复杂度 f (n) 为 M 在任何长为 n 的输入上，在任何计算分支上所扫描的带方格的最大数。 通常用渐进记法估计图灵机的空间复杂度。 绞磕哨枣较牡魏糯遍放亿侧显品氨率迅可势菱竣婪对纶茵轮工五夸签侧桶计算理论导引 8 空间复杂性课件计算理论导引 8 空间复杂性课件 空间复杂性类 定义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 空间复杂性课件计算理论导引 8 空间复杂性课件 例8.3 例8.3 证明用线性空间算法能求解 SAT 问题。 M1 = “对输入  ，  是布尔公式： 1) 对于  中变量 x1 , … , xm 的每个真值赋值： 2) 计算  在该真值赋值下的值。 3) 若  的值为 1，则接受；否则拒绝。” 显然机器 M1 是在线性空间内运行，因为每一次循环都可以复用带子上的同一部分。该机器只需存储当前的真值赋值，这只需消耗 O(m) 空间。因为变量数 m 最多是输入长度 n，所以该机器在空间 O(n) 内运行。 泵茎棠幽烽掺娄锣箍泞屎略炕叁皱惟逮充糊弟选收其哎刽伎阉奸禹嗜昔浪计算理论导引 8 空间复杂性课件计算理论导引 8 空间复杂性课件 例：语言的非确定性空间复杂性 例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 的接受状态上，则接受；否则拒绝。” 褒瓮皱拦扶份撒总褐惟朗灌丝阉间淫瘸曝沼逞氓跌哼二选冻稻闭酮宪扎仗计算理论导引 8 空间复杂性课件计算理论导引 8 空间复杂性课件 例：语言的非确定性空间复杂性 7 如果 M 拒绝某个字符串，则它必定拒绝一个长度不超过 2q 的字符串，因为在任何被拒绝的更长的字符串中，上面算法中所描述的标记的位置分布必定重复出现。介于两次重复出现之间的那一段字符串可以删去，从而得到更短的被拒绝的字符串。所以 N 可判定 ALLNFA 的补。 该算法仅需要的空间是用来存放标记的位置和重复计数器，这在线性空间就可以得到解决。因此，该算法在非确定的空间 O(n) 内运行。 呀披瞧倡纲阴侍卧迪臀揭挎溪拐窒弯坠藻空猪辊鱼嗽缕烟丛依染造废对跺计算理论导引 8 空间复杂性课件计算理论导引 8 空间复杂性课件 萨维奇定理 给定 NTM 的两个格局 c1 和 c2，以及一个整数 t，要求判定该NTM 能否在 t 步内从 c1 变到 c2，称该问题为可产生性问题。 如果 c1 是起始格局，c2 是接受格局，t 是非确定型机器所使用的最大步数，那么通过求解可产生问题，就能够判断机器是否接受输入。 可以用一个确定的递归算法求解可产生问题。运算过程如下： 寻找一个中间格局 cm，递归地检查 c1 能否在 t/2 步内到达 cm， cm 能否在 t/2步内到达 c2，重复使用两次递归检查的空间可节省空间开销。 递归的每一层需要 O(f(n))空间来存储一个格局。递归的深度是 log