EXPSPACE
1. 개요
EXPSPACE는 DSPACE와 NSPACE의 관점에서 정의되는 복잡도 종류이다. 이는 로 표현된다. EXPSPACE-완전 문제의 예시로는 두 정규 표현식이 서로 다른 언어를 나타내는지 확인하는 문제, 선형 시간 논리의 유효성 문제, 페트리 네트의 커버 가능성 문제가 있다. EXPSPACE는 PSPACE, NP, P의 진정한 상위 집합이며, EXPTIME의 진정한 상위 집합일 것으로 추정되지만 아직 증명되지 않았다.
| EXPSPACE | 계산 복잡도 이론에서, 결정 문제의 집합으로, 튜링 기계로 풀 수 있고 공간 복잡도가 O(2^(p(n)))인 문제들을 의미한다. 여기서 p(n)은 n에 대한 다항식 함수이다. |
|---|---|
| 다른 이름 | AEXPSPACE NPSPACE |
| 설명 | EXPSPACE는 ESPACE를 포함한다. EXPSPACE에 대해, 결정적 튜링 기계는 공간 O(2^(p(n)))을 사용하여 문제를 해결할 수 있다. |
|---|---|
| NEXPSPACE | 비결정적 튜링 기계가 공간 O(2^(p(n)))을 사용하여 풀 수 있는 결정 문제의 집합이다. Savitch의 정리에 의해 NEXPSPACE = EXPSPACE이다. |
| 설명 | EXPSPACE-완전 문제는 EXPSPACE에서 가장 어려운 문제로 간주된다. EXPSPACE의 모든 문제는 다항 시간 축소를 통해 EXPSPACE-완전 문제로 변환할 수 있다. |
|---|---|
| 예시 | 정규 표현식과 와일드카드를 사용한 두 개의 정규 표현식이 동일한 언어를 설명하는지 여부를 결정하는 문제. 짝수 이동으로 일반화된 체스, 체커, 바둑과 같은 게임을 이기는 전략이 있는지 여부를 결정하는 문제. |
| 관계 | PSPACE ⊆ EXPTIME ⊆ EXPSPACE NP ⊆ EXPTIME ⊆ EXPSPACE P ⊆ NP ⊆ PSPACE ⊆ EXPTIME ⊆ EXPSPACE ⊆ EXPTIME EXPSPACE-완전 문제는 P, NP, PSPACE, EXPTIME에 있지 않다고 추정된다. 그러나 증명되지는 않았다. |
|---|
2.1. DSPACE와 NSPACE
EXPSPACE는 결정론적 튜링 기계(DSPACE)와 비결정론적 튜링 기계(NSPACE)를 사용하여 다음과 같이 표현할 수 있다.
:
3. EXPSPACE-완전 문제의 예시
정규 표현식이 서로 다른 언어를 나타내는지 확인하는 문제, 선형 시간 논리를 시간(정수)으로 확장한 논리의 유효성 문제, 페트리 네트의 커버 가능성 문제 등은 EXPSPACE-완전 문제의 예시이다.
3.1. 정규 표현식 문제
두 개의 정규 표현식이 서로 다른 언어를 나타내는지 확인하는 문제는 EXPSPACE-완전 문제의 예시이다. 여기서 표현식은 합집합, 결합, 클레이니 스타(표현식의 0개 이상 복사), 제곱(표현식의 두 복사본)의 네 가지 연산자로 제한된다.
3.2. 선형 시간 논리 문제
알루어(Alur)와 헨징거(Henzinger)는 선형 시간 논리를 시간 (정수)으로 확장했고, 이들 논리의 유효성 문제가 EXPSPACE-완전임을 증명했다.
3.3. 페트리 네트 문제
페트리 네트의 커버 가능성 문제는 EXPSPACE-완전이다. 도달 가능성 문제는 오랫동안 EXPSPACE-난해 문제로 알려져 있었지만, 비기본 문제로 밝혀져 EXPSPACE에 속하지 않을 가능성이 높다. 2022년에는 아커만 함수-완전 문제임이 밝혀졌다.
4. 다른 복잡도 종류와의 관계
EXPSPACE는 PSPACE, NP, P의 진상위집합으로 알려져 있다. 또한 EXPTIME의 진상위집합일 것으로 추정되지만, 이는 아직 알려져 있지 않다.