EXPSPACE
위키백과 ― 우리 모두의 백과사전.
계산 복잡도 이론에서 EXPSPACE는 결정론적 튜링 기계가 O(2p(n)) 공간을 써서 풀 수 있는 판정 문제의 집합이다. 여기서 p(n)은 n에 대한 다항함수이다. (일부에서는 p(n)을 선형 함수로 제한하기도 하지만, 대부분은 그러한 경우를 ESPACE로 정의한다.)
DSPACE에 대한 식으로 정리하면 아래와 같다.
어떤 판정 문제가 EXPSPACE이고, EXPSPACE에 있는 모든 문제가 그 문제로 다항 시간 다대일 환산될 수 있으면, EXPSPACE-완전이라고 한다. 다시 말해서, 한 인스턴스를 다른 똑같은 해의 인스턴스로 변환하는 다항 시간 알고리즘이 존재한다는 뜻이다. EXPSPACE-완전 문제는 EXPSPACE 문제 가운데 가장 어려운 문제들일 것으로 추정되고 있다.
PSPACE, NP, P는 모두 EXPSPACE의 진부분집합이다. EXPTIME 역시 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 (in 영어). 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 |
