EXPSPACE
計算複雑性理論において、複雑性クラス EXPSPACE とは、決定性チューリング機械で O(2) の領域を使って解ける全決定問題の集合である。ここで、p(n) は n の多項式関数である。p(n) を一次関数に限定する場合もあるが、通常そのようなクラスは ESPACE と呼ばれる。
DSPACEの記法では以下のように表される。
EXPSPACE = ⋃ k ∈ N DSPACE ( 2 n k ) {\displaystyle {\mbox{EXPSPACE}}=\bigcup _{k\in \mathbb {N} }{\mbox{DSPACE}}(2^{n^{k}})}
EXPSPACE完全な決定問題とは、EXPSPACE に属し、かつ全ての EXPSPACE に属する問題を多項式時間多対一還元によってその問題に帰着させることができる場合を指す。