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

《计算理论导引-8-空间复杂性ppt课件.ppt》由会员分享，可在线阅读，更多相关《计算理论导引-8-空间复杂性ppt课件.ppt（48页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。计算理论第8章 空间复杂度1严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。主要内容主要内容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 等于等于 coNL2严格执行突发事件上报制度、校外活动报批制度等相关规章制度

2、。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。空间复杂度定义定义定义定义8.18.1令令 M 是一个在所有输入上都停机的确定型图灵机。是一个在所有输入上都停机的确定型图灵机。M 的的空间复杂度空间复杂度是一个函数是一个函数 f:NN，其中其中 f(n)是是 M 在任何长为在任何长为 n 的输入上扫描带方格的最大数的输入上扫描带方格的最大数。若若 M 的空间复杂度为的空间复杂度为 f(n)，也称，也称 M 在空间在空间 f(n)内运。内运。如果如果 M 是对所有输入是对所有输入在所有分支上都停机在所有分支上都停机的的非确定型图灵机非确定型图灵机，则定义它的则定义它的空间复杂度空间复杂度

3、 f(n)为为 M 在任何长为在任何长为 n 的输入上，在任的输入上，在任何计算分支上所扫描的带方格的最大数何计算分支上所扫描的带方格的最大数。通常用渐进记法估计图灵机的空间复杂度。通常用渐进记法估计图灵机的空间复杂度。严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。空间复杂性类定义定义定义定义8.28.2令令 f:NR+是一个函数，是一个函数，空间复杂性类空间复杂性类 SPACE(f(n)和和 NSPACE(f(n)定义如下：定义如下：SPACE(f(n)=L|L是被是被 O(f(n)空间的空间的确定型图灵机确定型图灵机判定的语

4、言判定的语言 NSPACE(f(n)=L|L是被是被 O(f(n)空间的空间的非确定型图灵机非确定型图灵机判定的语言判定的语言 严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。例8.3例例8.3 证明用线性空间算法能求解证明用线性空间算法能求解 SAT 问题。问题。M1=“对输入对输入，是布尔公式：是布尔公式：1)对于对于 中中变量变量 x1,xm 的每个真值赋值：的每个真值赋值：2)计算计算 在该真值赋值下的值。在该真值赋值下的值。3)若若 的值为的值为 1，则接受；否则拒绝。，则接受；否则拒绝。”显然机器显然机器 M1 是在线

5、性空间内运行，因为每一次循环都是在线性空间内运行，因为每一次循环都可以复可以复用带子上的同一部分用带子上的同一部分。该机器只需存储当前的真值赋值，这只。该机器只需存储当前的真值赋值，这只需需消耗消耗 O(m)空间空间。因为变量数。因为变量数 m 最多是输入长度最多是输入长度 n，所以该，所以该机器在空间机器在空间 O(n)内运行。内运行。严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。例：语言的非确定性空间复杂性例例8.4 令令 ALLNFA|A 是一个是一个 NFA 且且 L(A)=*首先给出非确定型线性空间算法来判定该语言的补

6、首先给出非确定型线性空间算法来判定该语言的补 ALLNFA。算法的思想是利用算法的思想是利用非确定性猜测一个被非确定性猜测一个被 NFA 拒绝的字符串拒绝的字符串，然后，然后用线性空间用线性空间跟踪该跟踪该 NFA，看它在特定时刻处在什么状态。，看它在特定时刻处在什么状态。需要注意的是，此时还不知道该语言是否在需要注意的是，此时还不知道该语言是否在 NP 或或 coNP 中。中。N“对于输入对于输入，M 是是 NFA：1)置标记于置标记于 NFA 的起始状态。的起始状态。2)重复执行下面的语句重复执行下面的语句 2q 次次，这里，这里 q 是是 M 的状态数。的状态数。3)非确定地选择一个输入

7、符号并移动标记到非确定地选择一个输入符号并移动标记到 M 的相的相 应状态应状态，来模拟读取那个符号。，来模拟读取那个符号。4)如果步骤如果步骤 2 和和 3 表明表明 M 拒绝某些字符串，即如果在某一时刻所有标记拒绝某些字符串，即如果在某一时刻所有标记都不落在都不落在 M 的接受状态上，则接受；否则拒绝。的接受状态上，则接受；否则拒绝。”严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。例：语言的非确定性空间复杂性如果如果 M 拒绝某个字符串，则它必定拒绝一个长度不超过拒绝某个字符串，则它必定拒绝一个长度不超过 2q 的字符串，因

