EXPSPACE
換言すれば、多項式時間アルゴリズムによって、ある問題から別の問題へ解を変えずに変換可能である。EXPSPACE完全問題は、EXPSPACEの中でも最も難しい問題とされる。
EXPSPACE は PSPACE、NP、P を真に包含する。また、EXPTIME をも真に包含すると考えられている。
EXPSPACE完全な問題の例として、2つの正規表現が異なる言語を表現しているかどうかの決定問題がある。このとき、その表現は4つの演算子(和集合、連結、クリーネ閉包(ゼロ個以上のコピー)、平方(2つのコピー))に制限される。
クリーネ閉包を除くと、この問題は NEXPTIME完全となる。これは EXPTIME完全に似ているが、決定性ではなく非決定性チューリング機械で定義される。
また1980年、L. Berman は実数の加法と比較(乗法は含まない)についての一階述語論理式の評価問題が EXPSPACE であることを示した。