Chap 8 空间复杂度 可根据 提供的ＰPT素材+参考以前同学的报告， 修改成为有自己见解的讨论报告 建议： 底色用浅色（象牙白， 浅黄， 白色等） 适合色盲 色弱 观众 字体颜色选择余地大 在投影机 效果差时 也还能能看见.

Presentation on theme: "Chap 8 空间复杂度 可根据 提供的ＰPT素材+参考以前同学的报告， 修改成为有自己见解的讨论报告 建议： 底色用浅色（象牙白， 浅黄， 白色等） 适合色盲 色弱 观众 字体颜色选择余地大 在投影机 效果差时 也还能能看见."— Presentation transcript:

1 Chap 8 空间复杂度 可根据 提供的ＰPT素材+参考以前同学的报告， 修改成为有自己见解的讨论报告 建议： 底色用浅色（象牙白， 浅黄， 白色等） 适合色盲 色弱 观众 字体颜色选择余地大 在投影机 效果差时 也还能能看见

2 空间复杂度定义 定义８.1 M的空间复杂度 对于在所有输入上都停机的确定型图灵机 对于在所有输入上都停机的非确定型图灵机
f:N→N ；n为输入长度，f(n)为扫描带方格的最大数 对于在所有输入上都停机的非确定型图灵机 f:N→N ；n为输入长度，f(n)为任何计算分支上扫描带方格的最大数 实践中是存储器（内外存）消耗问题 定义８.2 SPACE(f(n))= {L|L是被O(f(n))空间的确定型TM判定的语言} NSPACE(f(n))= {L|L是被O(f(n))空间的非确定型TM判定的语言}

3 Space Can Be Reused 例８.3 NP完全问题SAT的空间复杂度 算法说明：输入<φ>， φ是布尔公式 分析
①对φ中的每个变量 xi 赋真值 ②计算φ值 ③ φ为1则接受，否则拒绝 分析 输入长度为n，所以变量个数m≤n 输入占带子n格，变量赋值占m格（且可反复使用），共占m+n≤2n格 所以空间复杂度f(n)=O(n)

4 Savitch定理 定义８.2 SPACE(f(n))= NSPACE(f(n))= 定理８.5
{L|L是被O(f(n))空间的确定型TM判定的语言} NSPACE(f(n))= {L|L是被O(f(n))空间的非确定型TM判定的语言} 定理８.5 对于任何f:N→N，f(n)>n，有： 　　SPACE( f2(n) ) Ê NSPACE( f(n) ) 说明确定图灵机在O(f2(n))的空间下能够判定的语言集合包含了非确定图灵机在O(f(n))空间下能够判定的语言集合 说明一个O(f2(n))空间下的TM可以替代O(f(n))空间下的NTM作判定８

5 Savitch定理证明思路 错误思路 TM模拟NTM的方法参见P152，定理8.10证明 广度优先的分支模拟，导致2O(f(n))的空间消耗
证明思想 可产生性问题:判定NTM能否在t步内从格局c1变到c2 如c1=cstart，c2=caccept，则可判定NTM是否接受输入 递归算法 如存在cm，使得NTM可在t/2步内c1→cm 且NTM可在t/2步内cm→c2 问题递归为两个可产生性问题，可重用空间

6 Savitch定理证明 递归函数bool CanYield(c1,c2,t)
if(t= =1 && ( c1= =c2 || c1→c2只需一步)) return true; if(t>1) { for(每个格局cm) 　{　bool r1=CanYield(c1,cm,ceil(t/2)); 　　bool r2=CanYield(cm,c2,ceil(t/2)); 　　if(r1 && r2) return true; 　} } return false; 实际上就是求CanYield(cstart,caccept, 2O(f(n))) 分析分析 递归深度log2t，t是步数，所以就是所有分支上的最大可能时间t=2O(f(n))， log2t=O(f(n)) 每递归一层，需要补充O(f(n))的空间 因此最大空间： O(f(n)) ×log2t=O(f2(n))

7 8.3.3 广义地理学 报告人：

