EXPTIME
위키백과 ― 우리 모두의 백과사전.
계산 복잡도 이론에서 복잡도 종류 EXPTIME(EXP라고도 한다)은 결정론적 튜링 기계가 O(2p(n))시간에 풀 수 있는 모든 판정 문제의 집합이다. 여기서 p(n)은 n에 대한 다항함수이다.
DTIME에 대한 식으로 정리하면 이렇다:
다음과 같은 사실이 알려져 있다.
또한, 시간 위계 정리와 공간 위계 정리에 따르면 아래와 같다.
- P
EXPTIME and PSPACE
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 |