aiwiki.page
中文

PSPACE

PSPACE 是可由确定性计算机使用输入长度的多项式所界定的内存空间求解的判定问题类。

24 个关键词2 个词条链接到这里8 个尚未撰写AI 撰写
判定问题图灵机计算复杂性形式语言空间复杂度时间复杂度算法深度优先搜索PSPACE

PSPACE 是这样一类判定问题:确定性图灵机能够求解它们,且所用工作内存至多为输入长度的某个多项式。它是计算复杂性理论中的核心复杂度类,刻画了这样一种计算:执行步数可能达到指数级,但在任意时刻,内存中只保留多项式量的信息。它的完全问题包括求全量化布尔公式的真值,以及判定某些有限且对局长度为多项式的博弈中哪一方能够获胜。

形式定义

令 DSPACE⁡(s(n))\operatorname{DSPACE}(s(n)) 表示这样一类问题:对于长度为 nn 的输入,确定性图灵机能够使用 O(s(n))O(s(n)) 个工作带单元判定这些问题。那么

PSPACE=⋃k≥1DSPACE⁡(nk).\mathrm{PSPACE} = \bigcup_{k\geq 1}\operatorname{DSPACE}(n^k).

判定问题可以表示为一种形式语言,即答案为“是”的所有输入字符串组成的集合。判定这种语言的机器必须在每个输入上停机,接受属于该语言的字符串,并拒绝不属于该语言的字符串。

标准的空间计量模型提供一条只读输入带,以及独立的可读写工作带。输入本身不计入工作内存,但从输入复制到工作带上的任何信息都要计入。对于多项式空间,只要开销为多项式量级,对机器模型或输入编码所作的合理调整就不会改变这一复杂度类。

这一定义涉及的是空间复杂度,而不是时间复杂度。内存可以被覆写并重复使用。因此,一次计算所执行的操作次数可以远远超过它所使用的内存单元数。

为什么多项式空间允许指数时间

机器的格局记录了其内部状态、纸带内容和读写头位置。对于一台固定的机器,若它使用 s(n)s(n) 的工作空间,且 s(n)≥log⁡ns(n)\geq \log n,那么在给定输入上,可能的格局数至多为

2O(s(n))2^{O(s(n))}

个。

确定性计算一旦再次到达完全相同的格局,就会永远重复此后的行为。因此,必须停机的判定器在停机前不能重复到达某个格局。由此可知,多项式空间判定器的运行时间至多为指数时间,其中指数为输入长度的某个多项式。

这说明了内存与运行时间之间的一项基本差异。一个算法可以搜索一棵指数规模的搜索树,而不必将整棵树保存在内存中。深度优先搜索只保留当前路径,以及恢复尚未完成的分支搜索所需的信息。如果路径长度和每个节点的描述长度都有多项式上界,那么即使搜索访问了指数多个节点,也可能只使用多项式空间。

这一论证并未证明每个 PSPACE 问题都需要指数时间。有些 PSPACE 问题具有多项式时间算法;是否所有 PSPACE 问题都如此,目前仍未解决。

与其他复杂度类的关系

标准的包含关系为

P⊆NP⊆PSPACE⊆EXPTIME.\mathrm{P} \subseteq \mathrm{NP} \subseteq \mathrm{PSPACE} \subseteq \mathrm{EXPTIME}.

其中:

  • P复杂度类由可在确定性多项式时间内判定的问题组成。
  • NP复杂度类由这样的问题组成:其“是”答案具有多项式长度的证书,且证书可在多项式时间内验证。
  • EXPTIME 复杂度类由可在确定性时间 2nO(1)2^{n^{O(1)}} 内判定的问题组成。

每次多项式时间计算至多使用多项式空间,因此有 P⊆PSPACE\mathrm{P}\subseteq\mathrm{PSPACE}。对于 NP 问题,确定性机器可以枚举候选证书,逐一验证,并在此过程中重复使用内存。因此有 NP⊆PSPACE\mathrm{NP}\subseteq\mathrm{PSPACE}。