8 主要内容 8.2 PSPACE类。 1个定义， 几个关系搞清楚（p184图9-1） 8.3 PSPACE完全性。
1个定义，理解定义和NP完全问题定义不同的内涵； TQBF及其PSAPCE完全定理证明

9 P187 PSPACE完全性 报告人：ＸXX

10 内容提要 ８.3.2 博弈的必胜策略 博奕论 定理８.10 ８.3.3 广义地理学 地理学 定理８.11

11 博奕论-The Game Theory ８.3.2 博弈的必胜策略 P187 博奕论：关于包含相互依存情况中理性行为 的研究。 日光浴者
海滩 1/4 3/4 博奕论：关于包含相互依存情况中理性行为 的研究。

12 博奕论-The Game Theory ８.3.2 博弈的必胜策略 P187
博奕论：每个游戏常有2个以上的参加者，他们（局中人）在游戏中都有自己的切身利益，每个局中人都有自己的可行行动集供自己选择，这种选择毫无疑问地会影响到其他局中人的切身利益。游戏中各个局中人理性地采取/选择自己的策略行为，使得在这种相互制约相互影响的依存关系中，尽可能提高自己的利益所得，这正是游戏理论的关键所得。 博奕论-The Game Theory

13 ８.3.2 博弈的必胜策略 P187 棋手间的对弈问题 敌我双方在作战过程中每一阶段的排兵布阵问题
特点：一招制敌，见招拆招，以静制动，主动出击，把握关节点，争取主动权等 关键：互博 最终分出胜负

14 ８.3.2 博弈的必胜策略 TQBF语言问题 表达式 P185 TQBF={<f>| f是真的全量词化布尔公式}
布尔表达式：包含布尔变量、常数0,1、布尔运算符与/或/非 量词化布尔表达式：包含存在量词和全称量词 全量词化布尔表达式（句子）：每个变量都出现在某一量词的辖域内 语言：所有真的全量词化布尔表达式的集合

15 8.3.2 博弈的必胜策略 P187 寻求一种策略，使一方只要采取一定的策略，无论对方采取什么策略，己方都能找到相应的对策，使最终的结果为己方获胜. TQBF(真全量词化布尔公式) 对于布尔值变量，值域为｛0,1｝的公式，总能找到相应的变量取值，使其语句结果=TRUE，则该公式=TRUE。

16 博奕和量词紧密相关 8.3.2 博弈的必胜策略 P187 一个量化语句一个博弈 作用:描述和解释该语句的含义 一个博弈一个量化语句
作用:理解该博弈的复杂性

17 博奕和量词紧密相关 8.3.2 博弈的必胜策略 P187 E.g. 前束范式的量词化布尔公式 f=$x1"x2$x3…Qxk[]
2名选手A,E，轮流为x1，x2，x3…xk选值

18 博奕和量词紧密相关 8.3.2 博弈的必胜策略 P187 TRUE: E胜 选手A所对应的量词 FALSE: A胜 选手E所对应的量词
对变量进行处理的语句

19 8.3.2 博弈的必胜策略 P188  E必胜： 设E：x1=1;A：x2=0;E：x3=1; =1,E赢
E.g.9.9 f1=$x1"x2$x3[(x1Úx2)Ù(x2Úx3)Ù(x2Úx3)]  E确定的变量值 A确定的变量值 设E：x1=1;A：x2=0;E：x3=1; =1,E赢 取值相反 E必胜： f2=$x1"x2$x3[(x1Úx2)Ù(x2Úx3)Ù(x2Úx3)]  A必胜： 设E：x1=1/0;A：x2=0;E：x3=1/0; =0,A赢 必胜策略 一个选手有必胜策略，如果他在博弈双方都下出最佳步骤时能赢

20 8.3.2 博弈的必胜策略 P188 判定在与某具体公式关联的公式博弈中哪方有必胜策略的问题是PSPACE完全的
令FORMULA-GAME= {<>|在与关联的公式博奕中哪一方有必 胜策略的问题}

