《10_第六章空间复杂度(2)》由会员分享，可在线阅读，更多相关《10_第六章空间复杂度(2)（63页珍藏版）》请在金锄头文库上搜索。
1、1/63,Lecture for Computation Theory,Book :计算理论导引 Introduction to the Theory of Computation Section 8.3 -8.6 PSPACE ComplexityProf : 唐常杰TangC Http:/ : Phd, MS in CS . 2000- 2009, SCUStyle : Lecture / Seminar,2/63,2008.5.20 ，哀悼日第二天 ，计算理论课程 复课沉痛哀悼 汶川 8.0级地震 遇难同胞地动天不塌 大灾有大爱,3/63,作者/叶浪那是一张熟悉的脸 是我痛失亲人后看到的
2、最真切的笑脸眼里闪着泪花 话里充满着力量那一刻 我感到自己有一个强大的祖国那是一张陌生的脸 是我埋在瓦砾下看见的最勇敢的脸撬开了残垣 搬走了巨石那一刻 我感到自己有一个强大的祖国那是一张美丽的脸 是我躺在病床上看见的天使的脸包扎我的创伤 驱走我的恐惧那一刻， 我感到自己有一个强大的祖国,一首感人的 诗： 地动天不塌 ，大灾有大爱,4/63,那是一张慈祥的脸 是我奔离教室前看过的最镇静的脸为了自己的学生 成就了自己的永恒那一刻 我感到自己有一个强大的祖国那是一张年轻的脸 是我在排队长列里看到的最急切的脸为了灾区的伤员 献出了自己的殷殷鲜血那一刻 我感到自己有一个强大的祖国那是一张忙碌的脸 是我在
3、救灾一线上看到的最疲惫的脸眼里布满血丝 来不及顾及自己的家人那一刻 我感到有一个强大的祖国,5/63,那是世上最可爱的脸 是家乡地震后不曾面见过的男男女女的脸虽远在他乡海外 温暖的目光却紧紧地落在了我的身上那一刻 我感到自己有一个强大的祖国地动天不塌 大灾有大爱我感到自己有一个强大的祖国2008年5月14日作于成都市抗震救灾指挥部作者简介叶浪，成都市某局副局长。在成都市抗震救灾指挥部值班期间，眼见全民一心抢灾救灾感人场面，多次泪湿双眼。他利用工作间隙，在手机上写下真实感 受。“在抗灾这几天，我最强烈最真实的感觉，正是这首词的题目，我相信，在强大祖国的支持下，我们全民一心，众志成城，一定能够战胜
4、灾难！”叶浪说。,6/63,复习 NPC 概念 (时间复杂类）,直 观： NPC 即，最难缠的一群NP，他们 “拉邦结伙、互相规约、同衰共荣”, 有“繁衍能力”多伦多大学，Cook教授,1972 年 证明 3SAT in NPC3SAT作为种子，繁衍了上千个著名NPC,7/63,PSPACE-Complete CP 190,Definition 8.8: A language B is PSPACE-complete if:1) B is in PSPACE, and2) For every language APSPACE, we have APB.If B merely satisfies
5、 condition 2, we say that it is PSPACE-hardThe definition is the same as NP-Complete,只缘身在此山中,B有繁衍力,只知道B有繁衍力，不一定身在此山中,多项式时间规约,8/63,PSPACE-Complete CP 190,Definition 8.8: A language B is PSPACE-complete if:1) B is in PSPACE, and2) For every language APSPACE, we have APB.If B merely satisfies condition
6、 2, we say that it is PSPACE-hardThe definition is the same as NP-Complete,只缘身在此山中,B有繁衍力,只知道B有繁衍力，不一定身在此山中,多项式时间规约,9/63,Rule for reduction,为什么没有多项式空间规约？规约的目的是，以核心为种子，繁衍其他问题所以要求规约务必做到简单A machine can explore at most one new cell at each step of its computation时间简单了，空间就简单了；空间简单了，时间未必简单？ 所以空间规约意义不大,10/6
7、3,TQBF问题 CP190 8.31,TQBF T True Q Quantifier 量词 （for all , each ) B- Boolean F-Formula所有的变元都在量词的范围内，称为完全量化TQBF = | is true fully quantified Boolean formula问题 ： TQBF成员籍判定问题,Theorem 8.9: TQBF is PSPACE-complete,量化布尔表达式,11/63,TQBF问题 CP190 8.31,TQBF T True Q Quantifier 量词 （for all , each ) B- Boolean F-
8、Formula所有的变元都在量词的范围内，称为完全量化TQBF = | is true fully quantified Boolean formula问题 ： TQBF成员籍判定问题,Theorem 8.9: TQBF is PSPACE-complete,问题,结论,12/63,TQBF问题 （CP191),证明思路： TQBF is in PSPACE（1）只緣身在此山中 （只需要多项式空间） 将每个变量都带入值递归计算公式的值（2）繁衍能力 （是 规约 的 归宿） 书上先给了一个容易想到，但行不通的思路（CP192),13/63,证明：TQBF is in PSPACE,思想可以构造公
9、式 ,通过描绘接受画面来模拟M在输入W上的计算。因为:(1) M在W上的画面宽度是O(Nk); (2)M可能运行指数长的时间所以：M的高度是nk的指数。但是：多项式归约不能产生指数长的结果。寻找另一种新的方法(采用萨维奇定理相关技术),。,M消耗的空间,14/63,证明：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
10、 ; 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 ) 都是 接受，则接受；否则，拒绝。,两次递归，深度=变量个数m =输入长度n 所以需线性空间已说明 身在此山中 （只需要多项式空间）,15/63,证明TQBF 繁衍能力 （规约 归宿）,Each APSPACE is polynomial time reduciable to TQBF,T=2,nk,开始格局,接受格局,
11、问题A的计算的空间复杂度是 nk能多项式时间规约为TQBF吗？且看下页分解,16/63,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 stateeach cell requires constant number of variableseach configuration has O(nk) cellseach
12、 configuration is encoded by O(nk) variables,17/63,TQBF问题,C1 ,C2 -格局 t - 规约步数, 不妨设t=2k从 简单到复杂 构造公式 When t = 1 , 构造一步规约 公式， 下列两种之一： c1 = c2 or c1 yields c2 in one step by wiring triples like CookLevin,递归基础,18/63,TQBF问题,递归规律,一分为二,中间格局,19/63,TQBF问题,关键”从C1 格局 到 中间格局M，再到C2格局,20/63,TQBF问题,每次递归将 t 一分为二，但是将
13、公式长度加倍，结果最终的公式长度约为 ，所以问题就严重了,费了大力，还是指数级空间， 怎么办？,21/63,TQBF问题,原来的公式，一分为二后长度加倍 我们引入格局变量c3, c4,将公式变换成 =,变成两个公式,浓缩成一个公式（以时间为代价）长度不翻倍了,这里长度只增加点线性长度,22/63,TQBF问题,递归的空间消耗每层约为O(d*f(n): 新公式的长度， 递归深度为log( ) = O(f(n)所以空间复杂度为O(f2(n),因为 一分为二,23/63,8.3.2 博弈的必胜策略 CP 193,博奕论-The Game Theory,日光浴者,海滩,1/4,3/4,博奕论：关于包含相互依存情况中理性行为 的研究。,A B两个老板 研究小店在什么地方 生意才好，最后在中间，,24/63,棋手对弈排兵布阵 特点： 见招拆招，把握关节点，争取主动权 等 互博 最终分出胜负 为什么研究？ 1 游戏有了必胜策略， 玩起来没意思了，需要修改规则 2 如果寻找必胜策略很难， 这个游戏还可以玩,
