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의 진부분집합이라는 설이 유력하다.

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
EXPTIME | EXPSPACE | PR | RE | co-RE | RE-C | co-RE-C | R | BQP | BPP | RP | ZPP | PCP | IP | PH

다른 언어