计算理论导引空间复杂性精选文档.ppt

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

1、计算理论导引空间复杂性本讲稿第一页，共四十八页2主要内容主要内容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本讲稿第二页，共四十八页空间复杂度定义定义定义定义8.18.1令令 M 是一个在所有输入上都停机的确定型图灵机。是一个在所有输入上都停机的确定型图灵机。M 的的空间复杂度空间复杂度是一个函数是一个函数 f:NN，其中，其中 f(n)是是 M 在任何长为在任何长为

2、 n 的输入上扫描带方格的最大数的输入上扫描带方格的最大数。若若 M 的空间复杂度为的空间复杂度为 f(n)，也称，也称 M 在空间在空间 f(n)内运。内运。如果如果 M 是对所有输入是对所有输入在所有分支上都停机在所有分支上都停机的的非确定型图灵机非确定型图灵机，则定义它，则定义它的的空间复杂度空间复杂度 f(n)为为 M 在任何长为在任何长为 n 的输入上，在任何计算分支上的输入上，在任何计算分支上所扫描的带方格的最大数所扫描的带方格的最大数。通常用渐进记法估计图灵机的空间复杂度。通常用渐进记法估计图灵机的空间复杂度。本讲稿第三页，共四十八页空间复杂性类定义定义定义定义8.28.2令令

