EXPTIME

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

계산 복잡도 이론에서 복잡도 종류 EXPTIME(EXP라고도 한다)은 결정론적 튜링 기계O(2p(n))시간에 풀 수 있는 모든 판정 문제의 집합이다. 여기서 p(n)은 n에 대한 다항함수이다.

DTIME에 대한 식으로 정리하면 이렇다:

\mbox{EXPTIME} = \bigcup_{k \in \mathbb{N} } \mbox{ DTIME } \left( 2^{ n^k } \right) .

다음과 같은 사실이 알려져 있다.

P \subseteq NP \subseteq PSPACE \subseteqEXPTIME \subseteq NEXPTIME \subseteq EXPSPACE

또한, 시간 위계 정리와 공간 위계 정리에 따르면 아래와 같다.

P \subsetneq EXPTIME   and   PSPACE \subsetneq EXPSPACE

따라서 앞쪽 세 포함관계 중 적어도 하나는 진부분집합이어야 한다. 뒤쪽 세 포함관계도 마찬가지이다. 그러나 어느 것이 진부분집합 관계인지는 알려져 있지 않다. 전문가들은 모든 포함관계가 진부분집합 관계일 것으로 보고 있다. 만약 P = NP라면 EXPTIME = NEXPTIME이 성립한다는 사실도 알려져 있다. NEXPTIME은 비결정론적 튜링 기계가 지수 시간에 풀 수 있는 문제의 집합이다.


목차

[편집] EXPTIME-완전

[편집] 더 보기

  • 게임 복잡도
  • 다항 위계

[편집] 바깥 고리

[편집] 참고문헌

  • 크리스토스 파파드미트리오 (1994). “20.1: 지수 시간”, Computational Complexity, 1판, Addison Wesley, 491-499. ISBN 0-201-53082-1.


주요 복잡도 종류 (더 보기)

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