8、的字符串，因为在任何被拒绝的更长的字符串中，上面算法中所描述的标记的位置分布为在任何被拒绝的更长的字符串中，上面算法中所描述的标记的位置分布必定重复出现。介于两次重复出现之间的那一段字符串可以删去，从而得必定重复出现。介于两次重复出现之间的那一段字符串可以删去，从而得到更短的被拒绝的字符串。所以到更短的被拒绝的字符串。所以 N 可判定可判定 ALLNFA 的补。的补。该算法该算法仅需要的空间是用来存放标记的位置和重复计数器仅需要的空间是用来存放标记的位置和重复计数器，这在线性空间，这在线性空间就可以得到解决。因此，该算法在非确定的空间就可以得到解决。因此，该算法在非确定的空间 O(n)内运行。

9、内运行。7严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。萨维奇定理定理定理定理定理8.58.5对于任何函数对于任何函数 f:NR+，其中其中 f(n)n，NSPACE(f(n)SPACE(f 2(n)给定给定 NTM 的两个格局的两个格局 c1 和和 c2，以及一个整数，以及一个整数 t，要求判定该，要求判定该NTM 能否在能否在 t 步内从步内从 c1 变到变到 c2，称该问题为，称该问题为可产生性问题可产生性问题。如果如果 c1 是起始格局，是起始格局，c2 是接受格局，是接受格局，t 是非确定型机器所使用的最大步数，是非确

10、定型机器所使用的最大步数，那么通过求解可产生问题，就能够判断机器是否接受输入。那么通过求解可产生问题，就能够判断机器是否接受输入。可以用一个可以用一个确定的递归算法确定的递归算法求解可产生问题。运算过程如下：求解可产生问题。运算过程如下：寻找一个中间格局寻找一个中间格局 cm，递归地检查，递归地检查 c1 能否在能否在 t/2 步内到达步内到达 cm，cm 能否在能否在 t/2步内到达步内到达 c2，重复使用两次递归检查的空间可节省空间开销重复使用两次递归检查的空间可节省空间开销。递归的每一层需要递归的每一层需要 O(f(n)空间来存储一个格局。递归的深度是空间来存储一个格局。递归的深度是 l

11、og t，t 是非是非确定型机器在所有分支上可能消耗的最大时间，确定型机器在所有分支上可能消耗的最大时间，t=2O(f(n)，log t=O(f(n)。因此模拟过程需要因此模拟过程需要 O(f 2(n)。严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。萨维奇定理的证明设设 N 是在空间是在空间 f(n)内判定语言内判定语言 A 的的 NTM。构造一个判定构造一个判定 A 的确定型的确定型 TM M。机器。机器 M 利用过程利用过程 CANYIELD，该过程，该过程检查检查 N 的一个格局能否在指定的步数内产生另一个格局。的一个格局

12、能否在指定的步数内产生另一个格局。设设 w 是输入到是输入到 N 的字符串。对于的字符串。对于 N 在在 w 上的格局上的格局 c1、c2 以及整数以及整数 t，如果，如果从格局从格局 c1 出发，出发，N 有一系列非确定的选择能使它在有一系列非确定的选择能使它在 t 步内进入格局步内进入格局 c2，则，则CANYIELD(c1,c2,t)输出接受，否则，输出接受，否则，CANYIELD 输出拒绝。输出拒绝。CANYIELD=“对输入对输入 c1,c2 和和 t：1)若若 t=1，则直接检查是否有，则直接检查是否有 c1=c2，或者根据，或者根据 N 的规则检查的规则检查 c1 能否能否在一步

13、内产生在一步内产生c2。如果其中之一成立，则接受；如果两种情况都不。如果其中之一成立，则接受；如果两种情况都不成立，则拒绝。成立，则拒绝。2)若若 t 1，则对于，则对于 N 在在 w上消耗空间上消耗空间 f(n)的每一个格局的每一个格局cm：3)运行运行 CANYIELD(c1,cm,t/2)。4)运行运行 CANYIELD(cm,c2,t/2)。5)若第若第 3 和第和第 4 步都接受，则接受。步都接受，则接受。6)若此时还没有接受，则拒绝。若此时还没有接受，则拒绝。”严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。萨维奇定理