3、f:NR+是一个函数，是一个函数，空间复杂性类空间复杂性类 SPACE(f(n)和和 NSPACE(f(n)定义如下：定义如下：SPACE(f(n)=L|L是被是被 O(f(n)空间的空间的确定型图灵机确定型图灵机判定的语言判定的语言 NSPACE(f(n)=L|L是被是被 O(f(n)空间的空间的非确定型图灵机非确定型图灵机判定的语言判定的语言 本讲稿第四页，共四十八页例8.3例例8.3 证明用线性空间算法能求解证明用线性空间算法能求解 SAT 问题。问题。M1=“对输入对输入，是布尔公式：是布尔公式：1)对于对于 中中变量变量 x1,xm 的每个真值赋值：的每个真值赋值：2)计算计算 在该

4、真值赋值下的值。在该真值赋值下的值。3)若若 的值为的值为 1，则接受；否则拒绝。，则接受；否则拒绝。”显然机器显然机器 M1 是在线性空间内运行，因为每一次循环都是在线性空间内运行，因为每一次循环都可以复用带子可以复用带子上的同一部分上的同一部分。该机器只需存储当前的真值赋值，这只需。该机器只需存储当前的真值赋值，这只需消耗消耗 O(m)空间空间。因为变量数因为变量数 m 最多是输入长度最多是输入长度 n，所以该机器在空间，所以该机器在空间 O(n)内运行。内运行。本讲稿第五页，共四十八页例：语言的非确定性空间复杂性例例8.4 令令 ALLNFA|A 是一个是一个 NFA 且且 L(A)=*

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

6、的状态数。的状态数。3)非确定地选择一个输入符号并移动标记到非确定地选择一个输入符号并移动标记到 M 的相的相 应状态应状态，来模拟读取那个符号。，来模拟读取那个符号。4)如果步骤如果步骤 2 和和 3 表明表明 M 拒绝某些字符串，即如果在某一时刻所有标记都不落在拒绝某些字符串，即如果在某一时刻所有标记都不落在 M 的接受状态上，则接受；否则拒绝。的接受状态上，则接受；否则拒绝。”本讲稿第六页，共四十八页例：语言的非确定性空间复杂性7如果如果 M 拒绝某个字符串，则它必定拒绝一个长度不超过拒绝某个字符串，则它必定拒绝一个长度不超过 2q 的字符串，因为在任何被拒绝的的字符串，因为在任何被拒绝

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

8、定理定理定理定理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 是非确定型机器所使用的最大步数，那么通过求是非确定型机器所使用的最大步数，那么通过求解可产生问题，就能够判断机器是否接受输入。解可产生问题，就能够判断机器是否接受输入。

9、可以用一个可以用一个确定的递归算法确定的递归算法求解可产生问题。运算过程如下：求解可产生问题。运算过程如下：寻找一个中间格局寻找一个中间格局 cm，递归地检查，递归地检查 c1 能否在能否在 t/2 步内到达步内到达 cm，cm 能否在能否在 t/2步内到达步内到达 c2，重复使用两次递归检查的空间可节省空间开销重复使用两次递归检查的空间可节省空间开销。递归的每一层需要递归的每一层需要 O(f(n)空间来存储一个格局。递归的深度是空间来存储一个格局。递归的深度是 log t，t 是非确定型机器是非确定型机器在所有分支上可能消耗的最大时间，在所有分支上可能消耗的最大时间，t=2O(f(n)，lo

10、g t=O(f(n)。因此模拟过程需要因此模拟过程需要 O(f 2(n)。本讲稿第八页，共四十八页萨维奇定理的证明设设 N 是在空间是在空间 f(n)内判定语言内判定语言 A 的的 NTM。构造一个判定构造一个判定 A 的确定型的确定型 TM M。机器。机器 M 利用过程利用过程 CANYIELD，该过程检查，该过程检查 N 的的一个格局能否在指定的步数内产生另一个格局。一个格局能否在指定的步数内产生另一个格局。设设 w 是输入到是输入到 N 的字符串。对于的字符串。对于 N 在在 w 上的格局上的格局 c1、c2 以及整数以及整数 t，如果从格局，如果从格局 c1 出发，出发，N 有一系列非

11、确定的选择能使它在有一系列非确定的选择能使它在 t 步内进入格局步内进入格局 c2，则，则CANYIELD(c1,c2,t)输出接受，否则，输出接受，否则，CANYIELD 输出拒绝。输出拒绝。CANYIELD=“对输入对输入 c1,c2 和和 t：1)若若 t=1，则直接检查是否有，则直接检查是否有 c1=c2，或者根据，或者根据 N 的规则检查的规则检查 c1 能否在一步内能否在一步内产生产生c2。如果其中之一成立，则接受；如果两种情况都不成立，则拒绝。如果其中之一成立，则接受；如果两种情况都不成立，则拒绝。2)若若 t 1，则对于，则对于 N 在在 w上消耗空间上消耗空间 f(n)的每一

12、个格局的每一个格局cm：3)运行运行 CANYIELD(c1,cm,t/2)。4)运行运行 CANYIELD(cm,c2,t/2)。5)若第若第 3 和第和第 4 步都接受，则接受。步都接受，则接受。6)若此时还没有接受，则拒绝。若此时还没有接受，则拒绝。”本讲稿第九页，共四十八页萨维奇定理的证明现在定义现在定义 M 来模拟来模拟 N。首先修改。首先修改 N，当它接受时，把带子清空并把读写头移到最左，当它接受时，把带子清空并把读写头移到最左边的单元，从而进入称为边的单元，从而进入称为 caccept 的格局。的格局。令令 cstart 是是 N 在在 w 上的起始格局。选一个常数上的起始格局。

