맨위로가기

EXPTIME

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

1. 개요

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

더 읽어볼만한 페이지

  • 복잡도 종류 - P (복잡도)
    P는 결정론적 튜링 기계로 다항 시간 내에 풀 수 있는 판정 문제들의 집합이며, 다항 시간 균일 불 대수 회로 집합으로도 정의되고, NP, co-NP 등 다른 복잡도 종류들과 관계를 가진다.
  • 복잡도 종류 - P-NP 문제
    P-NP 문제는 계산 복잡도 이론에서 P와 NP 복잡도 종류의 관계에 대한 미해결 문제로, 컴퓨터 과학과 수학에 혁명적인 변화를 가져올 것으로 예상되며 암호학, 최적화, 인공지능 등 다양한 분야에 큰 영향을 미칠 수 있다.
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은 비결정적 튜링 기계로 지수 시간 내에 풀 수 있는 문제의 클래스이다.[1] 더 정확하게는, E ≠ NE인 것은 '''NP'''에 속하지만 '''P'''에는 속하지 않는 희소 언어가 존재할 때와 동일하다.[2]

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

4. EXPTIME-완전

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

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

4. 1. EXPTIME-완전 문제의 예시

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

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

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

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

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

참조

[1] 서적 Computational Complexity Addison-Wesley
[2] 간행물 Sparse Sets in NP−P: EXPTIME versus NEXPTIME http://portal.acm.or[...]
[3] harvtxt
[4] citation Theory of Computational Complexity https://books.google[...] John Wiley & Sons
[5] 학술지 Computing a perfect strategy for n×n chess requires time exponential in n
[6] 학술지 N by N checkers is Exptime complete
[7] 서적 Information Processing; Proceedings of IFIP Congress
[8] harvtxt
[9] 서적 Computational Complexity Addison-Wesley 1994
[10] 문서
[11] 웹사이트 CS 21: Lecture 13 notes http://www.cs.caltec[...] 2008-05-04
[12] 학술지 Computing a perfect strategy for n×n chess requires time exponential in n 1981
[13] 학술지 N by N checkers is Exptime complete 1984
[14] 서적 Information Processing; Proceedings of IFIP Congress 1983
[15] 문서
[16] 서적 Computational Complexity https://archive.org/[...] Addison Wesley
[17] 간행물 Sparse Sets in NP-P: EXPTIME versus NEXPTIME http://portal.acm.or[...]
[18] 문서
[19] 웹인용 CS 21: 강의록 13 https://web.archive.[...] 2007-03-26


본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com