EXPSPACE

在计算复杂度理论内，EXPSPACE是一个包含可以在O(2^p(n))空间内解决的决定性问题的集合，这里的p(n)是某个n的多项式。（有些作者认为p(n）应该限制为线性函数，但是多数的人把这这样的复杂度类称作ESPACE。)如果我们使用非决定性图灵机，我们会得到复杂度类NEXPSPACE。根据萨维奇定理，这个复杂度类等同EXPSPACE。

以DSPACE和NSPACE表示：

{\mbox{EXPSPACE}}=\bigcup _{k\in \mathbb {N} }{\mbox{DSPACE}}(2^{n^{k}})=\bigcup _{k\in \mathbb {N} }{\mbox{NSPACE}}(2^{n^{k}})

我们说一个问题是EXPSPACE-完全，如果这问题本身在EXPSPACE内，而且存在多项式多对一归约，令所有在EXPSPACE内的题目都可以归约成这个题目。换句话说，存在一个多项式时间的算法可以将一个状况换成其他题目的另一个状况，并且答案一样。EXPSPACE-完全的题目也可以想做是EXPSPACE里面最难的题目。

EXPSPACE是PSPACE，NP，和P的严格母集（前者包含且不等于后者）。并且也被相信是EXPTIME的严格母集。

一个EXPSPACE-完全的例子是分辨两个正规表式是否是一样的语言这个问题。这里的表示限制使用四种操作子：联集，串街，克莱尼星号（可以是零个或多个重复的表示式），和平方（两份表示式）。^[1]

如果我们排除星号，则这个问题变成NEXPTIME-完全，这个复杂度类有点类似EXPTIME-完全，不过使用的机器是非决定性图灵机而非一般的图灵机。

L. Berman在1980年证明了，证明或反证任何有关实数并且牵涉加法和比较大小（但不牵涉乘法）的一阶陈述，这个问题在EXPSPACE内。

参考资料

^ Meyer, A.R. and L. Stockmeyer. The equivalence problem for regular expressions with squaring requires exponential space （页面存档备份，存于互联网档案馆）. 13th IEEE Symposium on Switching and Automata Theory, Oct 1972, pp.125–129.

L. Berman The complexity of logical theories, Theoretical Computer Science 11:71-78, 1980.
Michael Sipser. Introduction to the Theory of Computation. PWS Publishing. 1997. ISBN 0-534-94728-X. Section 9.1.1: Exponential space completeness, pp.313–317. Demonstrates that determining equivalence of regular expressions with exponentiation is EXPSPACE-complete.

[1] Meyer, A.R. and L. Stockmeyer. The equivalence problem for regular expressions with squaring requires exponential space （页面存档备份，存于互联网档案馆）. 13th IEEE Symposium on Switching and Automata Theory, Oct 1972, pp.125–129.

[1]

相关页面

参考资料