EXPTIME

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요

EXPTIME은 결정론적 튜링 기계로 지수 시간 내에 풀 수 있는 모든 문제의 집합을 의미한다. P, NP, PSPACE, NEXPTIME, EXPSPACE 등 다른 복잡도 클래스와의 관계가 있으며, 시간 계층 정리와 공간 계층 정리에 의해 P ⊊ EXPTIME, NP ⊊ NEXPTIME, PSPACE ⊊ EXPSPACE임이 알려져 있다. EXPTIME-완전 문제는 EXPTIME에 속하는 문제 중 가장 어려운 문제로, 다항 시간 내에 해결될 수 없으며, 튜링 기계의 수용 문제, 일반화된 체스, 체커, 바둑(일본식 코 규칙) 등과 간결한 회로 관련 문제가 이에 해당한다.

EXPTIME

📚 더 읽어볼만한 페이지

복잡도 종류 - P (복잡도)
P는 결정론적 튜링 기계로 다항 시간 내에 풀 수 있는 판정 문제들의 집합이며, 다항 시간 균일 불 대수 회로 집합으로도 정의되고, NP, co-NP 등 다른 복잡도 종류들과 관계를 가진다.
복잡도 종류 - P-NP 문제
P-NP 문제는 계산 복잡도 이론에서 P와 NP 복잡도 종류의 관계에 대한 미해결 문제로, 컴퓨터 과학과 수학에 혁명적인 변화를 가져올 것으로 예상되며 암호학, 최적화, 인공지능 등 다양한 분야에 큰 영향을 미칠 수 있다.

1. 개요
2. 정의
3. 다른 복잡도 클래스와의 관계
4. EXPTIME-완전
- 4.1. EXPTIME-완전 문제의 예시

2. 정의

DTIME을 이용하여 다음과 같이 정의한다.

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

3. 다른 복잡도 클래스와의 관계

다음 포함 관계가 알려져 있다.

: P ⊆ NP ⊆ PSPACE ⊆ EXPTIME ⊆ NEXPTIME ⊆ EXPSPACE

또한, 시간 계층 정리와 공간 계층 정리에 의해 다음과 같다.

: P ⊊ EXPTIME, NP ⊊ NEXPTIME 및 PSPACE ⊊ EXPSPACE

위 식에서, 기호 ⊆는 "의 부분집합"을 의미하고, 기호 ⊊는 "의 진부분집합"을 의미한다.

따라서 처음 세 개의 포함 관계 중 적어도 하나와 마지막 세 개의 포함 관계 중 적어도 하나는 참이어야 하지만, 어떤 것이 참인지는 알려져 있지 않다. 또한, 만약 P = NP라면, EXPTIME = NEXPTIME이다. 여기서 NEXPTIME은 비결정적 튜링 기계로 지수 시간 내에 풀 수 있는 문제의 클래스이다. 더 정확하게는, E ≠ NE인 것은 NP에 속하지만 P에는 속하지 않는 희소 언어가 존재할 때와 동일하다.

EXPTIME은 교대 튜링 기계가 다항식 공간에서 해결할 수 있는 모든 문제의 집합인 APSPACE로 재구성될 수 있다. 이는 교대 튜링 기계가 결정적 튜링 기계만큼 강력하기 때문에 PSPACE ⊆ EXPTIME임을 알 수 있는 한 가지 방법이다.

4. EXPTIME-완전

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

반대로, 보드 크기에서 다항식의 수만큼 움직여서 끝나는 일반화된 게임은 종종 PSPACE-완전하다. 이는 반복이 자동적으로 이루어지지 않는 지수적으로 긴 게임에도 적용된다.

4.1. EXPTIME-완전 문제의 예시

어떤 판정 문제가 EXPTIME에 속하고, EXPTIME의 모든 문제가 그 문제로 다항 시간 다대일 환산될 때 그 문제를 EXPTIME-완전이라고 한다. EXPTIME-완전에 속하는 문제는 EXPTIME에서 가장 어려운 문제로 볼 수 있다. EXPTIME-완전 문제가 P에 속하지 않는다는 것은 시간 계층 정리에 의해 증명되어 있다.

계산가능성 이론에서 기본적인 EXPTIME-완전 문제 중 하나는 결정론적 튜링 기계가 어떤 입력을 최대 $k$ 단계에 받아들이는지 아닌지를 묻는 문제이다. 이 문제는 $O(k)$ 시간 시뮬레이션 방법이 있고, 입력 $k$ 가 $O(\log k)$ 비트를 써서 인코딩되기 때문에 EXPTIME이다. 이 문제가 EXPTIME-완전인 이유는 이 문제를 써서 어떤 기계가 EXPTIME 문제를 지수 단계 안에 받아들일지를 판정할 수 있기 때문이다.

이밖에도 여러 일반화된 보드 게임 문제가 EXPTIME-완전 문제이다.

* 체스
* 체커
* 바둑 (일본식 코 규칙 사용)

바둑의 경우, 일본식 코 규칙은 EXPTIME-완전성을 암시하는 것으로 알려져 있지만, 미국 또는 중국 규칙은 EXPTIME-완전한지는 알려져 있지 않다.

EXPTIME-완전 문제의 또 다른 중요한 예는 간결한 회로(Succinct Circuit) 문제이다. 간결한 회로는 지수적으로 적은 공간에서 일부 그래프를 설명하는 데 사용되는 간단한 기계이다. 많은 P-완전 그래프 문제의 경우, 간결한 회로 표현에서 동일한 문제를 해결하는 것은 EXPTIME-완전하다.