21 定理8.10 8.3.2 博弈的必胜策略 P188 Proof思路：要证FORMULA-GAME是PSPACE 完全的
FORMULA-GAME=TQBF P185 FORMULA-GAME={<>|是真的 全量词化布尔公式}

22 8.3.2 博弈的必胜策略 P188 Proof: f1=$x1"x2$x3…[]是TRUE的条件： $x1"x2$x3, =TRUE
E必胜策略的条件：E给x1赋某值，使得对x2任意赋值，E可以给x3赋一个值，使得=TRUE 若f1="x1,x2, x3$x4 , x5 "x6 [] A先给x1,x2, x3赋值；E再给x4,x5赋值，A再给x6赋值 ∴ 当∈TQBF且∈FORMULA-GAME时成立 ∴ FORMULA-GAME=TQBF 根据定理9.8：TQBF是PSPACE完全的 ∴FORMULA-GAME是PSPACE完全的

23 地理学 8.3.3 广义地理学 P188 一种儿童游戏 选手们轮流给世界各地的城市命名
每一座选中的城市的首字母必须与前一座城市的尾字母相同，不得重复。 游戏从某指定的起始城市开始，以某方无法延续而认输为止。 E.g. 开始： Peoria PeoriaAmherstTucsonNashua… 结束：直到某方被难倒

24 8.3.3 广义地理学 P189 地理学图---有向图表示 类似成语接龙 节点是世界各地的城市

25 8.3.3 广义地理学 P189 一名选手从指定的起始节点开始,然后选手们交替地挑选节点,形成图中的一条简单路径.
按照地理学规则翻译为图表示法 一名选手从指定的起始节点开始,然后选手们交替地挑选节点,形成图中的一条简单路径. 要求是简单路径(即每个节点只能用1次)对应于要求城市不能重复. 第1个不能扩展路径的选手输掉比赛.

26 8.3.3 广义地理学 P189 广义地理学游戏样例 选手I必胜 4 7 2 1 5 9 3 8 从节点1开始，选手I先做选择 6

27 8.3.3 广义地理学 P189 广义地理学游戏样例 选手I必胜 2 1 1 1 选手I可以选节点2，3 3

28 8.3.3 广义地理学 P189 广义地理学游戏样例 选手I必胜 1 选手I选节点3 3

29 8.3.3 广义地理学 P189 广义地理学游戏样例 选手I必胜 1 5 1 1 3 节点3，选手II只有1条路径可选，即节点5

30 8.3.3 广义地理学 P189 广义地理学游戏样例 选手I必胜 1 5 1 1 3 选手II，只能选节点5

31 8.3.3 广义地理学 P189 广义地理学游戏样例 选手I必胜 从节点5出发，选手I，可以选节点6，7，8 7 1 5 1 1 3 8 6

32 8.3.3 广义地理学 P189 广义地理学游戏样例 选手I必胜 选手I，选择节点6 1 5 1 1 3 6

33 8.3.3 广义地理学 P189 广义地理学游戏样例 选手I必胜 1 5 1 1 3 6 从节点6只能到达节点3，但节点3已走过

34 8.3.3 广义地理学 P189 广义地理学游戏样例 选手I必胜 1 5 1 1 3 6 所以选手II必输 此种情况下，选手I有必胜策略

35 广义地理学游戏样例 4 7 2 1 5 9 3 8 6 8.3.3 广义地理学 选手II必胜 P189 从节点1开始，选手I先做选择
现在方向变成节点3节点6

36 8.3.3 广义地理学 P189 广义地理学游戏样例 选手II必胜 4 选手I这次选节点2 7 2 1 1 1 1 5 1 9 3 8 6

37 8.3.3 广义地理学 P189 广义地理学游戏样例 选手II必胜 选手II选节点4 4 7 2 1 1 1 1 5 1 9 3 8 6

38 8.3.3 广义地理学 P189 广义地理学游戏样例 选手II必胜 若选手I选节点5 4 7 2 1 1 1 1 5 1 9 3 8 6