13、选一个常数 d，使得，使得 N 在在 f(n)空间上的格局数不超过空间上的格局数不超过 2df(n)，其中，其中 n 是是 w 的长度。的长度。2df(n)是是 N 在所有分支上的运行时间的上界在所有分支上的运行时间的上界。M“对输入对输入 w：1)输出输出 CANYIELD(cstart，caccept，2df(n)的结果。的结果。”算法算法 CANYIELD 显然求解了可产生性问题，因此显然求解了可产生性问题，因此 M 正确地模拟正确地模拟 N。下面需要分析下面需要分析 M，确信它在，确信它在 O(f(n)空间内运行。空间内运行。CANYIELD 在递归调用自己时，它都把所处的步骤号、在递

14、归调用自己时，它都把所处的步骤号、c1、c2 和和 t 的都存储在栈中，所以的都存储在栈中，所以递归调用时返回时能恢复这些值。因此在递归的每一层需要增加递归调用时返回时能恢复这些值。因此在递归的每一层需要增加 O(f(n)空间。空间。此外，此外，递归的每一层把递归的每一层把 t 的值减小一半的值减小一半。开始时。开始时 t 等于等于2df(n)，所以递归的深度是，所以递归的深度是 O(log 2df(n)或或 O(f(n)，因此共消耗空间是，因此共消耗空间是 O(f2(n)。本讲稿第十页，共四十八页11主要内容主要内容8.1 萨维奇定理萨维奇定理8.2 PSPACE 类类8.3 PSPACE

15、完全性完全性8.3.1 TQBF 问题问题8.3.2 博弈的必胜策略博弈的必胜策略8.3.3 广义地理学广义地理学8.4 L 类类 NL 类类8.5 NL 完全性完全性8.6 NL 等于等于 coNL本讲稿第十一页，共四十八页PSPACE 类定义定义定义定义8.68.6PSPACE 是在是在确定型确定型图灵机上、在图灵机上、在多项式空间内多项式空间内可判可判定的语言类。换言之，定的语言类。换言之，PSPACE k SPACE(nk)PSPACE 类的非确定型版本类的非确定型版本 NPSPACE，可以类似地用，可以类似地用NSPACE 类来类来定义。定义。然而，任何多项式的平方仍是多项式，根据萨

16、维奇定理，则然而，任何多项式的平方仍是多项式，根据萨维奇定理，则NPSPACE=PSPACE。在例在例8.3和和8.4中，已经说明了中，已经说明了 SAT 属于属于 SPACE(n)，ALLNFA 属于属于 coNSPACE(n)，而根据萨维奇定理，而根据萨维奇定理，确定型空间复杂度对补运算封闭确定型空间复杂度对补运算封闭，所以，所以 ALLNFA 也属于也属于 SPACE(n2)。因此。因此 SAT 和和ALLNFA 这两个语言都在这两个语言都在 PSPACE 中中。本讲稿第十二页，共四十八页PSPACE 类考察考察 PSPACE 与与 P 和和 NP 的关系。的关系。显而易见，显而易见，P

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

18、个消耗一个消耗f(n)空间的空间的 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 类类 NL 类类8.5 NL 完全性完全性8.6 NL 等于等于

19、 coNL本讲稿第十四页，共四十八页PSPACE 完全性定义定义定义定义8.78.7语言语言 B 是是PSPACE完全的完全的。若它满足下面两个条件：。若它满足下面两个条件：1)B 属于属于 PSPACE。2)PSPACE中的每一个语言中的每一个语言A多项式时间可归约到多项式时间可归约到B。若若 B 只满足条件只满足条件 2，则称它为，则称它为 PSPACE难的难的。本讲稿第十五页，共四十八页TQBF 问题q量词量词：、对于自然数，语句对于自然数，语句 x x+1x 为真。为真。y y+y=y 为假。为假。q辖域辖域：量词的作用范围。：量词的作用范围。q前束范式前束范式：形如形如 =Q1x1

20、Q2 x2 Qk xk B，Qi 为为 或或 q量词化布尔公式量词化布尔公式：带量词的布尔公式（必须是前束范式）。：带量词的布尔公式（必须是前束范式）。q全量词化全量词化：公式中的每个变量都出现在某一量词的辖域中。：公式中的每个变量都出现在某一量词的辖域中。qTQBF 问题就是要判定一个全量词化的布尔公式是真是假问题就是要判定一个全量词化的布尔公式是真是假。TQBF=|是真的全量词化的布尔公式是真的全量词化的布尔公式本讲稿第十六页，共四十八页TQBF 问题定理定理定理定理8.88.8TQBF 是是 PSPACE 完全的。完全的。q证明思路证明思路(1)为了为了证明证明TQBF属于属于PSPAC

21、E，给出一个简单的算法。该算法首先给变量赋值，给出一个简单的算法。该算法首先给变量赋值，然后递归地计算公式在这些值下的真值。从这些信息中算法就能确定原量化公然后递归地计算公式在这些值下的真值。从这些信息中算法就能确定原量化公式的真值。式的真值。(2)为了为了证明证明PSPACE中的每个语言中的每个语言A在多项式时间内可归约到在多项式时间内可归约到TQBF，从判定，从判定 A 的的多项式空间界限图灵机开始。然后给出多项式时间归约，它多项式空间界限图灵机开始。然后给出多项式时间归约，它把一个字符串映射为把一个字符串映射为一个量词化的布尔公式一个量词化的布尔公式，模拟机器对这个输入的计算。模拟机器对

22、这个输入的计算。公式为真的充分公式为真的充分必要条件是机器接受必要条件是机器接受。改用一种与萨维奇定理的证明相关的技术来构造公式。该公式把画面分成两半，利改用一种与萨维奇定理的证明相关的技术来构造公式。该公式把画面分成两半，利用全称量词的功能，用公式的同一部分来代表每一半。结果产生短得多的公式。用全称量词的功能，用公式的同一部分来代表每一半。结果产生短得多的公式。本讲稿第十七页，共四十八页TQBF 问题首先，给出一个判定首先，给出一个判定 TQBF 的多项式空间算法：的多项式空间算法：T “对输入对输入，是一个全量词化的布尔公式是一个全量词化的布尔公式：1)若若 不含量词，则它是一个只有常数的

23、表达式。计算不含量词，则它是一个只有常数的表达式。计算 的值，若为真，则接受；否的值，若为真，则接受；否则，拒绝。则，拒绝。2)若若 等于等于 x ，在，在 上递归地调用上递归地调用 T，首先用，首先用 0 替换替换 x，然后用，然后用 1 替换替换 x。只要有一个结果是接受只要有一个结果是接受，则接受；否则，拒绝。，则接受；否则，拒绝。3)若若 等于等于 x ，在，在 上递归地调用上递归地调用 T，首先用，首先用 0 替换替换 x，然后用，然后用 1 替换替换 x。若。若两个结果都能接受两个结果都能接受，则接受；否则，拒绝。，则接受；否则，拒绝。”算法算法 T 显然判定显然判定 TQBF。空

24、间复杂性：它递归的深度最多等于变量的个数。在每一层只需存储一个变空间复杂性：它递归的深度最多等于变量的个数。在每一层只需存储一个变量的值，所以全部空间消耗是量的值，所以全部空间消耗是 O(m)，其中，其中 m 是是 中出现的变量的个数。因此中出现的变量的个数。因此 T 在线性空间内运行。在线性空间内运行。本讲稿第十八页，共四十八页TQBF 问题下面，证明下面，证明 TQBF 是是 PSPACE 难的。难的。设设 A 是一个由是一个由 TM M 在在 nk 空间内判定的语言空间内判定的语言，k 是某个常数。是某个常数。下面给出一个从下面给出一个从 A 到到 TQBF 的多项式时间归约。该归约的多

25、项式时间归约。该归约把字符串把字符串 w 映射为一个量词化映射为一个量词化的布尔公式的布尔公式 ，为为真当且仅当真当且仅当 M 接受接受 w。为了说明怎样构造为了说明怎样构造 ，需解决一个更一般的问题。，需解决一个更一般的问题。利用两个代表格局的变量集合利用两个代表格局的变量集合 c1 和和 c2 及一个数及一个数 t 0，构造一个公式，构造一个公式 c1,c2,t。如果把。如果把 c1 和和c2 赋为实际的格局，则该公式为真赋为实际的格局，则该公式为真当且仅当当且仅当 M 能够在能够在最多最多 t 步内从步内从 c1到达到达 c2。然后，可以令。然后，可以令 是公式是公式 cstart,ca

26、ccept,h，其其中中 h=2df(n)，d 是一个选取的常数，使得是一个选取的常数，使得 M 在长为在长为 n 的输入上可能的格局数不超过的输入上可能的格局数不超过 2df(n)。这里，令这里，令f(n)=nk。为了方便，假设。为了方便，假设 t 是是 2 的幂。的幂。类似库克类似库克-列文定理的证明，该公式对带单元的内容编码。对应于单元的可能设置，每个单列文定理的证明，该公式对带单元的内容编码。对应于单元的可能设置，每个单元有几个相关的变量，每个带符号和状态有一个变量。每个格局有元有几个相关的变量，每个带符号和状态有一个变量。每个格局有nk个单元，所以用个单元，所以用 O(nk)个变量编

27、码。个变量编码。本讲稿第十九页，共四十八页TQBF问题若若 t=1，则容易构造，则容易构造 c1,c2,t。设计公式，使之表达要么设计公式，使之表达要么 c1 等于等于 c2，要么，要么 c1能在能在 M 的一步内变到的一步内变到 c2。为了表达相等性，使用一个布尔表达式来表示：为了表达相等性，使用一个布尔表达式来表示：代表代表 c1 的每一个变量与代表的每一个变量与代表 c2 的相应变的相应变量包含同样的布尔值量包含同样的布尔值。为表达第二种可能性，采用库克为表达第二种可能性，采用库克-列文定理的证明中给出的技巧，构造布尔表达式列文定理的证明中给出的技巧，构造布尔表达式表示，表示，代表代表

28、c1 的每个三元组的值能正确产生相应的的每个三元组的值能正确产生相应的 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,c

29、2,t 的这个构造的含义是：如果存在某个中间格局的这个构造的含义是：如果存在某个中间格局 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 能在能在 t 步内从步内从 c1 变到变到 c2，它就是，它就

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

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

32、的量化布尔公式。，从而得到语法正确的量化布尔公式。为了计算公式个为了计算公式个 cstart，caccept,h 的长度，其中的长度，其中 h=2df(n)，注意到递归增加的那部分公式，注意到递归增加的那部分公式的长度与格局的长度呈线性关系，所以长度是的长度与格局的长度呈线性关系，所以长度是O(f(n)。递归的层数是。递归的层数是log2df(n)或或 O(f(n)。所以所得到的公式的长度是。所以所得到的公式的长度是O(f 2(n)。本讲稿第二十一页，共四十八页博弈的必胜策略q博奕论：每个游戏常有博奕论：每个游戏常有 2 个以上的参加者，他们个以上的参加者，他们(局中人局中人)在在游戏中都有自

33、己的切身利益，每个局中人都有自己的可行行游戏中都有自己的切身利益，每个局中人都有自己的可行行动集供自己选择，这种选择毫无疑问地会影响到其他局中人动集供自己选择，这种选择毫无疑问地会影响到其他局中人的切身利益。游戏中各个局中人理性地采取的切身利益。游戏中各个局中人理性地采取/选择自己的策选择自己的策略行为，使得在这种相互制约相互影响的依存关系中，尽可略行为，使得在这种相互制约相互影响的依存关系中，尽可能提高自己的利益所得，这正是游戏理论的关键所得。能提高自己的利益所得，这正是游戏理论的关键所得。q要点：要点：博奕的各方都是理性的博奕的各方都是理性的各人的选择都是为取得利益的最大化各人的选择都是为

34、取得利益的最大化本讲稿第二十二页，共四十八页囚徒困境q1950年，就职于兰德公司的梅里尔年，就职于兰德公司的梅里尔弗勒德（弗勒德（Merrill Flood）和梅尔文）和梅尔文德雷希德雷希尔（尔（Melvin Dresher）拟定出相关困境的理论，后来由顾问艾伯特）拟定出相关困境的理论，后来由顾问艾伯特塔克（塔克（Albert Tucker）以囚徒方式阐述，并命名为）以囚徒方式阐述，并命名为“囚徒困境囚徒困境”。q经典的囚徒困境如下：经典的囚徒困境如下：两个嫌犯被捕后被关在相互隔离的牢房中。他们面临的选择是：或者坦白或者保持沉两个嫌犯被捕后被关在相互隔离的牢房中。他们面临的选择是：或者坦白或者

35、保持沉默（即不坦白）。他们被告知：默（即不坦白）。他们被告知：如果某个嫌疑犯坦白而其同伙不坦白，则坦白者可获自由而拒不坦如果某个嫌疑犯坦白而其同伙不坦白，则坦白者可获自由而拒不坦白者要被判白者要被判10年监禁；年监禁；如果二人都坦白，则二人都被判如果二人都坦白，则二人都被判5年监禁；年监禁；如果二人都不坦白，则二人皆被判如果二人都不坦白，则二人皆被判1年监禁。年监禁。q上述情况我们亦可用一支付矩阵表示如下：上述情况我们亦可用一支付矩阵表示如下：嫌疑犯乙嫌疑犯乙 坦白沉默坦白沉默 嫌疑犯甲坦白嫌疑犯甲坦白-5,-50,-10 沉默沉默-10,0-1,-1 在这种情况下，两个嫌犯将如何决策和选择呢

36、？在这种情况下，两个嫌犯将如何决策和选择呢？本讲稿第二十三页，共四十八页博弈的必胜策略q博奕和量词紧密相关博奕和量词紧密相关q一个量化语句一个量化语句一个博弈一个博弈作用：描述和解释该语句的含义作用：描述和解释该语句的含义q一个博弈一个博弈一个量化语句一个量化语句作用：理解该博弈的复杂性作用：理解该博弈的复杂性q例：前束范式的量词化布尔公式例：前束范式的量词化布尔公式q =x1 x2 x3Qxk q Q:/，-去掉量词的公式去掉量词的公式q 与下面的博弈关联：与下面的博弈关联：q 2 2名选手名选手A A,E E，轮流为，轮流为x1,x2,x3,xk 选值选值本讲稿第二十四页，共四十八页博弈的

37、必胜策略选手选手E所对所对应的量词应的量词选手选手A所对所对应的量词应的量词选手选手E取值取值选手选手A取值取值对变量进行对变量进行处理的语句处理的语句TRUE:E胜胜FALSE:A胜胜其中其中A对任意量词约束的变量选值；对任意量词约束的变量选值；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

38、;=0,A赢赢A必胜：必胜：2 2=x1 x2 x3(x1 x2 2)(x2 x3)(x2 x3)必胜策略必胜策略一个选手有必胜策略，如果他在博弈双方都下出最佳步骤时能赢一个选手有必胜策略，如果他在博弈双方都下出最佳步骤时能赢本讲稿第二十六页，共四十八页博弈的必胜策略q判定在与某具体公式关联的公式博弈中哪方有必胜策略的判定在与某具体公式关联的公式博弈中哪方有必胜策略的问题是问题是 PSPACE 完全的。完全的。FORMULA-GAME=|在与在与 关联的公式博奕中选手关联的公式博奕中选手E有必胜策略有必胜策略 本讲稿第二十七页，共四十八页博弈的必胜策略定理定理定理定理8.108.10FARMU

39、LA-GAME 是是 PSPACE 完全的。完全的。要证要证FORMULA-GAME是是PSPACE完全的完全的FORMULA-GAME=TQBFFORMULA-GAME=|是真的全量词化布尔公式是真的全量词化布尔公式 本讲稿第二十八页，共四十八页FARMULA-GAME 是 PSPACE 完全的公式公式 =x1 x2 x3 是是 TRUE 的条件是：的条件是：存在存在 x1 的某种赋值，使得对于的某种赋值，使得对于 x2 的任意赋值，存在的任意赋值，存在 x3 的某种赋值，使得的某种赋值，使得等等，等等，其中其中 在这些变量的赋值下是在这些变量的赋值下是 TRUE。类似地，选手类似地，选手

40、E 在与在与 关联的博奔中有必胜策略的条件是：关联的博奔中有必胜策略的条件是：选手选手 E 可以给可以给 x1 赋某个值，使得对于赋某个值，使得对于 x2 的任意赋值，选手的任意赋值，选手 E 可以给可以给 x3 赋一个值，赋一个值，使得使得等等，等等，在变量的这些赋值下为在变量的这些赋值下为 TRUE。当公式不在存在量词与全称量词之间交替时，同样的推理也能成立。当公式不在存在量词与全称量词之间交替时，同样的推理也能成立。如果如果 的形式为的形式为 x1,x2,x3 x4,x5 x6，选手选手 A 在公式博弈中走头三步，给在公式博弈中走头三步，给 x1,x2 和和 x3 贼值；然后选手贼值；然

41、后选手 E 走两次，给走两次，给 x4 和和 x5 贼贼值；最后选手值；最后选手 A 给给x6 赋一个值。赋一个值。因此，因此，TQBE 恰好当恰好当 FARMULA-GAME 时成立，由定理时成立，由定理8.8，本定理成立。，本定理成立。本讲稿第二十九页，共四十八页广义地理学地理学地理学q一种儿童一种儿童游戏。游戏。q选手们选手们轮流轮流给世界各地的城市命名。给世界各地的城市命名。q每一座选中的城市的每一座选中的城市的首字母必须与前一座城市的尾字母相首字母必须与前一座城市的尾字母相同，不得重复同，不得重复。q游戏游戏从某指定的起始城市开始从某指定的起始城市开始，以某方，以某方无法延续而认输为

42、无法延续而认输为止止。q例如：例如：开始：开始：Peoria PeoriaAmherstTucsonNashua 结束：直到某方被难倒结束：直到某方被难倒本讲稿第三十页，共四十八页地理学图类似成类似成语接龙语接龙结点是世界结点是世界各地的城市各地的城市本讲稿第三十一页，共四十八页广义地理学q按照地理学规则按照地理学规则翻译翻译为图表示法为图表示法一名选手从一名选手从指定的起始节点开始指定的起始节点开始，然后选手们，然后选手们交替交替地挑选结点，地挑选结点，形成图中的一条形成图中的一条简单路径简单路径。要求是简单路径要求是简单路径(即每个节点只能用即每个节点只能用 1 次次)对应于要求城市对应于

43、要求城市不能重不能重复复。第第 1 个个不能扩展路径的选手输掉比赛不能扩展路径的选手输掉比赛。本讲稿第三十二页，共四十八页广义地理学游戏样例广义地理学游戏样例选手选手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判定在广义地理学游戏中哪一方有必胜策赂的问题

44、是判定在广义地理学游戏中哪一方有必胜策赂的问题是PSPACE全的。全的。qGG=|在图在图 G 上以结点上以结点 b 起始的广义地理学游戏中，选手起始的广义地理学游戏中，选手 I 有必胜策略有必胜策略 定理定理定理定理8.118.11GG 是是 PSPACE 完全的。完全的。证明略证明略本讲稿第三十五页，共四十八页广义地理学下面的的算法判定在广义地理学实例中，选手下面的的算法判定在广义地理学实例中，选手I是否有必胜策略。换是否有必胜策略。换 句话说，它判定句话说，它判定GG。现证明它在多项式空间内运行：。现证明它在多项式空间内运行：M=“对输入对输入，G是有向图，是有向图，b是是G的结点：的结

45、点：1）若）若b出度为出度为0，则拒绝，因为选手，则拒绝，因为选手I立即输。立即输。2）删去结点）删去结点b以及与它关联的所有箭头，得到一个新图以及与它关联的所有箭头，得到一个新图G1。3）对于）对于b原先指向的每个节点原先指向的每个节点b1，b2，bk，在，在上递归地调用上递归地调用 M。4）若所有调用都接受，则选手）若所有调用都接受，则选手 在原先博弈中有必胜策略，所以拒绝。在原先博弈中有必胜策略，所以拒绝。否则，选手否则，选手I 没有必胜策赂，而选手没有必胜策赂，而选手I有必胜策略，因此接受。有必胜策略，因此接受。”本讲稿第三十六页，共四十八页37主要内容主要内容8.1 萨维奇定理萨维奇

46、定理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本讲稿第三十七页，共四十八页L 类和 NL 类q线性空间复杂性界限：线性空间复杂性界限：f(n)=nq亚线性空间复杂性界限：亚线性空间复杂性界限：f(n)n在时间复杂性中不考虑亚线性，因为亚线性连输入都不能读完。在时间复杂性中不考虑亚线性，因为亚线性连输入都不能读完。亚线性空间复杂性中能读完全部输入，但没有足够的空间存储全亚线性空间复杂性中能读完

47、全部输入，但没有足够的空间存储全部输入。解决办法是修改计算模型部输入。解决办法是修改计算模型包含只读带的两带图灵机。包含只读带的两带图灵机。q两带图灵机两带图灵机一条只读输入带：相当于一条只读输入带：相当于CD_ROM一条读写工作带：可修改。一条读写工作带：可修改。只有工作带上被扫描的单元才构成这种图灵机的空间复杂性。只有工作带上被扫描的单元才构成这种图灵机的空间复杂性。本讲稿第三十八页，共四十八页L 类和 NL 类定义定义定义定义8.128.12L 是确定型图灵机在对数空间内可判定的语言类。是确定型图灵机在对数空间内可判定的语言类。L SPACE(log n)NL是非确定型图灵机在对数空间内

48、可判定的语言类。是非确定型图灵机在对数空间内可判定的语言类。NL NSPACE(log n)本讲稿第三十九页，共四十八页L 类和 NL 类40例例8.13 语言语言 A=0k1k|k 0 是是 L 的成员。在的成员。在7.1节中描述了一个判定节中描述了一个判定 A 的图灵机，它左右来回扫描输人，删掉匹配的的图灵机，它左右来回扫描输人，删掉匹配的 0 和和 1。该算法用线。该算法用线性空间记录哪些位置已经被删掉，但可以修改为只使用对数空间。性空间记录哪些位置已经被删掉，但可以修改为只使用对数空间。判定判定 A 的对数空间的对数空间 TM 不能删除输入带上已经匹配的不能删除输入带上已经匹配的 0

49、和和 1，因为该带，因为该带是只读的。是只读的。机器在工作带上用二进制分别数机器在工作带上用二进制分别数 0 和和 1 的数目。唯一需要的空间是的数目。唯一需要的空间是用来记录这两个计数器的。在二进制形式，每个计数器只消耗对用来记录这两个计数器的。在二进制形式，每个计数器只消耗对数空间，因此算法在数空间，因此算法在 O(log n)空间内运行。所以空间内运行。所以 A L。本讲稿第四十页，共四十八页L 类和 NL 类41例例8.14 语言语言 PATH=|G 是包含从是包含从 s 到到 t 的有向路径的有向的有向路径的有向图图。定理。定理7.12证明证明 PATH 属于属于P，但是给出的算法消

50、耗线性空间。现，但是给出的算法消耗线性空间。现在能否找到只消耗对数空间的算法？在能否找到只消耗对数空间的算法？判定判定 PATH 的非确定型对数空间图灵机从节点的非确定型对数空间图灵机从节点 s 开始运算，开始运算，非确定地猜测从非确定地猜测从 s 到到 t 的路径的每一步的路径的每一步。机器在工作带上只记录每一步当前节点的位置机器在工作带上只记录每一步当前节点的位置，而不是整条路径，而不是整条路径(否则将否则将超出对数空间的要求超出对数空间的要求)。机器从当前节点所指向的节点中非确定地选择下一个节点。机器从当前节点所指向的节点中非确定地选择下一个节点。它反复执行这一操作，直到到达结点它反复执