EXPSPACE

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

계산 복잡도 이론에서 EXPSPACE결정론적 튜링 기계{\color{Blue}O}(2^{p(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. ISBN 0-534-94728-X