EXPSPACE 문서 원본 보기

{{위키데이터 속성 추적}}
[[계산 복잡도 이론]]에서 '''EXPSPACE'''는 [[결정론적 튜링 기계]]가 [[대문자 O 표기법|<math>{\color{Blue}O}(2^{p(n)})</math>]]
공간을 써서 풀 수 있는 [[판정 문제]]의 [[집합]]이다. 여기서 <math>p(n)</math>은 <math>n</math>에 대한 다항함수이다. (일부에서는 <math>p(n)</math>을 [[선형 함수]]로 제한하기도 하지만, 대부분은 그러한 경우를 '''[[ESPACE]]'''로 정의한다.)

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

:<math>\mathsf{EXPSPACE} = \bigcup_{k\in\mathbb{N}} \mathsf{DSPACE}(2^{n^k})</math>

어떤 판정 문제가 EXPSPACE이고, EXPSPACE에 있는 모든 문제가 그 문제로 [[다항 시간 다대일 환산]]될 수 있으면, '''EXPSPACE-완전'''이라고 한다. 다시 말해서, 한 인스턴스를 다른 똑같은 해의 인스턴스로 변환하는 다항 시간 [[알고리즘]]이 존재한다는 뜻이다. EXPSPACE-완전 문제는 EXPSPACE 문제 가운데 가장 어려운 문제들일 것으로 추정되고 있다.

'''[[PSPACE]]''', '''[[NP (complexity)|NP]]''', '''[[P (complexity)|P]]'''는 모두 EXPSPACE의 진부분집합이다. '''[[EXPTIME]]''' 역시 EXPSPACE의 진부분집합이라는 설이 유력하다.

'''EXPSPACE-complete'''의 예로는 두 [[정규 표현식]]이 다른 언어를 나타내는지 알아내는 문제가 있다. 여기서 표현식은 합집합, [[연결 (정규 표현식)]], [[클레이니 스타]] (0회 이상 반복), 제곱 (표현식 2회 반복) 네 연산자로 제한한다.

[[클레이니 스타]]가 없다면 이 문제는 '''[[NEXPTIME]]-완전''' 문제가 된다. [[NEXPTIME]]-완전은 비결정론적 튜링 기계로 정의한다는 점을 빼면 [[EXPTIME]]-완전과 비슷하다.

베르만은 [[1980년]]에 덧셈과 비교만 포함하는 실수 [[일차 논리|일차 논리식]]을 검증하는 문제가 '''EXPSPACE'''라는 것을 보였다. (이 논리식은 곱셈을 포함하지 않는다)

== 같이 보기 ==
* [[게임 복잡도]]

== 참고 문헌 ==

* {{언어링크|en}} L. Berman, ''The complexity of logical theories'', Theoretical Computer Science Vol. 11 pp.&nbsp;71–78, 1980.
* {{서적 인용|저자 = [[마이클 사이프저]] | 연도 = 1997 | 제목= Introduction to the Theory of Computation |url = https://archive.org/details/introductiontoth00sips | 출판사 = PWS Publishing | 언어= 영어 |ISBN=0-534-94728-X | 장= 9.1.1 (지수 공간 복잡도({{lang|en|Exponential space completeness}})) | 페이지 = [https://archive.org/details/introductiontoth00sips/page/313 313]-317 }}

{{복잡도 종류}}

[[분류:복잡도 종류]]