EXPSPACEとは？ わかりやすく解説

計算複雑性理論において、複雑性クラス EXPSPACE とは、決定性チューリング機械で O(2^p(n)) の領域を使って解ける全決定問題の集合である。ここで、p(n) は n の多項式関数である。p(n) を一次関数に限定する場合もあるが、通常そのようなクラスは ESPACE と呼ばれる。

DSPACEの記法では以下のように表される。

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

EXPSPACE完全な決定問題とは、EXPSPACE に属し、かつ全ての EXPSPACE に属する問題を多項式時間多対一還元によってその問題に帰着させることができる場合を指す。換言すれば、多項式時間アルゴリズムによって、ある問題から別の問題へ解を変えずに変換可能である。EXPSPACE完全問題は、EXPSPACEの中でも最も難しい問題とされる。

EXPSPACE は PSPACE、NP、P を真に包含する。また、EXPTIME をも真に包含すると考えられている。

EXPSPACE完全な問題の例として、2つの正規表現が異なる言語を表現しているかどうかの決定問題がある。このとき、その表現は4つの演算子（和集合、連結、クリーネ閉包（ゼロ個以上のコピー）、平方（2つのコピー））に制限される。

クリーネ閉包を除くと、この問題は NEXPTIME完全となる。これは EXPTIME完全に似ているが、決定性ではなく非決定性チューリング機械で定義される。

また1980年、L. Berman は実数の加法と比較（乗法は含まない）についての一階述語論理式の評価問題が EXPSPACE であることを示した。

参考文献

• L. Berman The complexity of logical theories, Theoretical Computer Science 11:71-78, 1980.
• Michael Sipser (1997年). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X.  Section 9.1.1: Exponential space completeness, pp.313–317. 冪乗の正規表現の等価性判定が EXPSPACE完全な問題であることを例示している。