EXPSPACE

在計算複雜度理論內，EXPSPACE是一個包含可以在O(2^p(n))空間內解決的決定性問題的集合，這裏的p(n)是某個n的多項式。（有些作者認為p(n）應該限制為線性函數，但是多數的人把這這樣的複雜度類稱作ESPACE。)如果我們使用非決定性圖靈機，我們會得到複雜度類NEXPSPACE。根據薩維奇定理，這個複雜度類等同EXPSPACE。

以DSPACE和NSPACE表示：

${\displaystyle {\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內。

相關頁面

• 遊戲複雜度

參考資料

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.

• 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.