EXPTIME 문서 원본 보기

{{위키데이터 속성 추적}}
[[계산 복잡도 이론]]에서 [[복잡도 종류]] '''EXPTIME'''('''EXP'''라고도 한다)은 [[결정론적 튜링 기계]]가 [[대문자 O 표기법|<math>{\color{Blue}O}(2^{p(n)})</math>]]시간에 풀 수 있는 모든 [[판정 문제]]의 [[집합]]이다. 여기서 <math>p(n)</math>은 <math>n</math>에 대한 다항함수이다.

[[DTIME]]에 대한 식으로 정리하면 이렇다:
:<math> \mbox{EXPTIME} = \bigcup_{k \in \mathbb{N} } \mbox{ DTIME } \left( 2^{ n^k } \right) . </math>

다음과 같은 사실이 알려져 있다.
:[[P (복잡도)|P]] &sube; [[NP (복잡도)|NP]] &sube; [[PSPACE]] &sube; EXPTIME &sube; [[NEXPTIME]] &sube; [[EXPSPACE]]

또한, [[시간 위계 정리]]와 [[공간 위계 정리]]에 따르면 아래와 같다.
:P <math>\subsetneq</math> EXPTIME &nbsp;이고&nbsp; NP <math>\subsetneq</math> NEXPTIME &nbsp;이고 &nbsp; PSPACE <math>\subsetneq</math> EXPSPACE이다

따라서 앞쪽 세 포함관계 중 적어도 하나는 진부분집합이어야 한다. 뒤쪽 세 포함관계도 마찬가지이다. 그러나 어느 것이 진부분집합 관계인지는 알려져 있지 않다. 전문가들은 모든 포함관계가 진부분집합 관계일 것으로 보고 있다. 만약 P&nbsp;=&nbsp;NP라면 EXPTIME&nbsp;=&nbsp;[[NEXPTIME]]이 성립한다는 사실도 알려져 있다. NEXPTIME은 [[비결정론적 튜링 기계]]가 지수 시간에 풀 수 있는 문제의 집합이다.<ref>{{서적 인용|저자 = [[크리스토스 파파디미트리우]] | 연도 = 1994 | 제목 = Computational Complexity |url = https://archive.org/details/computationalcom0000papa | 출판사 = Addison Wesley |ISBN=0-201-53082-1| 장 = 20.1: 지수 시간 | 페이지 = [https://archive.org/details/computationalcom0000papa/page/491 491]|언어=영어}}</ref> 더 정확히 말하면, EXPTIME &ne; NEXPTIME이고 오직 그럴 때만 NP 중에 P가 아닌 [[희소 언어]]가 존재한다.<ref>Juris Hartmanis, Neil Immerman, Vivian Sewelson. Sparse Sets in NP-P: EXPTIME versus NEXPTIME. ''Information and Control'', volume 65, issue 2/3, pp.158&ndash;181. 1985. [http://portal.acm.org/citation.cfm?id=808769 At ACM Digital Library]</ref>

EXPTIME은 [[교대 튜링 기계]]가 다항 공간을 써서 풀 수 있는 문제들의 집합인 [[APSPACE]]로 다시 쓸 수 있다. 이것은 PSPACE &sube; EXPTIME임을 보이는 방법이기도 하다. 교대 튜링 기계는 최소한 결정 튜링 기계보다는 강력하기 때문이다.<ref>파파디미트리우 (1994), 20장 1절, 따름정리 3, 495쪽.</ref>

== EXPTIME-완전==

어떤 [[판정 문제]]가 EXPTIME에 속하고, EXPTIME의 모든 문제가 그 문제로 [[다항 시간 다대일 환산]]될 때 그 문제를 EXPTIME-완전이라 한다. 다시 말해서, 다른 어떤 EXPTIME 문제의 인스턴스도 답을 똑같이 유지하면서 그 판정 문제의 인스턴스로 다항 시간에 환산할 수 있는 [[알고리즘]]이 존재한다는 뜻이다. EXPTIME-완전에 속하는 문제는 EXPTIME에서 가장 어려운 문제로 볼 수 있다. NP가 P에 속하는지 아닌지는 아직 모르지만, EXPTIME-완전 문제가 P에 속하지 않는다는 것은 증명되어 있다.

[[계산가능성 이론]]에서 기본적인 결정 불가능 문제 중 하나는 [[결정론적 튜링 기계]]가 특정한 입력 하나를 받아들일지 말지를 판정하는 것이다. 기본적인 EXPTIME-완전 문제 중 하나는 결정론적 튜링 기계가 어떤 입력을 최대 <math>k</math> 단계에 받아들이는지 아닌지를 묻는 문제이다. 이 문제가 EXPTIME인 이유는 단순한 <math>O(k)</math>시간 시뮬레이션 방법이 있고, 입력 <math>k</math>가 <math>O(\log k)</math>비트를 써서 인코딩되기 때문이다.<ref>{{웹 인용 | 저자 = Chris Umans | url = http://www.cs.caltech.edu/~umans/cs21/lec13.pdf | 제목 = CS 21: 강의록 13 | 확인날짜 = 2007-03-26 | 보존url = https://web.archive.org/web/20070221200158/http://www.cs.caltech.edu/~umans/cs21/lec13.pdf | 보존날짜 = 2007-02-21 | url-status = dead }} 슬라이드 24.</ref> 이 문제가 EXPTIME-완전인 이유는 이 문제를 써서 어떤 기계가 EXPTIME 문제를 지수 단계 안에 받아들일지를 판정할 수 있기 때문이다.

이밖에도 [[체스]], [[체커]] 등 여러 보드 게임 문제가 EXPTIME-완전 문제이다.

== 외부 링크 ==
* [https://web.archive.org/web/20061128071923/http://qwiki.caltech.edu/wiki/Complexity_Zoo#exp 복잡도 동물원]

== 참고 문헌 ==
<references />

{{복잡도 종류}}

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