EXPSPACE

위키백과 ― 우리 모두의 백과사전.

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

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

\mbox{EXPSPACE} = \bigcup_{k\in\mathbb{N}} \mbox{DSPACE}(2^{n^k})

어떤 판정 문제가 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
EXPTIME | EXPSPACE | PR | RE | co-RE | RE-C | co-RE-C | R | BQP | BPP | RP | ZPP | PCP | IP | PH

다른 언어