39 8.3.3 广义地理学 P189 广义地理学游戏样例 选手II必胜 4 7 2 1 1 1 1 5 1 9 3 8 选手II选节点6 6

40 广义地理学游戏样例 4 7 2 1 1 1 1 5 1 9 3 8 6 8.3.3 广义地理学 选手II必胜 P189

41 8.3.3 广义地理学 P189 广义地理学游戏样例 选手II必胜 选手II选节点4 4 7 2 1 1 1 1 5 1 9 3 8 6

42 8.3.3 广义地理学 P189 广义地理学游戏样例 选手II必胜 选手I选节点7 4 7 2 1 1 1 1 5 1 9 3 8 6

43 8.3.3 广义地理学 P189 广义地理学游戏样例 选手II必胜 4 选手II选节点9 7 2 1 1 1 1 5 1 9 3 8 6

44 广义地理学游戏样例 8.3.3 广义地理学 选手II必胜 4 7 2 1 1 1 5 1 1 9 3 8 6 该情况下，选手II有必胜策略
P189 广义地理学游戏样例 节点9无后继，选手I必输 选手II必胜 4 7 2 1 1 1 5 1 1 9 3 8 6 该情况下，选手II有必胜策略

45 8.3.3 广义地理学 P190 判定在广义地理学中哪方有必胜策略的问题是PSPACE完全的 令GG=
{<G,b>|在图G上以节点b起始的广义地理学游戏中，选手I有必胜策略}

46 定理8.11 8.3.3 广义地理学 P190 Proof思路：(1)∵算法在多项式空间内运行 ∴GGPSPACE
FORMULA-GAME到GG的多项式时间归约 该归约把公式博弈广义地理学图,使图上的游戏过程模拟公式博弈的游戏过程 实际上,广义地理学游戏的选手是在玩一种编码形式的公式博弈

47 8.3.3 广义地理学 P190 定理8.11 （1） I b

48 8.3.3 广义地理学 P190 定理8.11 （1） I b … 若b出度>0

49 8.3.3 广义地理学 P190 定理8.11 （1）

50 8.3.3 广义地理学 P190 定理8.11 （1）

51 8.3.3 广义地理学 P190 （1） ∵递归采用栈实现 ∴该算法在线性空间内运行

52 定理8.11 8.3.3 广义地理学 P190 (2)要证GC的PSPACE难解性 FORMULA-GAME多项式时间归约到GC
f=$x1"x2$x3… Qxk[]($开头和结尾, $/"交替) 广义地理学的实例<G,b> 选手I---选手E 选手II—选手A

53 模拟公式博弈的部分地理学图 Start:b P190 变量 对应于 选手I 选手E 路径对应变量的赋值

54 模拟公式博弈的部分地理学图 P190 路径对应变量的赋值 对应于 选手II 选手A 选手I----- 选手II------

55 模拟公式博弈的部分地理学图 选手II-------选手A 选手I----- 选手II------ P190 路径对应变量的赋值 对应于
假定的最后1个量词是$ 选手I----- 选手II------

56 模拟公式博弈的地理学图 P191 选手I选择文字 选手II选择Ci c1 c2 cm

57 模拟公式博弈的地理学图 P191 若f=FALSE，II选择不满足子句的节点，I选择的文字=FALSE，II获胜；
若f=TRUE，II选择所有子句都是TRUE文字，I获胜

58 模拟公式博弈的地理学图 P191 选手I选择文字 选手II选择Ci c1 c2 cm

59 L类和NL类

60 CONTENTS 8.4 L类和NL类 8.5 NL完全性

61 8.4 L类和NL类 线性空间复杂性界限：f(n)=n 亚线性空间复杂性界限：f(n)<n
在时间复杂性中不考虑亚线性，因为亚线性连输入都不能读完 亚线性空间复杂性中能读完全部输入，但没有足够的空间存储全部输入。解决办法是修改计算模型——包含只读带的两带图灵机。

