10第六章空间复杂度(2).ppt

Lecture for Computation Theory 2008.5.20 ，哀悼日第二天 ，计算理论课程 复课沉痛哀悼 汶川 8.0级地震 遇难同胞地动天不塌 大灾有大爱 复习 NPC 概念 (时间复杂类） 直 观： NPC 即，最难缠的一群NP，他们 “拉邦结伙、互相规约、同衰共荣”, 有“繁衍能力” 多伦多大学，Cook教授,1972 年 证明 3SAT in NPC 3SAT作为种子，繁衍了上千个著名NPC PSPACE-Complete CP 190 PSPACE-Complete CP 190 Rule for reduction 为什么没有多项式空间规约？ 规约的目的是，以核心为种子，繁衍其他问题 所以要求规约务必做到简单 A machine can explore at most one new cell at each step of its computation 时间简单了，空间就简单了； 空间简单了，时间未必简单？ 所以空间规约意义不大 TQBF问题 CP190 8.31 TQBF T –True Q –Quantifier 量词 （for all , each ) B- Boolean F-Formula 所有的变元都在量词的范围内，称为完全量化 TQBF = { | is true fully quantified Boolean formula} 问题 ： TQBF成员籍判定问题 TQBF问题 CP190 8.31 TQBF T –True Q –Quantifier 量词 （for all , each ) B- Boolean F-Formula 所有的变元都在量词的范围内，称为完全量化 TQBF = { | is true fully quantified Boolean formula} 问题 ： TQBF成员籍判定问题 TQBF问题 （CP191) 证明思路： TQBF is in PSPACE （1）只緣身在此山中 （只需要多项式空间） 将每个变量都带入值 递归计算公式的值 （2）繁衍能力 （是 规约 的 归宿） 书上先给了一个容易想到，但行不通的思路（CP192) 证明：TQBF is in PSPACE 思想 可以构造公式 ,通过描绘接受画面来模拟M 在输入W上的计算。 因为:(1) M在W上的画面宽度是O(Nk); (2)M可能运行指数长的时间 所以：M的高度是nk的指数。 但是：多项式归约不能产生指数长的结果。 寻找另一种新的方法(采用萨维奇定理相关技术) 证明：TQBF is in PSPACE 1）给出一个判定TQBF多项式空间算法 T = “on input ? ,a fully quantified Boolean formula” If contains no quantifiers,（即无量词）//只能是常数T或F; { If ( it is T) accept else reject ; } Else if ф = （存在 x）Ψ， { Ψ上递归地调用T，先用0换x，后用1换x。 If (其中之一T) accept ；else reject; } else if (ф =(For all x)Ψ ) { Ψ上递归调T，首先用0替换x，然后用1替换x。若两个结果 (因 For all ) 都是 接受，则接受；否则，拒绝。} 证明TQBF 繁衍能力 （规约 归宿） Each A?PSPACE is polynomial time reduciable to TQBF A 规约 to TQBF （归宿） 回忆 The formula as in proof of CookLevin encodes contents of tape cells with variables 1 ～ c = |Q???{#}| each cell has one variable for each tape symbol and state each cell requires constant number of variables each configuration has O(nk) cells each config