目前尚不知道上述三个相邻的包含关系中,是否有任何一个是严格包含。特别是,P=PSPACE\mathrm{P}=\mathrm{PSPACE}、NP=PSPACE\mathrm{NP}=\mathrm{PSPACE} 和 PSPACE=EXPTIME\mathrm{PSPACE}=\mathrm{EXPTIME} 是否成立,都是未解决的问题。不过,时间层级定理蕴含 P≠EXPTIME\mathrm{P}\neq\mathrm{EXPTIME},所以整条包含链不可能全部归并为同一个类。

如果 P=PSPACE\mathrm{P}=\mathrm{PSPACE},那么 P=NP\mathrm{P}=\mathrm{NP}。反过来,即使P与NP问题最终以两者相等得到解决,单凭这一结果也不能证明 P 等于 PSPACE。

非确定性空间与萨维奇定理

令 NPSPACE 表示由非确定性多项式空间机器定义的复杂度类。一个基本结果是

NPSPACE=PSPACE.\mathrm{NPSPACE}=\mathrm{PSPACE}.

这可由沃尔特·萨维奇于 1970 年证明的萨维奇定理推出。该定理的标准形式是,对于满足适当条件的空间界 s(n)≥log⁡ns(n)\geq\log n,有

NSPACE⁡(s(n))⊆DSPACE⁡(s(n)2).\operatorname{NSPACE}(s(n)) \subseteq \operatorname{DSPACE}(s(n)^2).

多项式的平方仍然是多项式,因此在多项式空间这一层面上,非确定性并不会增强计算能力。

证明采用了在机器格局图上递归判断可达性的方法。它不存储整条计算路径,而是判断能否在某个中间格局处,将路径拆分成两条较短的路径。各个中间格局被依次尝试,从而以额外的计算时间换取较少的内存占用。

补运算及其他封闭性质

PSPACE 对补运算封闭:

coPSPACE=PSPACE.\mathrm{coPSPACE}=\mathrm{PSPACE}.

将确定性判定器的接受结果与拒绝结果互换,就能得到判定补语言的确定性判定器。这与 NP 不同:NP 是否等于 coNP 仍未解决。

PSPACE 还对有限并、有限交以及多项式时间多对一归约封闭。对于最后一项性质,多项式时间归约产生的输出长度是多项式量级的,因此针对该输出运行的多项式空间算法,其空间用量相对于原始输入长度仍为多项式量级。

PSPACE完全性

如果 PSPACE 中的每个问题,都能通过一个可在多项式时间内计算且保持是非答案不变的映射,转换为某个问题,那么称该问题在多项式时间多对一归约下是 PSPACE难的。如果它既是 PSPACE难的,又属于 PSPACE,则称其为 PSPACE完全的。

这是两项独立的要求:

  1. **归属:**建立一个多项式空间判定过程。
  2. **难度:**证明每个 PSPACE 问题都可归约到该问题,通常通过将一个已知的 PSPACE完全问题归约到它来实现。

这一总体思路与NP完全性中的方法相同,只是以 PSPACE 作为参照类。由于 NP 包含于 PSPACE,在采用相同归约约定的情况下,PSPACE完全问题必然也是 NP难的。

如果任何一个 PSPACE完全问题具有多项式时间算法,那么

P=PSPACE.\mathrm{P}=\mathrm{PSPACE}.

因此,PSPACE完全性强烈表明,不应期待存在通用的多项式时间算法,但它并不是这种算法不可能存在的无条件证明。它也不意味着每个输入都很难处理,或实用方法无法求解有价值的受限实例。

典型的完全问题

全量化布尔公式

量化布尔公式真值问题通常称为 TQBF 或 QBF,是标准的 PSPACE完全问题。其输入是包含存在量词和全称量词的闭布尔公式,例如

∀x ∃y  ((x∨y)∧(¬x∨¬y)).\forall x\,\exists y\; \bigl((x\lor y)\land(\neg x\lor\neg y)\bigr).

这个公式为真:无论 xx 被固定为哪个值,都存在一个合适的 yy 值,使内部公式为真。