62 两带图灵机 一条只读输入带：相当于CD_ROM 一条读写工作带：可修改。 只有工作带上被扫描的单元才构成这种图灵机的空间复杂性。

63 L类和NL类的定义 定义8.12 L是确定性图灵机在对数空间内可判定的语言类 L=SPACE(log n)
NL是非确定性图灵机在对数空间内可判定的语言类 NL=SPACE(log n) 注：指向输入的指针可以在对数空间内表示，所以考虑对数空间算法计算能力的一种方式是考虑固定输入数目的输入指针的计算能力。

64 例8.13 例8.13：A={0k1k|k>=0}是L的成员。
在对数空间空间内由于输入带是只读的，故不能删除已经匹配的0和1。用工作带存放两个计数器记录0和1 的个数，这两个计数器用二进制表示只消耗对数空间。即算法可在O(log n)空间内运行。

65 例8. 14 ：8. 2节定义的语言PATH={<G,s,t>|G是包含从s到t的有向路径的有向图}。定理8
例8.14 ：8.2节定义的语言PATH={<G,s,t>|G是包含从s到t的有向路径的有向图}。定理8.12已经证明了PATH属于P，但原来的算法消耗线性空间。现在能否找到只消耗对数空间的算法？ 目前还没有找到确定性对数空间图灵机判定PATH ，但有非确定性对数空间图灵机判定PATH，即PATH属于NL

66 非确定性对数空间图灵机判定PATH 从节点s开始运算，非确定的猜测从s到t的路经的每一步。机器在工作带上只记录每一步当前节点的位置，而不是整条路径（如果是整条路径会超出对数空间）。 机器从当前节点指向的节点中非确定的 选择下一个节点，直到达到节点t接受，或指向m步后拒绝，其中m是图的节点数。 所以PATH属于NL

67 对数空间界限的运行时间界限 f(n)空间界限的图灵机也在2O(f(n))时间内运行。这个断言在对数空间仍然成立。
定义9.15：如M是一个有单独的只读输入带的图灵机，w是输入，则M在w上的格局包含：状态、工作带、两个读写头位置。输入w不作为格局的一部分。 现在要计算M在w上的时间上限

68 M空间为f(n)，|w|=n，作为M在w上的格局数为n2O(f(n)) .
设M有c个状态 带符号g个，则可能出现在工作带上的字符串数为g f(n) 输入带上输入头有n种位置。 工作带头有f(n)中可能位置 由①②③④得到M的总格局数为cnf(n)gf(n) ，或表示为n2O(f(n))即M在w上的运行上界。 当f(n) ≥㏒n时， n2O(f(n))等于2O(f(n))

69 8.5 NL完全性 类似于P=NP是否成立，也有N=NL是否成立的问题。
前面知道PATH∈NL，但PATH∈L？我们相信PATH不属于L，但不知道如何证明。还没有证明NL中哪一个问题不属于L。 为了解决N和NL的问题，引入了NL完全NL_complete, NL完全语言是NL中最困难的语言。如果L≠NL，则所有NL完全语言就不属于L。

70 NL完全语言定义为属于NL，并且NL中的其他语言都可归约到它。
引入对数空间可归约性。

71 对数空间转换器 包含一条只读的输入带，一条只写的输出带和一条可读写的工作带。工作带可以包含O(㏒n)个符号的图灵机。
对数空间转换器M计算一个函数f：∑*-->∑*，f称为对数空间可计算函数。 f(w)是把w放在M的输入带上启动M运行，到M停机时输出带上存放的字符串。 如果语言A通过f映射可归约到B,则称A可对数空间可归约到B，记为A≤LB

72 NL完全性定义 定义8.17：语言B是NL完全的，如果 B∈NL NL中的每个A对数空间可归约到B。
定理8.18：如果A≤LB且B∈L，则A∈L。 按照定理8.25的证明思路：A的对数空间算法先通过对数空间可计算函数f将w映射为f(w)，然后用B的对数空间算法。但对数空间放不下f(w)，所以需要修改算法。

