PSPACE 是这样一类判定问题:确定性图灵机能够求解它们,且所用工作内存至多为输入长度的某个多项式。它是计算复杂性理论中的核心复杂度类,刻画了这样一种计算:执行步数可能达到指数级,但在任意时刻,内存中只保留多项式量的信息。它的完全问题包括求全量化布尔公式的真值,以及判定某些有限且对局长度为多项式的博弈中哪一方能够获胜。
形式定义
令 表示这样一类问题:对于长度为 的输入,确定性图灵机能够使用 个工作带单元判定这些问题。那么
判定问题可以表示为一种形式语言,即答案为“是”的所有输入字符串组成的集合。判定这种语言的机器必须在每个输入上停机,接受属于该语言的字符串,并拒绝不属于该语言的字符串。
标准的空间计量模型提供一条只读输入带,以及独立的可读写工作带。输入本身不计入工作内存,但从输入复制到工作带上的任何信息都要计入。对于多项式空间,只要开销为多项式量级,对机器模型或输入编码所作的合理调整就不会改变这一复杂度类。
这一定义涉及的是空间复杂度,而不是时间复杂度。内存可以被覆写并重复使用。因此,一次计算所执行的操作次数可以远远超过它所使用的内存单元数。
为什么多项式空间允许指数时间
机器的格局记录了其内部状态、纸带内容和读写头位置。对于一台固定的机器,若它使用 的工作空间,且 ,那么在给定输入上,可能的格局数至多为
个。
确定性计算一旦再次到达完全相同的格局,就会永远重复此后的行为。因此,必须停机的判定器在停机前不能重复到达某个格局。由此可知,多项式空间判定器的运行时间至多为指数时间,其中指数为输入长度的某个多项式。
这说明了内存与运行时间之间的一项基本差异。一个算法可以搜索一棵指数规模的搜索树,而不必将整棵树保存在内存中。深度优先搜索只保留当前路径,以及恢复尚未完成的分支搜索所需的信息。如果路径长度和每个节点的描述长度都有多项式上界,那么即使搜索访问了指数多个节点,也可能只使用多项式空间。
这一论证并未证明每个 PSPACE 问题都需要指数时间。有些 PSPACE 问题具有多项式时间算法;是否所有 PSPACE 问题都如此,目前仍未解决。
与其他复杂度类的关系
标准的包含关系为
其中:
- P复杂度类由可在确定性多项式时间内判定的问题组成。
- NP复杂度类由这样的问题组成:其“是”答案具有多项式长度的证书,且证书可在多项式时间内验证。
- EXPTIME 复杂度类由可在确定性时间 内判定的问题组成。
每次多项式时间计算至多使用多项式空间,因此有 。对于 NP 问题,确定性机器可以枚举候选证书,逐一验证,并在此过程中重复使用内存。因此有 。
目前尚不知道上述三个相邻的包含关系中,是否有任何一个是严格包含。特别是,、 和 是否成立,都是未解决的问题。不过,时间层级定理蕴含 ,所以整条包含链不可能全部归并为同一个类。
如果 ,那么 。反过来,即使P与NP问题最终以两者相等得到解决,单凭这一结果也不能证明 P 等于 PSPACE。
非确定性空间与萨维奇定理
令 NPSPACE 表示由非确定性多项式空间机器定义的复杂度类。一个基本结果是
这可由沃尔特·萨维奇于 1970 年证明的萨维奇定理推出。该定理的标准形式是,对于满足适当条件的空间界 ,有
多项式的平方仍然是多项式,因此在多项式空间这一层面上,非确定性并不会增强计算能力。
证明采用了在机器格局图上递归判断可达性的方法。它不存储整条计算路径,而是判断能否在某个中间格局处,将路径拆分成两条较短的路径。各个中间格局被依次尝试,从而以额外的计算时间换取较少的内存占用。
补运算及其他封闭性质
PSPACE 对补运算封闭:
将确定性判定器的接受结果与拒绝结果互换,就能得到判定补语言的确定性判定器。这与 NP 不同:NP 是否等于 coNP 仍未解决。
PSPACE 还对有限并、有限交以及多项式时间多对一归约封闭。对于最后一项性质,多项式时间归约产生的输出长度是多项式量级的,因此针对该输出运行的多项式空间算法,其空间用量相对于原始输入长度仍为多项式量级。
PSPACE完全性
如果 PSPACE 中的每个问题,都能通过一个可在多项式时间内计算且保持是非答案不变的映射,转换为某个问题,那么称该问题在多项式时间多对一归约下是 PSPACE难的。如果它既是 PSPACE难的,又属于 PSPACE,则称其为 PSPACE完全的。
这是两项独立的要求:
- **归属:**建立一个多项式空间判定过程。
- **难度:**证明每个 PSPACE 问题都可归约到该问题,通常通过将一个已知的 PSPACE完全问题归约到它来实现。
这一总体思路与NP完全性中的方法相同,只是以 PSPACE 作为参照类。由于 NP 包含于 PSPACE,在采用相同归约约定的情况下,PSPACE完全问题必然也是 NP难的。
如果任何一个 PSPACE完全问题具有多项式时间算法,那么
因此,PSPACE完全性强烈表明,不应期待存在通用的多项式时间算法,但它并不是这种算法不可能存在的无条件证明。它也不意味着每个输入都很难处理,或实用方法无法求解有价值的受限实例。
典型的完全问题
全量化布尔公式
量化布尔公式真值问题通常称为 TQBF 或 QBF,是标准的 PSPACE完全问题。其输入是包含存在量词和全称量词的闭布尔公式,例如
这个公式为真:无论 被固定为哪个值,都存在一个合适的 值,使内部公式为真。
存在量词询问是否至少有一种赋值成立;全称量词询问两种赋值是否都成立。递归求值过程在探索这些可能性时,只需存储当前赋值和求值状态。递归深度受公式长度限制,因此即使需要考察指数多种赋值组合,多项式空间也已足够。
布尔可满足性问题只询问是否存在满足赋值,而 QBF 允许存在选择与全称选择不受限制地交替出现。这使它具备了编码一般多项式空间计算所需的结构。
广义地理游戏
在广义地理游戏中,两名玩家轮流沿有限图的有向边移动一个棋子。每次移动都不能再次访问已经访问过的顶点,无法移动的玩家判负。判定先手是否具有必胜策略是 PSPACE完全的。
一局游戏的步数至多等于顶点数。因此,递归的必胜策略搜索可以在考察一棵分支规模呈指数级的博弈树时,只保留多项式长度的历史记录。
对局长度的多项式上界十分重要。合法对局可能长得多的游戏,其复杂度分类可能不同;并非每一种广义棋盘游戏都是 PSPACE完全的。
规划与时序推理
对于动作以显式方式表示的标准命题 STRIPS 式自动规划,判定是否存在计划是 PSPACE完全的。规划实例可能有指数多个可达状态,因为每个状态都为多项式数量的命题指定了真值。
线性时序逻辑提供了另一个重要例子:它的可满足性问题是 PSPACE完全的。LTL 模型检测在组合复杂度意义下也是 PSPACE完全的;在这一度量中,系统描述和公式都计入输入规模。
这些分类取决于具体的形式体系和输入表示方式,不能不加区分地套用于所有规划语言、时序逻辑或模型检测任务。
其他刻画方式
交替多项式时间
交替图灵机具有存在状态和全称状态。存在状态在至少一个后继状态接受时接受;全称状态则在所有后继状态都接受时接受。
交替多项式时间类满足
这一刻画由阿肖克·钱德拉、德克斯特·科曾和拉里·斯托克迈耶的研究确立,解释了 PSPACE、量化公式与对抗性博弈之间的紧密联系。多项式深度的交替可以描述一棵包含指数多种可能计算的树。
确定性机器可以使用多项式空间对这棵树求值。反过来,多项式空间计算也可以通过多项式时间的交替过程来表达。
交互式证明
另一种刻画是
其中,交互式证明系统对应的 IP 类由具有这类证明系统的语言组成:系统包含一个概率多项式时间验证者,以及一个计算能力不受限制的证明者。阿迪·沙米尔在 1992 年发表的研究中确立了这一等式。
验证者与证明者交换消息,验证者在过程中使用私有的随机选择。完备性要求:对于真实断言,存在合适的证明者,使验证者能够以足够高的概率接受;可靠性则限制了任何证明者使验证者接受虚假断言的概率。
这一等式并未给出求解 PSPACE 问题的多项式时间算法。证明者的计算能力不受限制,而且验证是通过交互式随机协议进行的,而不是通过通常的确定性判定过程完成的。
意义与实践局限
PSPACE 刻画了一种反复出现的计算模式:只保留紧凑的当前状态、搜索历史以及有限的辅助信息,就能探索庞大的状态空间。因此,这一复杂度类在形式验证、规划、逻辑推理和有限博弈中都很重要。
然而,多项式空间是一种理论上的资源界,并不保证实际效率。高次多项式的内存需求可能难以承受,而指数时间搜索即使内存占用不大,也仍可能无法实际完成。实际的求解器往往利用受限实例、结构性质、符号表示和启发式方法,而最坏情况下的完全性分类并不能反映这些因素。
实例的编码方式同样至关重要。显式列出的图,与用紧凑电路描述的、规模呈指数级增大的图,是不同的计算输入。类似地,固定逻辑公式而只改变系统,与允许两者都随输入增长,可能对应不同的复杂度度量。PSPACE 分类适用于问题形式和输入规模约定都得到精确定义的情形。