計算 複雜度 理論 에서 EXPSPACE 는 決定論的 튜링 機械 가 ${\displaystyle {\color {Blue}O}(2^{p(n)})}$ 空間을 써서 풀 수 있는 判定 問題 의 集合 이다. 여기서 ${\displaystyle p(n)}$은 ${\displaystyle n}$에 對한 多項函數이다. (一部에서는 ${\displaystyle p(n)}$을 線形 函數 로 制限하기도 하지만, 大部分은 그러한 境遇를 ESPACE 로 定義한다.)

DSPACE 에 對한 式으로 整理하면 아래와 같다.

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

어떤 判定 問題가 EXPSPACE이고, EXPSPACE에 있는 모든 問題가 그 問題로 다항 時間 多對일 換算 될 수 있으면, EXPSPACE-完全 이라고 한다. 다시 말해서, 한 인스턴스를 다른 똑같은 해의 인스턴스로 變換하는 다항 時間 알고리즘 이 存在한다는 뜻이다. EXPSPACE-完全 問題는 EXPSPACE 問題 가운데 가장 어려운 問題들일 것으로 推定되고 있다.

PSPACE , NP , P 는 모두 EXPSPACE의 眞部分集合이다. EXPTIME 亦是 EXPSPACE의 眞部分集合이라는 說이 有力하다.

EXPSPACE-complete 의 例로는 두 正規 表現式 이 다른 言語를 나타내는지 알아내는 問題가 있다. 여기서 表現式은 合集合, 連結 (正規 表現式) , 클레이니 스타 (0回 以上 反復), 제곱 (表現式 2回 反復) 네 演算子로 制限한다.

클레이니 스타 가 없다면 이 問題는 NEXPTIME -完全 問題가 된다. NEXPTIME -完全은 非決定論的 튜링 機械로 定義한다는 點을 빼면 EXPTIME -完全과 비슷하다.

베르만은 1980年 에 덧셈과 比較만 包含하는 失手 日次 論理式 을 檢證하는 問題가 EXPSPACE 라는 것을 보였다. (이 論理式은 곱셈을 包含하지 않는다)

같이 보기 [ 編輯 ]

• 게임 複雜度

參考 文獻 [ 編輯 ]

• (英語) L. Berman, The complexity of logical theories , Theoretical Computer Science Vol. 11 pp. 71?78, 1980.
• 마이클 사이프저 (1997). 〈9.1.1 (指數 空間 複雜度( Exponential space completeness ))〉. 《Introduction to the Theory of Computation》 (英語). PWS Publishing. 313 -317쪽. ISBN   0-534-94728-X .