73 证明：A的机器MA不再算出整个f(w)，而是根据B的机器MB的需要计算个别符号。在模拟过程中， MA记录MB的输入头在f(w)上的位置。每一次B移动时， MA重新开始在W上计算f，除了MB所要的f(w)上的特定位置的字符以外，其他的忽略。 这就造成了重复计算，在时间复杂性方面的性能就非常低。 但好处就是在任何时候只需要存储f(w)的一个字符。即以时间换空间。 推论：9.19 若有一个NL完全语言属于L，则L=NL

74 图中的搜索c194、e298 定理8.20：PATH是NL完全的。 证明思路：
例9.14已经证明PATH是NL，现在只需证明PATH是NL难的。即必须证明NL中的每个语言A对数空间可归约到PATH 从A到PATH的对数空间归约背后的思想是构造一个图，用来表示判定A的非确定对数空间图灵机的计算过程。 归约把W映射为有一个图，图中的节点对应于NTM在w上的格局。一个节点能指向另一个节点的条件是第一个节点对应的格局能在NTM下一步产生第二个节点对应的格局。因此只要从对应初始格局的节点到对应接受格局的节点之间存在一条路经，则机器接受w。

75 证明： 设NTM M在O(㏒n)空间内判定A。给定输入w，在对数空间内构造<G,s,t>,其中有向图包含从s到t的路径当且仅当M接受w.如何构造？G的节点是M在w上的格局。对于M在w上的格局c1和c2，如果c2是M从c1出发的下一个可能的格局，则(c1,c2)是G的一条边。更精确地说，如果M的转移函数指出，c1的状态和输入带头和工作带头下的符号能产生下一个状态和带头动作，使c1变成c2，则(c1,c2)是G的一条边。节点s是M在w上的初始格局，机器被修改为只有唯一的接受格局，把该格局指定为节点s。 该映射把A映射到PATH，因为M只要接受输入，就有一个计算分支接受，这对应s到t的一条路径。反之，如果G中存在从s到t的路径，M在输入w运行时，某个计算分支必然接受，从而M接受w。 证明该归约在对数空间内运算,使用一个对数空间转器，它在输入w上输出G的一个描述。c195

76 证明:定理8.20说明NL中的任何语言对数空间可归约到PATH。回忆一下，消耗空间f(n)的图灵机在n2O(f(n))内运行，所以在对数空间内运行的的归约器也在多项式时间内运行。因此NL中的任何语言多项式时间可归约到PATH。由定理8.12知道后者属于P。又知每一个多项式时间可归约到P中的语言也在P中。证毕。

77 8.6 NL equals CONL 报告人：

78 NL equals CONL 一般认为：NP<>coNP 这里：NL＝coNL

79 Proof Idea To Show that every problem in coNL is also in NL, we show is in NL. The NL algorithm M that we present for must have an accepting computation whenever the input graph G does not contain a path from s to t. PATH={<G,s,t>} First, c is the number of nodes in G that are reachable from s. And c is provided as input to M. Later, show how to compute c.

80 Proof Idea 给定G, s, t, c 用算法M对所有G中的节点，非确定性猜是否能从s到达。
当猜u从s可到达时，M就验证它，找一条从s到u的路径，如果不能在m步内找到，则拒绝，不可达。 如果猜t可达时，拒绝，因为属于PATH. M对所有的s可达的节点计数，并验证是否等于c, 如果等于，就接受，否则，拒绝。 也就是说，M不确定性地选择不包括t的c个节点，其余的节点是s不可达，并证明之。

81 Proof Idea 给定G, s, t, c 用算法M对所有G中的节点，非确定性猜是否能从s到达。
当猜u从s可到达时，M就验证它，找一条从s到u的路径，如果不能在m步内找到，则拒绝，不可达。 如果猜t可达时，拒绝，因为属于PATH. M对所有的s可达的节点计数，并验证是否等于c, 如果等于，就接受，否则，拒绝。 也就是说，M不确定性地选择不包括t的c个节点，其余的节点是s不可达，并证明之。

