第5期 高强，等：时间复杂性和空间复杂性研究 ·533· 走棋到分出胜负，共产生的局面的数量为2× 复使用，根据萨维奇定理0]，如果一台非确定型图 22esm,用渐近记法表示，为2(w1so),是指数级 灵机能够利用f(n)空间解决某个问题，那么一台确 的。即该游戏属于EXPTIME问题。 定型图灵机能够在至多f2(n)空间解决相同的问 3 空间复杂性 题。由该定理可得推论：NPSPACE=PSPACE)。 3.3 PSPACE的完全问题 空间复杂性是指求解一个问题所需多少空间。 一个语言B属于PSPACE的完全问题[) 属于某空间复杂性类的问题，它的求解难度要大于 (PSPACE-complete),如果它满足2个条件： 属于时间复杂性类的问题，因为运行快的算法不可 1)B属于PSPACE; 能消耗大量的空间，也就是说在每个计算步上最多 2)每个属于PSPACE的问题在多项式时间内 能访问一个新单元，所以，任何在时间t(n)内运行 归约到B。 的机器最多能消耗t(n)的空间山。与时间复杂性 PSPACE-complete属于PSPACE类中最困难的 一样，也是采用渐近记法来计算求解问题的空间复 问题，和NP-complete的定义类似，如果B仅仅满足 杂性。另外，也可以通过证明，给一些问题的空间复 条件2，说明B不属于PSPACE,可以说它是 杂性分类来说明该问题求解的困难程度。 PSPACE-hard,那么B可能更加难解。常见的属于 3.1确定型多项式空间复杂性 PSPACE-complete的问题有QBF[6(量词的布尔公 确定型多项式空间复杂性(deterministic polyno- 式)、formula game(公式博弈)、棋类游戏)(chess mial space,PSPACE)是指能够被确定型图灵机在多 game)等。 项式空间内解决的问题的集合[9)。属于PSPACE 举例广义地理学游戏1(generalized geogra- 问题举例：全量词化的布尔公式(true qualified bool-- phy game)是一种地理学游戏，选手们轮流给出世界 ean formula,TQBF)[o,形如：x3y(x∧y),该公 各地的城市名称。每一座选中的城市的首字母必须 式的含义是：对于任意的x,存在y,使得x八y为真。 与前一座城市的尾字母相同，城市的名称不允许重 全量词化的布尔公式是指公式中出现的所有变量， 复，游戏从某个指定的城市开始，直到某一方不能延 都有量词对其约束[6。TQBF问题就是判定一个全 续为止。对于证明某问题属于PSPACE-complete的 量词化的布尔公式是真或假的问题，它属于 过程与NP-complete的证明类似，首先要证明该问 PSPACE。其多项式空间算法)如下： 题属于PSPACE,文献[1]中给出了一个多项式空间 T=对输入的全量词化的布尔公式： 的算法，证明了该问题可在多项式空间求解。然后 1)若该公式不含量词，则它是一个只有常数的 选择了一个已被证明为PSPACE-complete类的问题 表达式。计算公式的值，若为真，则接受；否则，则拒 如formula game(实际上，它就是TQBF,只是假设有 绝。 2个选手交替为每个变量赋值)并独出心裁地构造 2)若公式等于3xp,在p上递归地调用T,首 了一个归约，如图3 先用0替换x,然后用1替换x。只要有一个结果是 True (b)False 接受，则接受：否则，拒绝。 3)若p等于Vxp,在p上递归调用T,首先用 0替换x,然后用1替换x。若2个结果都是接受，则 接受：否则，拒绝。 算法分析该算法模拟的是量词化布尔公式的 计算过程，每一次递归就是对公式中最左侧的一个 量词所约束的变量赋值（假设该公式为前束范 式1)。递归的深度就是该公式中中包含的变量的 个数，设为m,因此每层只需存储一个变量，所以该 算法的空间消耗是O(m)。因此该算法属于多项式 空间算法。 3.2 NPSPACE 它是指能够被非确定型图灵机在多项式空间内 图3归约的全部结构 解决的问题的集合。空间与时间不同，它可以被重 Fig.3 The complete structure of reducibility走棋 到 分 出 胜 负， 共 产 生 的 局 面 的 数 量 为 ２ × ２ ２ｅｎ／ ｌｏｇ（ｎ） ，用渐近记法表示，为 ２ Ｏ（ｎ／ ｌｏｇ（ｎ）） ，是指数级 的。 即该游戏属于 ＥＸＰＴＩＭＥ 问题。 ３ 空间复杂性 空间复杂性是指求解一个问题所需多少空间。 属于某空间复杂性类的问题，它的求解难度要大于 属于时间复杂性类的问题，因为运行快的算法不可 能消耗大量的空间，也就是说在每个计算步上最多 能访问一个新单元，所以，任何在时间 ｔ（ ｎ）内运行 的机器最多能消耗 ｔ（ ｎ）的空间［１］ 。 与时间复杂性 一样，也是采用渐近记法来计算求解问题的空间复 杂性。 另外，也可以通过证明，给一些问题的空间复 杂性分类来说明该问题求解的困难程度。 ３．１ 确定型多项式空间复杂性 确定型多项式空间复杂性（ｄｅｔｅｒｍｉｎｉｓｔｉｃ ｐｏｌｙｎｏ⁃ ｍｉａｌ ｓｐａｃｅ，ＰＳＰＡＣＥ）是指能够被确定型图灵机在多 项式空间内解决的问题的集合［１９］ 。 属于 ＰＳＰＡＣＥ 问题举例：全量词化的布尔公式（ｔｒｕｅ ｑｕａｌｉｆｉｅｄ ｂｏｏｌ⁃ ｅａｎ ｆｏｒｍｕｌａ，ＴＱＢＦ） ［６］ ，形如： ∀ｘ∃ｙ（ｘ ∧ ｙ） ，该公 式的含义是：对于任意的 ｘ，存在 ｙ，使得 ｘ ∧ ｙ 为真。 全量词化的布尔公式是指公式中出现的所有变量， 都有量词对其约束［６］ 。 ＴＱＢＦ 问题就是判定一个全 量词 化 的 布 尔 公 式 是 真 或 假 的 问 题， 它 属 于 ＰＳＰＡＣＥ。 其多项式空间算法［１］如下： Ｔ ＝ 对输入的全量词化的布尔公式： １）若该公式不含量词，则它是一个只有常数的 表达式。 计算公式的值，若为真，则接受；否则，则拒 绝。 ２）若公式等于∃ ｘφ ，在 φ 上递归地调用 Ｔ，首 先用 ０ 替换 ｘ，然后用 １ 替换 ｘ。 只要有一个结果是 接受，则接受；否则，拒绝。 ３）若 φ 等于 ∀ｘφ ，在 φ 上递归调用 Ｔ，首先用 ０ 替换 ｘ，然后用 １ 替换 ｘ。 若 ２ 个结果都是接受，则 接受；否则，拒绝。 算法分析 该算法模拟的是量词化布尔公式的 计算过程，每一次递归就是对公式中最左侧的一个 量词所约束的变量赋值 （ 假设该公式为前束范 式［１８］ ）。 递归的深度就是该公式 φ 中包含的变量的 个数，设为 ｍ，因此每层只需存储一个变量，所以该 算法的空间消耗是 Ｏ（ｍ）。 因此该算法属于多项式 空间算法。 ３．２ ＮＰＳＰＡＣＥ 它是指能够被非确定型图灵机在多项式空间内 解决的问题的集合。 空间与时间不同，它可以被重 复使用，根据萨维奇定理［２０］ ，如果一台非确定型图 灵机能够利用 ｆ（ｎ）空间解决某个问题，那么一台确 定型图灵机能够在至多 ｆ ２ （ ｎ） 空间解决相同的问 题。 由该定理可得推论： ＮＰＳＰＡＣＥ ＝ ＰＳＰＡＣＥ ［１］ 。 ３．３ ＰＳＰＡＣＥ 的完全问题 一个 语 言 Ｂ 属 于 ＰＳＰＡＣＥ 的 完 全 问 题［１］ （ＰＳＰＡＣＥ⁃ｃｏｍｐｌｅｔｅ），如果它满足 ２ 个条件： １）Ｂ 属于 ＰＳＰＡＣＥ； ２）每个属于 ＰＳＰＡＣＥ 的问题在多项式时间内 归约到 Ｂ。 ＰＳＰＡＣＥ⁃ｃｏｍｐｌｅｔｅ 属于 ＰＳＰＡＣＥ 类中最困难的 问题，和 ＮＰ⁃ｃｏｍｐｌｅｔｅ 的定义类似，如果 Ｂ 仅仅满足 条件 ２， 说 明 Ｂ 不 属 于 ＰＳＰＡＣＥ， 可 以 说 它 是 ＰＳＰＡＣＥ⁃ｈａｒｄ，那么 Ｂ 可能更加难解。 常见的属于 ＰＳＰＡＣＥ⁃ｃｏｍｐｌｅｔｅ 的问题有 ＱＢＦ ［６］ （量词的布尔公 式）、ｆｏｒｍｕｌａ ｇａｍｅ ［１］ （公式博弈）、棋类游戏［１］ （ｃｈｅｓｓ ｇａｍｅ）等。 举例 广义地理学游戏［１］ （ ｇｅｎｅｒａｌｉｚｅｄ ｇｅｏｇｒａ⁃ ｐｈｙ ｇａｍｅ）是一种地理学游戏，选手们轮流给出世界 各地的城市名称。 每一座选中的城市的首字母必须 与前一座城市的尾字母相同，城市的名称不允许重 复，游戏从某个指定的城市开始，直到某一方不能延 续为止。 对于证明某问题属于 ＰＳＰＡＣＥ⁃ｃｏｍｐｌｅｔｅ 的 过程与 ＮＰ⁃ｃｏｍｐｌｅｔｅ 的证明类似，首先要证明该问 题属于 ＰＳＰＡＣＥ，文献［１］中给出了一个多项式空间 的算法，证明了该问题可在多项式空间求解。 然后 选择了一个已被证明为 ＰＳＰＡＣＥ⁃ｃｏｍｐｌｅｔｅ 类的问题 如 ｆｏｒｍｕｌａ ｇａｍｅ（实际上，它就是 ＴＱＢＦ，只是假设有 ２ 个选手交替为每个变量赋值）并独出心裁地构造 了一个归约，如图 ３ ［１］ 。 图 ３ 归约的全部结构 Ｆｉｇ．３ Ｔｈｅ ｃｏｍｐｌｅｔｅ ｓｔｒｕｃｔｕｒｅ ｏｆ ｒｅｄｕｃｉｂｉｌｉｔｙ 第 ５ 期 高强，等：时间复杂性和空间复杂性研究 ·５３３·