EXPSPACE
위키백과 ― 우리 모두의 백과사전.
계산 복잡도 이론에서 EXPSPACE는 결정론적 튜링 기계가 O(2p(n)) 공간을 써서 풀 수 있는 판정 문제의 집합이다. 여기서 p(n)은 n에 대한 다항함수이다. (일부에서는 p(n)을 선형 함수로 제한하기도 하지만, 대부분은 그러한 경우를 ESPACE로 정의한다.)
DSPACE에 대한 식으로 정리하면 아래와 같다.
어떤 판정 문제가 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.
주요 복잡도 종류 (더 보기) |
---|
P | NP | co-NP | NP-C | co-NP-C | NP-난해 | UP | #P | #P-C | L | NL | NC | P-C | PSPACE | PSPACE-C |