我要投搞

标签云

收藏小站

爱尚经典语录、名言、句子、散文、日志、唯美图片

当前位置:小鱼儿玄机1站开奘结果 > 前束范式 >

计算理论导引空间复杂性ppt

归档日期:07-05       文本归类:前束范式      文章编辑:爱尚语录

  1.本站不保证该用户上传的文档完整性,不预览、不比对内容而直接下载产生的反悔问题本站不予受理。

  例8.3 例8.3 证明用线性空间算法能求解 SAT 问题。 例:语言的非确定性空间复杂性 例8.4 令 ALLNFA = { A A 是一个 NFA 且 L(A) = ?* } TQBF 问题 量词: ? 、? 对于自然数,语句 ?x [ x+1x ] 为真。 ? y [ y+y=y ]为假。 辖域:量词的作用范围。 前束范式: 形如 ? = Q1x1 Q2 x2 … Qk xk B, Qi 为?或? 量词化布尔公式:带量词的布尔公式(必须是前束范式)。 全量词化:公式中的每个变量都出现在某一量词的辖域中。 TQBF 问题就是要判定一个全量词化的布尔公式是真是假。 TQBF={ ? ? 是真的全量词化的布尔公式} TQBF 问题 下面,证明 TQBF 是 PSPACE 难的。 设 A 是一个由 TM M 在 nk 空间内判定的语言,k 是某个常数。 下面给出一个从 A 到 TQBF 的多项式时间归约。该归约把字符串 w 映射为一个量词化的布尔公式 ? , ? 为真当且仅当 M 接受 w。 为了说明怎样构造 ? ,需解决一个更一般的问题。利用两个代表格局的变量集合 c1 和 c2 及一个数 t 0,构造一个公式? c1, c2 , t。如果把 c1 和c2 赋为实际的格局,则该公式为真当且仅当 M 能够在最多 t 步内从 c1到达 c2。然后,可以令 ? 是公式? cstart , caccept, h,其中 h= 2df(n) ,d 是一个选取的常数,使得 M 在长为 n 的输入上可能的格局数不超过 2df (n) 。这里,令f(n)=nk。为了方便,假设 t 是 2 的幂。 类似库克-列文定理的证明,该公式对带单元的内容编码。对应于单元的可能设置,每个单元有几个相关的变量,每个带符号和状态有一个变量。每个格局有nk个单元,所以用 O(nk) 个变量编码。 博弈的必胜策略 博奕论:每个游戏常有 2 个以上的参加者,他们(局中人)在游戏中都有自己的切身利益,每个局中人都有自己的可行行动集供自己选择,这种选择毫无疑问地会影响到其他局中人的切身利益。游戏中各个局中人理性地采取/选择自己的策略行为,使得在这种相互制约相互影响的依存关系中,尽可能提高自己的利益所得,这正是游戏理论的关键所得。 要点: 博奕的各方都是理性的 各人的选择都是为取得利益的最大化 囚徒困境 1950年,就职于兰德公司的梅里尔·弗勒德(Merrill Flood)和梅尔文·德雷希尔(Melvin Dresher)拟定出相关困境的理论,后来由顾问艾伯特·塔克(Albert Tucker)以囚徒方式阐述,并命名为“囚徒困境”。 经典的囚徒困境如下: 两个嫌犯被捕后被关在相互隔离的牢房中。他们面临的选择是:或者坦白或者保持沉默(即不坦白)。他们被告知: ① 如果某个嫌疑犯坦白而其同伙不坦白,则坦白者可获自由而拒不坦白者要被判10年监禁; ② 如果二人都坦白,则二人都被判5年监禁; ③ 如果二人都不坦白,则二人皆被判1年监禁。 上述情况我们亦可用一支付矩阵表示如下: 嫌疑犯乙 坦白沉默 嫌疑犯甲坦白 -5, -50, -10 沉默 -10, 0-1, -1 在这种情况下,两个嫌犯将如何决策和选择呢? 博弈的必胜策略 博奕和量词紧密相关 一个量化语句?一个博弈 作用:描述和解释该语句的含义 一个博弈?一个量化语句 作用:理解该博弈的复杂性 例:前束范式的量词化布尔公式 f=$x1x2$x3…Qxk[?] Q:$/, ?--去掉量词的公式 f与下面的博弈关联: 2名选手A,E,轮流为x1, x2 , x3 , … , xk 选值 博弈的必胜策略 博弈的必胜策略 判定在与某具体公式关联的公式博弈中哪方有必胜策略的问题是 PSPACE 完全的。 FORMULA-GAME={ ? 在与 ? 关联的公式博奕中选手E有必胜策略 } 广义地理学 地理学 一种儿童游戏。 选手们轮流给世界各地的城市命名。 每一座选中的城市的首字母必须与前一座城市的尾字母相同,不得重复。 游戏从某指定的起始城市开始,以某方无法延续而认输为止。 例如: 开始:Peoria Peoria?Amherst?Tucson?Nashua… 结束:直到某方被难倒 地理学图 广义地理学 按照地理学规则翻译为图表示法 一名选手从指定的起始节点开始,然后选手们交替地挑选结点,形成图中的一条简单路径。 要求是简单路径 (即每个节点只能用 1 次) 对应于要求城市不能重复。 第 1 个不能扩展路径的选手输掉比赛。 广义地理学游戏样例 广义地理学游戏样例 L 类和 NL 类 线性空间复杂性界限:f (n)=n 亚线性空间复杂性界限:f (n)n 在时间复杂性中不考虑亚线性,因为亚线性连输入都不能读完。 亚线性空间复杂性中能读完全部输入,但没有足够的空间存储全部输入。解决办法是修改计算模型——包含只读带的两带图灵机。 两带图灵机 一条只读输入带:相当于CD_ROM 一条读写工作带:可修改。 只有工作带上被扫描的单元才构成这种图灵机的空间复杂性。 作业 8.1、8.3、8.12、8.21、8.25、8.28 选手I必胜 1 3 6 4 5 2 7 8 9 从结点1开始,选手I先做选择 选手II必胜 1 3 6 4 5 2 7 8 9 从结点1开始,选手I先做选择 现在方向变成节点3?节点6 广义地理学 判定在广义地理学游戏中哪一方有必胜策赂的问题是PSPACE全的。 GG = { G, b 在图 G 上以结点 b 起始的广义地理学游戏中,选手 I 有必胜策略 } 定理8.11 GG 是 PSPACE 完全的。 证明略 广义地理学 下面的的算法判定在广义地理学实例中,选手I是否有必胜策略。换 句话说,它判定GG。现证明它在多项式空间内运行: M=“对输入G,b,G是有向图,b是G的结点: 1)若b出度为0,则拒绝,因为选手I立即输。 2)删去结点b以及与它关联的所有箭头,得到一个新图G1。 3)对于b原先指向的每个节点b1, b2, …, bk,在G1 , bi上递归地调用 M。 4)若所有调用都接受,则选手?在原先博弈中有必胜策略,所以拒绝。 否则,选手I?没有必胜策赂,而选手I有必胜策略,因此接受。” * 主要内容 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 L 类和 NL 类 定义8.12 L 是确定型图灵机在对数空间内可判定的语言类。 L = SPACE(log n) NL是非确定型图灵机在对数空间内可判定的语言类。 NL = NSPACE(log n) L 类和 NL 类 * 例8.13 语言 A={0k1k k?0 } 是 L 的成员。在7.1节中描述了一个判定 A 的图灵机,它左右来回扫描输人,删掉匹配的 0 和 1。该算法用线性空间记录哪些位置已经被删掉,但可以修改为只使用对数空间。 判定 A 的对数空间 TM 不能删除输入带上已经匹配的 0 和 1,因为该带是只读的。 机器在工作带上用二进制分别数 0 和 1 的数目。唯一需要的空间是用来记录这两个计数器的。在二进制形式,每个计数器只消耗对数空间,因此算法在 O(log n) 空间内运行。所以 A?L。 L 类和 NL 类 * 例8.14 语言 PATH = { G, s, t G 是包含从 s 到 t 的有向路径的有向图 }。定理7.12证明 PATH 属于P,但是给出的算法消耗线性空间。现在能否找到只消耗对数空间的算法? 判定 PATH 的非确定型对数空间图灵机从节点 s 开始运算, 非确定地猜测从 s 到 t 的路径的每一步。 机器在工作带上只记录每一步当前节点的位置,而不是整条路径 (否则将超出对数空间的要求)。 机器从当前节点所指向的节点中非确定地选择下一个节点。 它反复执行这一操作,直到到达结点 t 而接受,或者执行 m 步以后拒绝,其中 m 是图中的节点数。 所以 PATH 属于 NL。 L 类和 NL 类 定义8.15 若 M 是一个有单独的只读输入带的图灵机,w 是输入,则 M 在 w 上的格局包含状态、工作带和两个读写头位置。输入 w 不作为 M 在 w 上的格局的一部分。 如果 M 在 f(n) 空间内运行,w 是长为 n 的输入,则 M 在 w 上的格局数是 n2O(f(n))。 我们几乎只关注不小于 log n 的空间界限 f(n)。 萨维奇定理表明非确定型 TM 可以转化为确定型 TM,而空间复杂性 f(n) 只增加平方。可以推广萨维奇定理,使它对于亚线性空间界限 f(n) ? log n 也能成立。 * 主要内容 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 NL完全性 定义8.16 对数空间转换器(log space transducer)是有一条只读输入带、一条只写输出带和一条读写工作带的图灵机。工作带可以包含 O(logn) 个符号。 对数空间转换器 M 计算一个函数 f : ?*? ?*,其中 f(w) 是把 w 放在 M 的输入带上启动 M 运行,到 M 停机时输出带上存放的字符串。称 f 为对数空间可计算函数。 如果语言 A 通过对数空间可计算函数 f 映射可归约到语言 B,则称 A 对数空间可归约到 B,记为 A≤L B。 NL完全性 定义8.17 语言 B 是 NL 完全的,如果 1) B ? NL,并且 2) NL 中的每个 A 对数空间可归约到 B。 如果一个语言对数空间可归约到另一个己知属于 L 的语言,则这个语言也属于 L。 NL完全性 定理8.18 A≤L B 且 B ? L, 则 A ?L。 一种思路,A 的对数空间算法首先用对数空间归约 f 把输入 w 映射为 f(w),然后应用 B 的对数空间算法。 但是存储 f(w) 的空间需求量可能太大,不能放进对数空间界限内,所以需要修改这种方法。 A 的机器 MA 不再算出整个 f(w),而是当 B 的机器 MB 需要的时候计算f(w)的个别符号。 在模拟过程中, MA 记录 MB 的输入头在 f(w) 上的位置。每一次 MB 移动时, MA 重新开始在 w 上计算 f,除了所需要的 f(w) 上的位置以外,其余输出全部忽略。这么做可能不时地要求重新计算 f(w) 的某些部分,因而在时间复杂性方面是低效的。 这种方法的好处是在任何时刻只需存储 f(w) 的一个符号,其结果是用时间来换取空间。 NL 完全性 推论8.19 若有一个 NL 完全语言属于 L,则 L=NL。 定理8.20 PATH 是 NL 完全的。 推论8.21 NL ? P。 定理8.22 NL =coNL。 博奕和量词紧密相关。一个量化的语句有一个对应的博弈;反之,一个博奕也经常有一个对应的量化语句。这种对应关系在以下这几个方面是有用的。首先.把一个包含许多量词的数学语句用对应的博奔表达出来,可以洞悉该语句的含义。其次,把一个博弈用量化语句表达出来有助于理解该博弈的复杂性。 为了阐明博弈与量词之间的对应关系,本节描述一种称为公式博弈的人工博弈。 设? = ?X1 ? X2 ?X3…QXk[?]是一个前束范式的量词化布尔公式。这里Q代表量词?或者? 。让?与下面的博奔相关联。两名选手,称为选手A和选手E,轮流为变量X1,…,Xk选值。选手A为那些?量词约束的变量选值,选手E为那些?量向约束的变量选值。进行的顺序与公式开头量词出现的顺序相同。在游戏结束时,利用选手给变量挑选的值宣布结果。如果? (即删去量词后的那部分公式)此时是TRUE,则选手E赢;如果?此时是FALSE,则选手A赢。 * 计算理论 * 主要内容 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.1 令 M 是一个在所有输入上都停机的确定型图灵机。M 的空间复杂度是一个函数 f : N?N,其中 f (n) 是 M 在任何长为 n 的输入上扫描带方格的最大数。 若 M 的空间复杂度为 f(n),也称 M 在空间 f(n)内运。 如果 M 是对所有输入在所有分支上都停机的非确定型图灵机,则定义它的空间复杂度 f (n) 为 M 在任何长为 n 的输入上,在任何计算分支上所扫描的带方格的最大数。 通常用渐进记法估计图灵机的空间复杂度。 空间复杂性类 定义8.2 令 f : N?R+是一个函数,空间复杂性类 SPACE(f(n))和 NSPACE(f(n))定义如下: SPACE(f(n)) ={ L L是被 O(f(n)) 空间的确定型图灵机判定的语言} NSPACE(f(n)) = { L L是被 O(f(n)) 空间的非确定型图灵机判定的语言} M1 = “对输入 ? , ? 是布尔公式: 1) 对于 ? 中变量 x1 , … , xm 的每个线) 计算 ? 在该线,则接受;否则拒绝。” 显然机器 M1 是在线性空间内运行,因为每一次循环都可以复用带子上的同一部分。该机器只需存储当前的真值赋值,这只需消耗 O(m) 空间。因为变量数 m 最多是输入长度 n,所以该机器在空间 O(n) 内运行。 首先给出非确定型线性空间算法来判定该语言的补 ALLNFA 。 算法的思想是利用非确定性猜测一个被 NFA 拒绝的字符串,然后用线性空间跟踪该 NFA,看它在特定时刻处在什么状态。 需要注意的是,此时还不知道该语言是否在 NP 或 coNP 中。 N=“对于输入 M,M 是 NFA: 1) 置标记于 NFA 的起始状态。 2) 重复执行下面的语句 2q 次,这里 q 是 M 的状态数。 3) 非确定地选择一个输入符号并移动标记到 M 的相 应状态,来模拟读取那个符号。 4) 如果步骤 2 和 3 表明 M 拒绝某些字符串,即如果在某一时刻所有标记都不落在 M 的接受状态上,则接受;否则拒绝。” 例:语言的非确定性空间复杂性 * 如果 M 拒绝某个字符串,则它必定拒绝一个长度不超过 2q 的字符串,因为在任何被拒绝的更长的字符串中,上面算法中所描述的标记的位置分布必定重复出现。介于两次重复出现之间的那一段字符串可以删去,从而得到更短的被拒绝的字符串。所以 N 可判定 ALLNFA 的补。 该算法仅需要的空间是用来存放标记的位置和重复计数器,这在线性空间就可以得到解决。因此,该算法在非确定的空间 O(n) 内运行。 萨维奇定理 定理8.5 对于任何函数 f : N?R+ ,其中 f(n)? n, NSPACE( f(n) ) ? SPACE( f 2(n) ) 给定 NTM 的两个格局 c1 和 c2,以及一个整数 t,要求判定该NTM 能否在 t 步内从 c1 变到 c2,称该问题为可产生性问题。 如果 c1 是起始格局,c2 是接受格局,t 是非确定型机器所使用的最大步数,那么通过求解可产生问题,就能够判断机器是否接受输入。 可以用一个确定的递归算法求解可产生问题。运算过程如下: 寻找一个中间格局 cm,递归地检查 c1 能否在 t/2 步内到达 cm, cm 能否在 t/2步内到达 c2,重复使用两次递归检查的空间可节省空间开销。 递归的每一层需要 O(f(n))空间来存储一个格局。递归的深度是 log 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 的一个格局能否在指定的步数内产生另一个格局。 设 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 能否在一步内产生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) 若此时还没有接受,则拒绝。” 萨维奇定理的证明 现在定义 M 来模拟 N。首先修改 N,当它接受时,把带子清空并把读写头移到最左边的单元,从而进入称为 caccept 的格局。 令 cstart 是 N 在 w 上的起始格局。选一个常数 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 在递归调用自己时,它都把所处的步骤号、c1、c2 和 t 的都存储在栈中,所以递归调用时返回时能恢复这些值。因此在递归的每一层需要增加 O(f(n)) 空间。 此外,递归的每一层把 t 的值减小一半。开始时 t 等于2df(n) ,所以递归的深度是 O(log 2df(n)) 或 O(f(n)) ,因此共消耗空间是 O(f2(n)) 。 * 主要内容 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 PSPACE 类 定义8.6 PSPACE 是在确定型图灵机上、在多项式空间内可判定的语言类。换言之, PSPACE =∪k SPACE(nk) PSPACE 类的非确定型版本 NPSPACE,可以类似地用NSPACE 类来定义。 然而,任何多项式的平方仍是多项式,根据萨维奇定理,则NPSPACE = PSPACE 。 在例8.3和8.4中,已经说明了 SAT 属于 SPACE(n), ALLNFA 属于 coNSPACE(n) ,而根据萨维奇定理,确定型空间复杂度对补运算封闭,所以 ALLNFA 也属于 SPACE(n2) 。因此 SAT 和ALLNFA 这两个语言都在 PSPACE 中。 PSPACE 类 考察 PSPACE 与 P 和 NP 的关系。 显而易见,P ? PSPACE,因为运行快的机器不可能消耗大量的空间。更精确地说,当 t(n)≥n 时,由于在每个计算步上最多能访问一个新单元,因此,任何在时间 t(n) 内运行的机器最多能消耗 t(n) 的空间。 类似地,NP ? NPSPACE ,所以 NP ? PSPACE 。 反过来,根据图灵机的空间复杂性可以界定它的时间复杂性。 对于 f (n )≥n ,通过简单推广引理5.7 的证明可知,一个消耗f(n) 空间的 TM 至多有 f(n)2O(f(n)) 个不同的格局,也必定在时间 f(n)2O(f(n)) 内运行,得出: PSPACE ?EXPTIME = ∪k TIME(2nk) P ? NP ? PSPACE=NPSPACE ?EXPTIME * 主要内容 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 PSPACE 完全性 定义8.7 语言 B 是PSPACE完全的。若它满足下面两个条件: 1) B 属于 PSPACE。 2) PSPACE中的每一个语言A多项式时间可归约到B。 若 B 只满足条件 2,则称它为 PSPACE难的。 TQBF 问题 定理8.8 TQBF 是 PSPACE 完全的。 证明思路 (1) 为了证明TQBF属于PSPACE,给出一个简单的算法。该算法首先给变量赋值,然后递归地计算公式在这些值下的真值。从这些信息中算法就能确定原量化公式的线) 为了证明PSPACE中的每个语言A在多项式时间内可归约到TQBF,从判定 A 的多项式空间界限图灵机开始。然后给出多项式时间归约,它把一个字符串映射为一个量词化的布尔公式ф,ф 模拟机器对这个输入的计算。公式为真的充分必要条件是机器接受。 改用一种与萨维奇定理的证明相关的技术来构造公式。该公式把画面分成两半,利用全称量词的功能,用公式的同一部分来代表每一半。结果产生短得多的公式。 TQBF 问题 首先,给出一个判定 TQBF 的多项式空间算法: T = “对输入 ? , ? 是一个全量词化的布尔公式: 1) 若 ? 不含量词,则它是一个只有常数的表达式。计算 ? 的值,若为真,则接受;否则,拒绝。 2) 若 ? 等于 ?x ?,在 ? 上递归地调用 T,首先用 0 替换 x,然后用 1 替换 x。只要有一个结果是接受,则接受;否则,拒绝。 3) 若 ? 等于 ?x ?,在 ? 上递归地调用 T,首先用 0 替换 x,然后用 1 替换 x。若两个结果都能接受,则接受;否则,拒绝。” 算法 T 显然判定 TQBF 。 空间复杂性:它递归的深度最多等于变量的个数。在每一层只需存储一个变量的值,所以全部空间消耗是 O(m),其中 m 是 ? 中出现的变量的个数。因此 T 在线性空间内运行。 TQBF问题 若 t=1,则容易构造 ? c1, c2 , t。 设计公式,使之表达要么 c1 等于 c2,要么 c1能在 M 的一步内变到 c2 。 为了表达相等性,使用一个布尔表达式来表示:代表 c1 的每一个变量与代表 c2 的相应变量包含同样的布尔值。 为表达第二种可能性,采用库克-列文定理的证明中给出的技巧,构造布尔表达式表示,代表 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, c2 , 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 ,它就是 TRUE。然而,它太长了。构造过程中涉及的递归的每一层都把 t 的值减小一半,却把公式的长度增加了大约一倍,最后导致公式的长度大约是 t,开始时 t= 2df(n),所以这种方法结出的公式是指数长的。 为了缩短公式的长度,除了使用?量词以外,再利用?量词。令 ? c1, c2 , t = ?m1 ?(c3, c4)?{(c1, m1) ,(m1, c2)}[? c3, c4 , t/2 ] 新引入的变量代表格局 c3 和 c4,它允许把两个递归的子公式“折叠”为一个子公式,而保持原来的意思。通过写成 ?(c3, c4 ) ?{(c1, m1) ,(m1, c2)} 就指明了代表格局 c3 和 c4 的变量可以分别取 c1 和 m1 的变量的值,或者 m1和 c2 的变量的值,结果公式? c3, c4 , t/2 在两种情况下都为线, c2)}替换为等价的结构 ?x[(x=y?x=z) ?…] ,从而得到语法正确的量化布尔公式。 为了计算公式个 ? cstart, caccept,h 的长度,其中 h= 2df(n) ,注意到递归增加的那部分公式的长度与格局的长度呈线性关系,所以长度是O(f(n)) 。递归的层数是log2df(n) 或 O(f(n)) 。所以所得到的公式的长度是O(f 2(n)) 。 选手E所对应的量词 选手A所对应的量词 选手E取值 选手A取值 对变量进行处理的语句 TRUE: E胜 FALSE: A胜 其中A对任意量词约束的变量选值; E对存在量词约束的变量选值 例8.9 f1=$x1x2$x3[(x1úx2)ù(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必胜: f2=$x1x2$x3[(x1úx2)ù(x2úx3)ù(x2úx3)] ? 必胜策略 一个选手有必胜策略,如果他在博弈双方都下出最佳步骤时能赢 博弈的必胜策略 定理8.10 FARMULA-GAME 是 PSPACE 完全的。 要证FORMULA-GAME是PSPACE完全的 FORMULA-GAME=TQBF FORMULA-GAME={ ? ?是真的全量词化布尔公式 } FARMULA-GAME 是 PSPACE 完全的 公式? = ?x1 ?x2 ?x3 … [?] 是 TRUE 的条件是: 存在 x1 的某种赋值,使得对于 x2 的任意赋值,存在 x3 的某种赋值,使得…等等,其中 ? 在这些变量的赋值下是 TRUE。 类似地,选手 E 在与 ? 关联的博奔中有必胜策略的条件是: 选手 E 可以给 x1 赋某个值,使得对于 x2 的任意赋值,选手 E 可以给 x3 赋一个值,使得…等等, ? 在变量的这些赋值下为 TRUE 。 当公式不在存在量词与全称量词之间交替时,同样的推理也能成立。 如果 ? 的形式为 ?x1 , x2 , x3 ?x4 , x5 ?x6[?], 选手 A 在公式博弈中走头三步,给 x1 , x2 和 x3 贼值;然后选手 E 走两次,给 x4 和 x5 贼值;最后选手 A 给x6 赋一个值。 因此, ? ? TQBE 恰好当 ? ? FARMULA-GAME 时成立,由定理8.8,本定理成立。 类似成语接龙 结点是世界各地的城市

  “原创力文档”前称为“文档投稿赚钱网”,本网站为“文档C2C交易模式”,即用户上传的文档直接卖给(下载)用户,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有【成交的100%(原创)】

本文链接:http://scrinzoom.com/qianshufanshi/504.html