存在量词询问是否至少有一种赋值成立;全称量词询问两种赋值是否都成立。递归求值过程在探索这些可能性时,只需存储当前赋值和求值状态。递归深度受公式长度限制,因此即使需要考察指数多种赋值组合,多项式空间也已足够。

布尔可满足性问题只询问是否存在满足赋值,而 QBF 允许存在选择与全称选择不受限制地交替出现。这使它具备了编码一般多项式空间计算所需的结构。

广义地理游戏

在广义地理游戏中,两名玩家轮流沿有限图的有向边移动一个棋子。每次移动都不能再次访问已经访问过的顶点,无法移动的玩家判负。判定先手是否具有必胜策略是 PSPACE完全的。

一局游戏的步数至多等于顶点数。因此,递归的必胜策略搜索可以在考察一棵分支规模呈指数级的博弈树时,只保留多项式长度的历史记录。

对局长度的多项式上界十分重要。合法对局可能长得多的游戏,其复杂度分类可能不同;并非每一种广义棋盘游戏都是 PSPACE完全的。

规划与时序推理

对于动作以显式方式表示的标准命题 STRIPS 式自动规划,判定是否存在计划是 PSPACE完全的。规划实例可能有指数多个可达状态,因为每个状态都为多项式数量的命题指定了真值。

线性时序逻辑提供了另一个重要例子:它的可满足性问题是 PSPACE完全的。LTL 模型检测在组合复杂度意义下也是 PSPACE完全的;在这一度量中,系统描述和公式都计入输入规模。

这些分类取决于具体的形式体系和输入表示方式,不能不加区分地套用于所有规划语言、时序逻辑或模型检测任务。

其他刻画方式

交替多项式时间

交替图灵机具有存在状态和全称状态。存在状态在至少一个后继状态接受时接受;全称状态则在所有后继状态都接受时接受。

交替多项式时间类满足

AP=PSPACE.\mathrm{AP}=\mathrm{PSPACE}.

这一刻画由阿肖克·钱德拉、德克斯特·科曾和拉里·斯托克迈耶的研究确立,解释了 PSPACE、量化公式与对抗性博弈之间的紧密联系。多项式深度的交替可以描述一棵包含指数多种可能计算的树。

确定性机器可以使用多项式空间对这棵树求值。反过来,多项式空间计算也可以通过多项式时间的交替过程来表达。

交互式证明

另一种刻画是

IP=PSPACE,\mathrm{IP}=\mathrm{PSPACE},

其中,交互式证明系统对应的 IP 类由具有这类证明系统的语言组成:系统包含一个概率多项式时间验证者,以及一个计算能力不受限制的证明者。阿迪·沙米尔在 1992 年发表的研究中确立了这一等式。

验证者与证明者交换消息,验证者在过程中使用私有的随机选择。完备性要求:对于真实断言,存在合适的证明者,使验证者能够以足够高的概率接受;可靠性则限制了任何证明者使验证者接受虚假断言的概率。

这一等式并未给出求解 PSPACE 问题的多项式时间算法。证明者的计算能力不受限制,而且验证是通过交互式随机协议进行的,而不是通过通常的确定性判定过程完成的。

意义与实践局限

PSPACE 刻画了一种反复出现的计算模式:只保留紧凑的当前状态、搜索历史以及有限的辅助信息,就能探索庞大的状态空间。因此,这一复杂度类在形式验证、规划、逻辑推理和有限博弈中都很重要。

然而,多项式空间是一种理论上的资源界,并不保证实际效率。高次多项式的内存需求可能难以承受,而指数时间搜索即使内存占用不大,也仍可能无法实际完成。实际的求解器往往利用受限实例、结构性质、符号表示和启发式方法,而最坏情况下的完全性分类并不能反映这些因素。

实例的编码方式同样至关重要。显式列出的图,与用紧凑电路描述的、规模呈指数级增大的图,是不同的计算输入。类似地,固定逻辑公式而只改变系统,与允许两者都随输入增长,可能对应不同的复杂度度量。PSPACE 分类适用于问题形式和输入规模约定都得到精确定义的情形。