PSPACE 复杂度类

阐述

PSPACE 是可以用确定性 Turing 机在多项式空间内判定的问题的集合。

$$\operatorname{PSPACE}=\bigcup_{k} \operatorname{SPACE}\left(n^{k}\right)$$

由于 Savitch 定理，相应的非确定性版本 NPSPACE 与它相等。

其中最难的一组问题称为 PSPACE 完全复杂度类。

实例

性质

相关内容

• P 复杂度类 和 NP 复杂度类 都包含于 PSPACE
• PSPACE 包含于指数复杂度类，即

$$\text{PSPACE}\subseteq \text { EXPTIME }=\bigcup_{k} \operatorname{TIME}\left(2^{n^{k}}\right)$$

总结：

$$\mathrm{P} \subseteq \mathrm{NP} \subseteq \mathrm{PSPACE}=\mathrm{NPSPACE} \subseteq \mathrm{EXPTIME}$$

参考文献