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

例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, -5　　　　0, -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… 结束：直到某方被难倒 地理学图 广义地理学 按照地理学规则翻译为图表示法 一名选手从指定的起始节点开始，然后选手们交替地挑选结点，形成图中的一条简单路径。 要求是简单路径 (即每个节