EXPSPACE는 계산 복잡도 이론에서 다루는 중요한 공간 복잡도 클래스 중 하나이다. 이 클래스는 결정론적 튜링 기계가 입력 크기 $n$에 대해 지수적으로 많은 공간, 즉 $O(2^{p(n)})$ (여기서 $p(n)$은 $n$에 대한 임의의 다항식)을 사용하여 풀 수 있는 모든 결정 문제의 집합을 포함한다.
좀 더 형식적으로, EXPSPACE는 $L(2^{O(n^k)})$와 같이 정의될 수 있다. 여기서 $L(f(n))$은 $O(f(n))$ 공간을 사용하는 문제를 나타낸다. 이는 기계가 사용할 수 있는 메모리 양이 입력 길이의 다항식 승으로 증가하는 형태를 의미한다.
주요 특징 및 다른 클래스와의 관계:
- 비결정론적 동등성: EXPSPACE는 비결정론적 튜링 기계를 사용하더라도 동일한 클래스를 정의한다는 것이 알려져 있다. 즉, NEXPSPACE = EXPSPACE이다. 이는 사비치(Savitch) 정리에 의해 비결정론적 공간 복잡도를 결정론적 공간 복잡도로 변환할 때 다항식 오버헤드만 발생하기 때문에, 지수적 공간에서는 이 다항식 오버헤드가 큰 영향을 미치지 않기 때문이다.
- 포함 관계: EXPSPACE는 다른 주요 복잡도 클래스들을 포함한다.
- PSPACE $\subseteq$ EXPSPACE: 다항 공간에서 해결 가능한 모든 문제는 당연히 지수 공간에서도 해결 가능하다.
- EXPTIME $\subseteq$ EXPSPACE: 지수 시간(exponential time) 내에 해결되는 모든 문제는 지수 공간 내에서도 해결될 수 있다. 왜냐하면, $T$ 시간 내에 $T$개 이상의 공간을 사용할 수 없기 때문이다.
- EXPTIME $\subseteq$ NEXPTIME $\subseteq$ EXPSPACE: 비결정론적 시간 클래스들도 EXPSPACE에 포함된다.
- 계층 정리: 공간 계층 정리(Space Hierarchy Theorem)에 따르면, EXPSPACE는 PSPACE보다 엄격하게 큰 클래스이다. 즉, PSPACE $\subsetneq$ EXPSPACE가 성립한다.
EXPSPACE에 속하는 문제의 예시:
이 클래스에 속하는 대표적인 문제로는 다음이 있다.
- 일반화된 체스(Generalized Chess)의 결정 문제: $n \times n$ 보드에서 진행되는 체스와 같은 보드 게임에서 주어진 위치에서 어떤 플레이어가 승리할 수 있는지 결정하는 문제. 이러한 문제들은 입력 크기에 따라 가능한 상태 공간이 기하급수적으로 증가하여 지수적인 공간을 필요로 한다.
- 프레스버거 산술(Presburger arithmetic)의 결정 문제: 덧셈과 등식만을 포함하는 자연수에 대한 1차 논리 문장이 참인지 거짓인지 결정하는 문제. 이 문제 또한 EXPSPACE 완전(EXPSPACE-complete)으로 알려져 있다.
EXPSPACE는 컴퓨터가 해결할 수 있는 문제의 한계를 이해하는 데 중요한 기준점이 되며, 현대 컴퓨터의 한계를 넘어서는 문제들을 분류하고 이론적으로 분석하는 데 기여한다.