EXPSPACE

계산 복잡도 이론에서 EXPSPACE는 결정론적 튜링 기계가 ${\color {Blue}O}(2^{p(n)})$ 공간을 써서 풀 수 있는 판정 문제의 집합이다. 여기서 $p(n)$은 $n$에 대한 다항함수이다. (일부에서는 $p(n)$을 선형 함수로 제한하기도 하지만, 대부분은 그러한 경우를 ESPACE로 정의한다.)

DSPACE에 대한 식으로 정리하면 아래와 같다.

${\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.