EXPSPACE 在計算複雜度理論內EXPSPACE是一個包含可以在Opn空間內解決的決定性問題的集合這裡的pn是某個n的多項式有些作者認為pn應該限制為線性函數但是多數的人把這這樣的複雜度類稱作ESPACE如果我們使用非決定性圖靈機我們會得到複雜度類NEXPSPACE根據薩維奇定理這個複雜度類等同EXPSPACE 以DSPACE和NSPACE表示 EXPSPACE   k  N DSPACE   n k    k  N NSPACE   n k  displaystyle mboxEXPSPACEbigcup kin mathbb N mboxDSPACEnkbigcup kin mathbb N mboxNSPACEnk 我們說一個問題是EXPSPACE完全如果這問題本身在EXPSPACE內而且存在多項式多對一歸約令所有在EXPSPACE內的題目都可以歸約成這個題目換句話說存在一個多項式時間的演算法可以將一個狀況換成其他題目的另一個狀況並且答案一樣EXPSPACE完全的題目也可以想做是EXPSPACE裡面最難的題目 EXPSPACE是PSPACENP和P的嚴格母集前者包含且不等於後者並且也被相信是EXPTIME的嚴格母集 一個EXPSPACE完全的例子是分辨兩個正規表式是否是一樣的語言這個問題這裡的表示限制使用四種操作子聯集串街克萊尼星號可以是零個或多個重複的表示式和平方兩份表示式 如果我們排除星號則這個問題變成NEXPTIME完全這個複雜度類有點類似EXPTIME完全不過使用的機器是非決定性圖靈機而非一般的圖靈機 L Berman在年證明了證明或反證任何有關實數並且牽涉加法和比較大小但不牽涉乘法的一階陳述這個問題在EXPSPACE內