82 c的计算 G有m个节点 对于i=0 tom m, Ai表示离s的最大距离为i(路径长度)的所有节点的集合， A0={s},
Am包括了所有m个节点。 ci表示Ai中节点的数量。 描述一个算法来从ci计算ci+1

83 算法描述 该算法测试所有的节点，看节点是否在Ai+1中，并对其计数。
判定一个节点v是否在Ai+1中,我们使用一个内循环来检查每个G的节点，看是否它在Ai中。如果是，则从s到该节点的路径最长为i. 对于已经验证的Ai中的节点u，算法测试(u,v)是否是G的一条边，如果是，则v∈Ai+1. 内循环结束，Ai中的节点计数如果不等于ci,则拒绝；如果等，并且v不在Ai+1,则继续下一个v.

84 算法 测试v是否在Ai+1中 M=“on input <G,s,t> 1.Let co=1 2.For i=0 to m-1
3. Let ci+1= //对Ai+1中节点计数 Let d= //d对Ai中节点计数 For each node v in G For each node u in G Nondeterministically either perform or skip these steps: Nondeterministically follow a path of lengh i from s and if none of the nodes encountered are u, reject. Increment d. If (u,v) is an edge of G, increment ci+1, Go to stage 6 If d<>ci, then reject.

85 算法 测试u是否在Ai中 M=“on input <G,s,t> 1.Let co=1 2.For i=0 to m-1
3. Let ci+1=0 Let d=0 For each node v in G For each node u in G Nondeterministically either perform or skip these steps: Nondeterministically follow a path of lengh i from s and if none of the nodes encountered are u, reject. Increment d. If (u,v) is an edge of G, increment ci+1, Go to stage 6 If d<>ci, then reject.

86 算法 找从s出发长度为i路径，如果u在其中一个路径上，则接受，否则拒绝 M=“on input <G,s,t>
1.Let co=1 2.For i=0 to m-1 3. Let ci+1=0 Let d=0 For each node v in G For each node u in G Nondeterministically either perform or skip these steps: Nondeterministically follow a path of lengh i from s and if none of the nodes encountered are u, reject. Increment d. If (u,v) is an edge of G, increment ci+1, Go to stage 6 If d<>ci, then reject.

87 算法 u在从s出发长度为i的路径上，则u属于Ai, d加1 M=“on input <G,s,t> 1.Let co=1
2.For i=0 to m-1 3. Let ci+1=0 Let d=0 For each node v in G For each node u in G Nondeterministically either perform or skip these steps: Nondeterministically follow a path of lengh i from s and if none of the nodes encountered are u, reject. Increment d. If (u,v) is an edge of G, increment ci+1, Go to stage 6 If d<>ci, then reject.

88 算法 如果(u,v)是一条边，则v属于Ai+1, 计数加1, M=“on input <G,s,t> 1.Let co=1
2.For i=0 to m-1 3. Let ci+1=0 Let d=0 For each node v in G For each node u in G Nondeterministically either perform or skip these steps: Nondeterministically follow a path of lengh i from s and if none of the nodes encountered are u, reject. Increment d. If (u,v) is an edge of G, increment ci+1, Go to stage 6 If d<>ci, then reject.

89 算法 内循环结束，但找到的节点数与ci不等，则没找完，拒绝。继续判断下一个v M=“on input <G,s,t>
1.Let co=1 2.For i=0 to m-1 3. Let ci+1=0 Let d=0 For each node v in G For each node u in G Nondeterministically either perform or skip these steps: Nondeterministically follow a path of lengh i from s and if none of the nodes encountered are u, reject. Increment d. If (u,v) is an edge of G, increment ci+1, Go to stage 6 If d<>ci, then reject.

90 12. For each node u in G Nondeterministically either perform or skip these steps: Nondeterministically follow a path of lengh i from s and if none of the nodes encountered are u, reject. if u=t, reject. Increment d. 17.If d<>cm, then reject; otherwise accept.

91 Summaries The relationships among several complexity classes as follows: