1、CS_Dept.Sichaun Univ.可计算理论Lecture for Computation TheoryBook : 计算理论导引 Introduction to the Theory of Computation Section 8.3 -8.6 PSPACE ComplexityProf : 唐常杰TangC Http:/ : Phd, MS in CS . 2000- 2009, SCUStyle : Lecture / Seminar 1CS_Dept.Sichaun Univ.可计算理论2008.5.20 ，哀悼日第二天 ，计算理论课程 复课沉痛哀悼 汶川 8.0级地震 遇难
2、同胞地动天不塌 大灾有大爱2CS_Dept.Sichaun Univ.可计算理论作者 /叶浪 那是一张熟悉的脸 是我痛失亲人后看到的最真切的笑脸 眼里闪着泪花 话里充满着力量 那一刻 我感到自己有一个强大的祖国 那是一张陌生的脸 是我埋在瓦砾下看见的最勇敢的脸 撬开了残垣 搬走了巨石 那一刻 我感到自己有一个强大的祖国 那是一张美丽的脸 是我躺在病床上看见的天使的脸 包扎我的创伤 驱走我的恐惧 那一刻， 我感到自己有一个强大的祖国 一首感人的 诗 ： 地动天不塌 ，大灾有大爱3CS_Dept.Sichaun Univ.可计算理论 那是一张慈祥的脸 是我奔离教室前看过的最镇静的脸 为了自己的学生
3、 成就了自己的永恒 那一刻 我感到自己有一个强大的祖国 那是一张年轻的脸 是我在排队长列里看到的最急切的脸 为了灾区的伤员 献出了自己的殷殷鲜血 那一刻 我感到自己有一个强大的祖国 那是一张忙碌的脸 是我在救灾一线上看到的最疲惫的脸 眼里布满血丝 来不及顾及自己的家人 那一刻 我感到有一个强大的祖国 4CS_Dept.Sichaun Univ.可计算理论 那是世上最可爱的脸 是家乡地震后不曾面见过的男男女女的脸 虽远在他乡海外 温暖的目光却紧紧地落在了我的身上 那一刻 我感到自己有一个强大的祖国 地动天不塌 大灾有大爱 我感到自己有一个强大的祖国2008年 5月 14日作于成都市抗震救灾指挥部
4、作者简介 叶浪，成都市某局副局长。在成都市抗震救灾指挥部值班期间，眼见全民一心抢灾救灾感人场面，多次泪湿双眼。他利用工作间隙，在手机上写下真实感 受。 “在抗灾这几天，我最强烈最真实的感觉，正是这首词的题目，我相信，在强大祖国的支持下，我们全民一心，众志成城，一定能够战胜灾难！ ”叶浪说。5CS_Dept.Sichaun Univ.可计算理论复习 NPC 概念 (时间复杂类）n 直 观：n NPC 即，最难缠的一群 NP，他们 “拉邦结伙、互相规约、同衰共荣 ”, 有 “繁衍能力 ”n 多伦多大学， Cook教授 ,1972 年 证明 3SAT in NPCn 3SAT作为种子，繁衍了上千个著
5、名 NPC6CS_Dept.Sichaun Univ.可计算理论PSPACE-Complete CP 190Definition 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 2, we say that it is PSPACE-hardThe definition is the same as NP-Complete只缘 身在此山中B有 繁衍力只知道 B有 繁衍力，
6、不一定 身在此山中多项式时间规约7CS_Dept.Sichaun Univ.可计算理论PSPACE-Complete CP 190Definition 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 2, we say that it is PSPACE-hardThe definition is the same as NP-Complete只缘 身在此山中B有 繁衍力
7、只知道 B有 繁衍力，不一定 身在此山中多项式时间规约8CS_Dept.Sichaun Univ.可计算理论Rule for reductionn 为什么没有多项式空间规约？H 规约的目的是，以核心为种子，繁衍其他问题H 所以要求规约务必做到简单A machine can explore at most one new cell at each step of its computation时间简单了，空间就简单了；空间简单了，时间未必简单？ 所以 空间规约意义不大9CS_Dept.Sichaun Univ.可计算理论TQBF问题 CP190 8.31n TQBF T True Q Quantifier 量词 （ for all , each ) n B- Boolean F-Formula所有的变元都在量词的范围内，称为完全量化TQBF = | is true fully quantified Boolean formula问题 ： TQBF成员籍判定问题Theorem 8.9: TQBF is PSPACE-complete量化布尔表达式10