14、的证明现在定义现在定义 M 来模拟来模拟 N。首先修改。首先修改 N，当它接受时，把带子清空并把读写头，当它接受时，把带子清空并把读写头移到最左边的单元，从而进入称为移到最左边的单元，从而进入称为 caccept 的格局。的格局。令令 cstart 是是 N 在在 w 上的起始格局。选一个常数上的起始格局。选一个常数 d，使得，使得 N 在在 f(n)空间上的格空间上的格局数不超过局数不超过 2df(n)，其中，其中 n 是是 w 的长度。的长度。2df(n)是是 N 在所有分支上的运行时在所有分支上的运行时间的上界间的上界。M“对输入对输入 w：1)输出输出 CANYIELD(cstart，

15、caccept，2df(n)的结果。的结果。”算法算法 CANYIELD 显然求解了可产生性问题，因此显然求解了可产生性问题，因此 M 正确地模拟正确地模拟 N。下面需要分析下面需要分析 M，确信它在，确信它在 O(f(n)空间内运行。空间内运行。CANYIELD 在递归调用自己时，它都把所处的步骤号、在递归调用自己时，它都把所处的步骤号、c1、c2 和和 t 的都存的都存储在栈中，所以递归调用时返回时能恢复这些值。因此在递归的每一层需储在栈中，所以递归调用时返回时能恢复这些值。因此在递归的每一层需要增加要增加 O(f(n)空间。空间。此外，此外，递归的每一层把递归的每一层把 t 的值减小一半

16、的值减小一半。开始时。开始时 t 等于等于2df(n)，所以递归的深，所以递归的深度是度是 O(log 2df(n)或或 O(f(n)，因此共消耗空间是，因此共消耗空间是 O(f2(n)。严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。11主要内容主要内容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严格

17、执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。PSPACE 类定义定义定义定义8.68.6PSPACE 是在是在确定型确定型图灵机上、在图灵机上、在多项式空间内多项式空间内可判可判定的语言类。换言之，定的语言类。换言之，PSPACE k SPACE(nk)PSPACE 类的非确定型版本类的非确定型版本 NPSPACE，可以类似地用，可以类似地用NSPACE 类来定义。类来定义。然而，任何多项式的平方仍是多项式，根据萨维奇定理，则然而，任何多项式的平方仍是多项式，根据萨维奇定理，则NPSPACE=PSPACE。在例在例8.3和和8.4

18、中，已经说明了中，已经说明了 SAT 属于属于 SPACE(n)，ALLNFA 属属于于 coNSPACE(n)，而根据萨维奇定理，而根据萨维奇定理，确定型空间复杂度对确定型空间复杂度对补运算封闭补运算封闭，所以，所以 ALLNFA 也属于也属于 SPACE(n2)。因此。因此 SAT 和和ALLNFA 这两个语言都在这两个语言都在 PSPACE 中中。严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。PSPACE 类考察考察 PSPACE 与与 P 和和 NP 的关系。的关系。显而易见，显而易见，P PSPACE，因为，因为运行快

19、的机器不可能消耗大量运行快的机器不可能消耗大量的空间的空间。更精确地说，当。更精确地说，当 t(n)n 时，由于在每个计算步上时，由于在每个计算步上最多能访问一个新单元，因此，任何在时间最多能访问一个新单元，因此，任何在时间 t(n)内运行的内运行的机器最多能消耗机器最多能消耗 t(n)的空间。的空间。类似地，类似地，NP NPSPACE，所以，所以 NP PSPACE。反过来，反过来，根据图灵机的空间复杂性可以界定它的时间复杂性根据图灵机的空间复杂性可以界定它的时间复杂性。对于对于 f(n)n，通过简单推广引理，通过简单推广引理5.7 的证明可知，的证明可知，一个消耗一个消耗f(n)空间的空

20、间的 TM 至多有至多有 f(n)2O(f(n)个不同的格局个不同的格局，也必定在，也必定在时间时间 f(n)2O(f(n)内运行，得出：内运行，得出：PSPACE EXPTIME=k TIME(2nk)P NP PSPACE=NPSPACE EXPTIME严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。14主要内容主要内容8.1 萨维奇定理萨维奇定理8.2 PSPACE 类类8.3 PSPACE 完全性完全性8.3.1 TQBF 问题问题8.3.2 博弈的必胜策略博弈的必胜策略8.3.3 广义地理学广义地理学8.4 L 类类 N

21、L 类类8.5 NL 完全性完全性8.6 NL 等于等于 coNL严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。PSPACE 完全性定义定义定义定义8.78.7语言语言 B 是是PSPACE完全的完全的。若它满足下面两个条件：。若它满足下面两个条件：1)B 属于属于 PSPACE。2)PSPACE中的每一个语言中的每一个语言A多项式时间可归约到多项式时间可归约到B。若若 B 只满足条件只满足条件 2，则称它为，则称它为 PSPACE难的难的。严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理

22、各类违纪行为或突发事件。TQBF 问题q量词量词：、对于自然数，语句对于自然数，语句 x x+1x 为真。为真。y y+y=y 为假。为假。q辖域辖域：量词的作用范围。：量词的作用范围。q前束范式前束范式：形如形如 =Q1x1 Q2 x2 Qk xk B，Qi 为为 或或 q量词化布尔公式量词化布尔公式：带量词的布尔公式（必须是前束范式）。：带量词的布尔公式（必须是前束范式）。q全量词化全量词化：公式中的每个变量都出现在某一量词的辖域中。：公式中的每个变量都出现在某一量词的辖域中。qTQBF 问题就是要判定一个全量词化的布尔公式是真是假问题就是要判定一个全量词化的布尔公式是真是假。TQBF=|

23、是真的是真的全量词化的布尔公式全量词化的布尔公式严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。TQBF 问题定理定理定理定理8.88.8TQBF 是是 PSPACE 完全的。完全的。q证明思路证明思路(1)为了为了证明证明TQBF属于属于PSPACE，给出一个简单的算法。该算法首先给变，给出一个简单的算法。该算法首先给变量赋值，然后递归地计算公式在这些值下的真值。从这些信息中算法量赋值，然后递归地计算公式在这些值下的真值。从这些信息中算法就能确定原量化公式的真值。就能确定原量化公式的真值。(2)为了为了证明证明PSPACE中的每

24、个语言中的每个语言A在多项式时间内可归约到在多项式时间内可归约到TQBF，从，从判定判定 A 的多项式空间界限图灵机开始。然后给出多项式时间归约，它的多项式空间界限图灵机开始。然后给出多项式时间归约，它把一个字符串映射为一个量词化的布尔公式把一个字符串映射为一个量词化的布尔公式，模拟机器对这个输入模拟机器对这个输入的计算。的计算。公式为真的充分必要条件是机器接受公式为真的充分必要条件是机器接受。改用一种与萨维奇定理的证明相关的技术来构造公式。该公式把画面改用一种与萨维奇定理的证明相关的技术来构造公式。该公式把画面分成两半，利用全称量词的功能，用公式的同一部分来代表每一半。分成两半，利用全称量词

25、的功能，用公式的同一部分来代表每一半。结果产生短得多的公式。结果产生短得多的公式。严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。TQBF 问题首先，给出一个判定首先，给出一个判定 TQBF 的多项式空间算法：的多项式空间算法：T “对输入对输入，是一个全量词化的布尔公式是一个全量词化的布尔公式：1)若若 不含量词，则它是一个只有常数的表达式。计算不含量词，则它是一个只有常数的表达式。计算 的值，若为的值，若为真，则接受；否则，拒绝。真，则接受；否则，拒绝。2)若若 等于等于 x ，在，在 上递归地调用上递归地调用 T，首先用，首

26、先用 0 替换替换 x，然后用，然后用 1 替换替换 x。只要有一个结果是接受只要有一个结果是接受，则接受；否则，拒绝。，则接受；否则，拒绝。3)若若 等于等于 x ，在，在 上递归地调用上递归地调用 T，首先用，首先用 0 替换替换 x，然后用，然后用 1 替换替换 x。若。若两个结果都能接受两个结果都能接受，则接受；否则，拒绝。，则接受；否则，拒绝。”算法算法 T 显然判定显然判定 TQBF。空间复杂性：它递归的深度最多等于变量的个数。在每一层只需存储一个空间复杂性：它递归的深度最多等于变量的个数。在每一层只需存储一个变量的值，所以全部空间消耗是变量的值，所以全部空间消耗是 O(m)，其中

27、，其中 m 是是 中出现的变量的个中出现的变量的个数。因此数。因此 T 在线性空间内运行。在线性空间内运行。严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。TQBF 问题下面，证明下面，证明 TQBF 是是 PSPACE 难的。难的。设设 A 是一个由是一个由 TM M 在在 nk 空间内判定的语言空间内判定的语言，k 是某个常数。是某个常数。下面给出一个从下面给出一个从 A 到到 TQBF 的多项式时间归约。该归约的多项式时间归约。该归约把字符串把字符串 w 映射为一映射为一个量词化的布尔公式个量词化的布尔公式 ，为为真当且仅当

28、真当且仅当 M 接受接受 w。为了说明怎样构造为了说明怎样构造 ，需解决一个更一般的问题。，需解决一个更一般的问题。利用两个代表格局的变量利用两个代表格局的变量集合集合 c1 和和 c2 及一个数及一个数 t 0，构造一个公式，构造一个公式 c1,c2,t。如果把。如果把 c1 和和c2 赋为实际的赋为实际的格局，则该公式为真当且仅当格局，则该公式为真当且仅当 M 能够在能够在最多最多 t 步内从步内从 c1到达到达 c2。然后，可以。然后，可以令令 是公式是公式 cstart,caccept,h，其中其中 h=2df(n)，d 是一个选取的常数，使得是一个选取的常数，使得 M 在长在长为为

29、n 的输入上可能的格局数不超过的输入上可能的格局数不超过 2df(n)。这里，令。这里，令f(n)=nk。为了方便，假设。为了方便，假设 t 是是 2 的幂。的幂。类似库克类似库克-列文定理的证明，该公式对带单元的内容编码。对应于单元的可能列文定理的证明，该公式对带单元的内容编码。对应于单元的可能设置，每个单元有几个相关的变量，每个带符号和状态有一个变量。每个格局设置，每个单元有几个相关的变量，每个带符号和状态有一个变量。每个格局有有nk个单元，所以用个单元，所以用 O(nk)个变量编码。个变量编码。严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违

30、纪行为或突发事件。TQBF问题若若 t=1，则容易构造，则容易构造 c1,c2,t。设计公式，使之表达要么设计公式，使之表达要么 c1 等于等于 c2，要么，要么 c1能在能在 M 的一步内变到的一步内变到 c2。为了表达相等性，使用一个布尔表达式来表示：为了表达相等性，使用一个布尔表达式来表示：代表代表 c1 的每一个变量与代表的每一个变量与代表 c2 的相应变量包含同样的布尔值的相应变量包含同样的布尔值。为表达第二种可能性，采用库克为表达第二种可能性，采用库克-列文定理的证明中给出的技巧，构造布尔表列文定理的证明中给出的技巧，构造布尔表达式表示，达式表示，代表代表 c1 的每个三元组的值能

31、正确产生相应的的每个三元组的值能正确产生相应的 c2 的三元组的值，的三元组的值，从而就能够表达从而就能够表达 c1 在在 M 的一步内产生的一步内产生 c2。若若 t1，递归的构造递归的构造 c1,c2,t。作为预演。作为预演，先尝试一种不太好的想法，然后再，先尝试一种不太好的想法，然后再修正它。令：修正它。令：c1,c2,t =m1 c1,m1,t/2 m1,c2,t/2 符号符号 m1 表示表示 M 的一个格局。的一个格局。m1是是 x1,.,xf 的缩写，其中的缩写，其中 l=O(nk)，x1,.,xf 是对是对 m1 编码的变量。所以编码的变量。所以 c1,c2,t 的这个构造的含义

32、是：如果存在某个中的这个构造的含义是：如果存在某个中间格局间格局 m1，使得，使得 M 在至多在至多 t/2 步内从步内从 c1 变到变到 m1，并且在至多，并且在至多 t/2步内从步内从 m1 变到变到 c2，那么，那么 M 就能在至多就能在至多 t 步内从步内从 c1 变到变到 c2。然后再递归地构造。然后再递归地构造 c1,m1,t/2 和和 m1,c2,t/2 这两个公式。这两个公式。严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。TQBF问题公式公式 c1,c2,t 具有正确值。具有正确值。换言之，只要换言之，只要 M

33、能在能在 t 步内从步内从 c1 变到变到 c2，它就是，它就是 TRUE。然而，它太长了。构造过程中涉及的递归的每一层都把。然而，它太长了。构造过程中涉及的递归的每一层都把 t 的值减的值减小一半，却把公式的长度增加了大约一倍，最后导致公式的长度大约是小一半，却把公式的长度增加了大约一倍，最后导致公式的长度大约是 t，开始时，开始时 t=2df(n)，所以这种方法结出的公式是指数长的。，所以这种方法结出的公式是指数长的。为了缩短公式的长度，除了使用为了缩短公式的长度，除了使用 量词以外，再利用量词以外，再利用 量词。令量词。令 c1,c2,t =m1 (c3,c4)(c1,m1),(m1,c

34、2)c3,c4,t/2 新引入的变量代表格局新引入的变量代表格局 c3 和和 c4，它允许把两个递归的子公式，它允许把两个递归的子公式“折叠折叠”为一个为一个子公式，而保持原来的意思。通过写成子公式，而保持原来的意思。通过写成 (c3,c4)(c1,m1),(m1,c2)就指明了代表格局就指明了代表格局 c3 和和 c4 的变量可以分别取的变量可以分别取 c1 和和 m1 的变量的值，或者的变量的值，或者 m1和和 c2 的变量的值，结果公式的变量的值，结果公式 c3,c4,t/2 在两种情况下都为真。可以把结构在两种情况下都为真。可以把结构(c3,c4)(c1,m1),(m1,c2)替换为等

35、价的结构替换为等价的结构 x(x=y x=z)，从而得，从而得到语法正确的量化布尔公式。到语法正确的量化布尔公式。为了计算公式个为了计算公式个 cstart，caccept,h 的长度，其中的长度，其中 h=2df(n)，注意到递归增加的那，注意到递归增加的那部分公式的长度与格局的长度呈线性关系，所以长度是部分公式的长度与格局的长度呈线性关系，所以长度是O(f(n)。递归的层。递归的层数是数是log2df(n)或或 O(f(n)。所以所得到的公式的长度是。所以所得到的公式的长度是O(f 2(n)。严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行

36、为或突发事件。博弈的必胜策略q博奕论：每个游戏常有博奕论：每个游戏常有 2 个以上的参加者，他们个以上的参加者，他们(局中人局中人)在在游戏中都有自己的切身利益，每个局中人都有自己的可行行游戏中都有自己的切身利益，每个局中人都有自己的可行行动集供自己选择，这种选择毫无疑问地会影响到其他局中人动集供自己选择，这种选择毫无疑问地会影响到其他局中人的切身利益。游戏中各个局中人理性地采取的切身利益。游戏中各个局中人理性地采取/选择自己的策选择自己的策略行为，使得在这种相互制约相互影响的依存关系中，尽可略行为，使得在这种相互制约相互影响的依存关系中，尽可能提高自己的利益所得，这正是游戏理论的关键所得。能

37、提高自己的利益所得，这正是游戏理论的关键所得。q要点：要点：博奕的各方都是理性的博奕的各方都是理性的各人的选择都是为取得利益的最大化各人的选择都是为取得利益的最大化严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。囚徒困境q1950年，就职于兰德公司的梅里尔年，就职于兰德公司的梅里尔弗勒德（弗勒德（Merrill Flood）和梅尔文）和梅尔文德雷希尔（德雷希尔（Melvin Dresher）拟定出相关困境的理论，后来由顾问艾）拟定出相关困境的理论，后来由顾问艾伯特伯特塔克（塔克（Albert Tucker）以囚徒方式阐述，并命名为

38、）以囚徒方式阐述，并命名为“囚徒困境囚徒困境”。q经典的囚徒困境如下：经典的囚徒困境如下：两个嫌犯被捕后被关在相互隔离的牢房中。他们面临的选择是：或者两个嫌犯被捕后被关在相互隔离的牢房中。他们面临的选择是：或者坦白或者保持沉默（即不坦白）。他们被告知：坦白或者保持沉默（即不坦白）。他们被告知：如果某个嫌疑犯坦白而其同伙不坦白，则坦白者可获自由而拒不坦如果某个嫌疑犯坦白而其同伙不坦白，则坦白者可获自由而拒不坦白者要被判白者要被判10年监禁；年监禁；如果二人都坦白，则二人都被判如果二人都坦白，则二人都被判5年监禁；年监禁；如果二人都不坦白，则二人皆被判如果二人都不坦白，则二人皆被判1年监禁。年监禁

39、。q上述情况我们亦可用一支付矩阵表示如下：上述情况我们亦可用一支付矩阵表示如下：嫌疑犯乙嫌疑犯乙 坦白沉默坦白沉默 嫌疑犯甲坦白嫌疑犯甲坦白-5,-50,-10 沉默沉默-10,0-1,-1 在这种情况下，两个嫌犯将如何决策和选择呢？在这种情况下，两个嫌犯将如何决策和选择呢？严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。博弈的必胜策略q博奕和量词紧密相关博奕和量词紧密相关q一个量化语句一个量化语句一个博弈一个博弈作用：描述和解释该语句的含义作用：描述和解释该语句的含义q一个博弈一个博弈一个量化语句一个量化语句作用：理解该博弈的复

40、杂性作用：理解该博弈的复杂性q例：前束范式的量词化布尔公式例：前束范式的量词化布尔公式 =x1 x2 x3Qxk Q:/，-去掉量词的公式去掉量词的公式 与下面的博弈关联：与下面的博弈关联：2 2名选手名选手A A,E E，轮流为，轮流为x1,x2,x3,xk 选值选值严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。博弈的必胜策略选手选手E所对所对应的量词应的量词选手选手A所对所对应的量词应的量词选手选手E取值取值选手选手A取值取值对变量进行对变量进行处理的语句处理的语句TRUE:E胜胜FALSE:A胜胜其中其中A对任意量词约束的

41、变量选值；对任意量词约束的变量选值；E对存在量词约束的变量选值对存在量词约束的变量选值严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。例8.9 1 1=x1 x2 x3(x1 x2 2)(x2 x3)(x2 x3)E确定的确定的变量值变量值A确定的确定的变量值变量值 设设E：x1=1;A：x2=0;E：x3=1;=1,E赢赢取值相反取值相反E必胜：必胜：设设E：x1=1/0;A：x2=0;E：x3=1/0;=0,A赢赢A必胜：必胜：2 2=x1 x2 x3(x1 x2 2)(x2 x3)(x2 x3)必胜策略必胜策略一个选手有必胜

42、策略，如果他在博弈双方都下出最佳步骤时能赢一个选手有必胜策略，如果他在博弈双方都下出最佳步骤时能赢严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。博弈的必胜策略q判定在与某具体公式关联的公式博弈中哪方有必胜策略的判定在与某具体公式关联的公式博弈中哪方有必胜策略的问题是问题是 PSPACE 完全的。完全的。FORMULA-GAME=|在与在与 关联的公式博奕中选手关联的公式博奕中选手E有必胜策略有必胜策略 严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。博弈的必胜策略定

43、理定理定理定理8.108.10FARMULA-GAME 是是 PSPACE 完全的。完全的。要证要证FORMULA-GAME是是PSPACE完全的完全的FORMULA-GAME=TQBFFORMULA-GAME=|是真的全量词化布尔公式是真的全量词化布尔公式 严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。FARMULA-GAME 是 PSPACE 完全的公式公式 =x1 x2 x3 是是 TRUE 的条件是：的条件是：存在存在 x1 的某种赋值，使得对于的某种赋值，使得对于 x2 的任意赋值，存在的任意赋值，存在 x3 的某种赋

44、值，使得的某种赋值，使得等等，其中等等，其中 在这些变量的赋值下是在这些变量的赋值下是 TRUE。类似地，选手类似地，选手 E 在与在与 关联的博奔中有必胜策略的条件是：关联的博奔中有必胜策略的条件是：选手选手 E 可以给可以给 x1 赋某个值，使得对于赋某个值，使得对于 x2 的任意赋值，选手的任意赋值，选手 E 可以给可以给 x3 赋赋一个值，使得一个值，使得等等，等等，在变量的这些赋值下为在变量的这些赋值下为 TRUE。当公式不在存在量词与全称量词之间交替时，同样的推理也能成立。当公式不在存在量词与全称量词之间交替时，同样的推理也能成立。如果如果 的形式为的形式为 x1,x2,x3 x4

45、,x5 x6，选手选手 A 在公式博弈中走头三步，给在公式博弈中走头三步，给 x1,x2 和和 x3 贼值；然后选手贼值；然后选手 E 走两次，走两次，给给 x4 和和 x5 贼值；最后选手贼值；最后选手 A 给给x6 赋一个值。赋一个值。因此，因此，TQBE 恰好当恰好当 FARMULA-GAME 时成立，由定理时成立，由定理8.8，本定理，本定理成立。成立。严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。广义地理学地理学地理学q一种儿童一种儿童游戏。游戏。q选手们选手们轮流轮流给世界各地的城市命名。给世界各地的城市命名。q每一

46、座选中的城市的每一座选中的城市的首字母必须与前一座城市的尾字母相首字母必须与前一座城市的尾字母相同，不得重复同，不得重复。q游戏游戏从某指定的起始城市开始从某指定的起始城市开始，以某方，以某方无法延续而认输为无法延续而认输为止止。q例如：例如：开始：开始：Peoria PeoriaAmherstTucsonNashua 结束：直到某方被难倒结束：直到某方被难倒严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。地理学图类似成类似成语接龙语接龙结点是世结点是世界各地的界各地的城市城市严格执行突发事件上报制度、校外活动报批制度等相关规章制

47、度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。广义地理学q按照地理学规则按照地理学规则翻译翻译为图表示法为图表示法一名选手从一名选手从指定的起始节点开始指定的起始节点开始，然后选手们，然后选手们交替交替地挑地挑选结点，形成图中的一条选结点，形成图中的一条简单路径简单路径。要求是简单路径要求是简单路径(即每个节点只能用即每个节点只能用 1 次次)对应于要求城对应于要求城市市不能重复不能重复。第第 1 个个不能扩展路径的选手输掉比赛不能扩展路径的选手输掉比赛。严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。广义地理学游戏样

48、例广义地理学游戏样例选手选手I必胜必胜1 13 36 64 45 52 27 78 89 9从结点从结点1开始，开始，选手选手I先做选择先做选择严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。广义地理学游戏样例广义地理学游戏样例选手选手II必胜必胜1 13 36 64 45 52 27 78 89 9从结点从结点1开始，选开始，选手手I先做选择先做选择现在方向变成节现在方向变成节点点3节点节点6严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。广义地理学q判定在广义地理

49、学游戏中哪一方有必胜策赂的问题是判定在广义地理学游戏中哪一方有必胜策赂的问题是PSPACE全的。全的。qGG=|在图在图 G 上以结点上以结点 b 起始的广义地理学游戏中，起始的广义地理学游戏中，选手选手 I 有必胜策略有必胜策略 定理定理定理定理8.118.11GG 是是 PSPACE 完全的。完全的。证明略证明略严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。广义地理学下面的的算法判定在广义地理学实例中，选手下面的的算法判定在广义地理学实例中，选手I是否有必胜策略。换是否有必胜策略。换 句话说，它判定句话说，它判定GG。现证明

50、它在多项式空间内运行：。现证明它在多项式空间内运行：M=“对输入对输入，G是有向图，是有向图，b是是G的结点：的结点：1）若）若b出度为出度为0，则拒绝，因为选手，则拒绝，因为选手I立即输。立即输。2）删去结点）删去结点b以及与它关联的所有箭头，得到一个新图以及与它关联的所有箭头，得到一个新图G1。3）对于）对于b原先指向的每个节点原先指向的每个节点b1，b2，bk，在，在上递归上递归地调用地调用 M。4）若所有调用都接受，则选手）若所有调用都接受，则选手 在原先博弈中有必胜策略，所以拒绝。在原先博弈中有必胜策略，所以拒绝。否则，选手否则，选手I 没有必胜策赂，而选手没有必胜策赂，而选手I有必