교대 튜링 기계

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

1. 개요
2. 정의
3. 복잡도 클래스
4. 제한된 교대
5. 예제
참조

1. 개요

교대 튜링 기계는 비결정적 튜링 기계의 일종으로, 존재적 상태와 보편적 상태를 번갈아 사용하며 계산을 수행한다. 존재적 상태에서는 일부 전이가 수용 상태로 이어지면 수용되고, 보편적 상태에서는 모든 전이가 수용 상태로 이어져야 수용된다. 이러한 특징을 통해 계산 복잡도를 분석하며, NP, co-NP와 같은 복잡도 클래스를 정의하는 데 활용된다. 교대 튜링 기계는 시간과 공간 복잡도를 정의하며, AP = PSPACE, APSPACE = EXPTIME 등의 관계를 갖는다. 또한 교대 횟수를 제한하여 다항식 계층과 같은 복잡도 클래스를 정의할 수 있으며, TQBF 문제와 같은 문제를 해결하는 데 사용될 수 있다.

더 읽어볼만한 페이지

계산 모형 - 양자 컴퓨터
양자 컴퓨터는 양자역학적 현상을 이용하여 정보를 처리하는 컴퓨터로, 큐비트를 통해 0과 1을 동시에 표현하여 특정 연산에서 기존 컴퓨터보다 빠른 속도를 보이며 암호 해독, 신약 개발 등 다양한 분야에 혁신을 가져올 것으로 기대된다.
계산 모형 - 양자 회로
양자 회로는 양자 컴퓨팅에서 양자 논리 게이트들을 연결한 회로로, 큐비트의 양자역학적 특성을 활용하여 계산을 수행하며 양자 계산의 핵심 요소로서 연구가 활발히 진행되고 있다.

교대 튜링 기계
기본 정보
교대 튜링 기계의 작동 방식
종류	계산 모델
구조
상태	존재적 상태 (∃) 보편적 상태 (∀) 수락 상태 거부 상태
전이 함수	Q × Γ → P(Q × Γ × {L,R})
속성
결정성	비결정적
대역폭	k log n
시간 복잡도	ATIME(f(n)) = DSPACE(f(n))
공간 복잡도	ASPACE(f(n)) = DTIME(f(n))
완전성	ASPACE(log n) = P
기타	병렬 계산의 모델 게임의 모델

2. 정의

교대 튜링 기계(ATM)는 비결정적 튜링 기계를 확장한 것으로, 계산 과정에서 '존재'(∃) 상태와 '보편'(∀) 상태를 교대로 사용한다. 일반적인 튜링 기계는 '현재 상태에서 가능한 모든 전이 중 하나를 선택'하는 방식으로 동작하는 반면, 교대 튜링 기계는 상태에 따라 다른 규칙을 적용한다.

존재 상태(∃): 현재 상태에서 가능한 전이 중 하나라도 수락(accept) 상태로 이어진다면, 해당 상태는 수락으로 간주된다. 이는 마치 여러 갈래의 길 중 하나라도 목적지에 도달하면 성공으로 보는 것과 유사하다.
보편 상태(∀): 현재 상태에서 가능한 모든 전이가 수락 상태로 이어져야만 해당 상태가 수락으로 간주된다. 모든 길이 목적지에 도달해야 성공으로 인정되는 것이다.

이러한 존재/보편 상태의 개념은 NP와 co-NP 문제의 정의와도 관련이 있다. NP 문제는 '존재적' 특성을 가지는데, 해가 존재한다면 (즉, 수락 상태로 가는 경로가 하나라도 있다면) 문제를 해결할 수 있다. 반면, co-NP 문제는 '보편적' 특성을 가지며, 모든 가능한 경우가 조건을 만족해야 (즉, 모든 경로가 수락 상태로 이어져야) 문제가 해결된다.

교대 튜링 기계는 이 두 가지 상태를 번갈아 사용하면서 계산을 수행하며, 초기 상태가 수락 상태이면 입력 문자열을 수락하고, 거부 상태이면 거부한다.

2. 1. 비공식적 설명

교대 튜링 기계는 비결정적 튜링 기계의 한 종류로, 상태가 존재적 상태와 보편적 상태 두 가지로 나뉜다. 존재적 상태에서는 여러 전이 중 하나라도 수락(accept) 상태로 이어지면 수락된다. 반면, 보편적 상태에서는 모든 전이가 수락 상태로 이어져야만 수락된다.^[1]

전이가 없는 보편적 상태는 무조건 수락되고, 전이가 없는 존재적 상태는 무조건 거부된다. 교대 튜링 기계는 초기 상태가 수락이면 입력 문자열을 수락하고, 거부면 거부한다.^[1]

이러한 상태 교대는 NP와 co-NP의 정의와 관련이 있다. NP는 어떤 선택이든 수용 상태로 이어지면 수용되는 '존재적 모드'를 사용하는 반면, co-NP는 모든 선택이 수용 상태로 이어져야 수용되는 '보편적 모드'를 사용한다. 교대 튜링 기계는 이 두 모드를 모두 사용하여 계산을 수행한다.^[1]

2. 2. 형식적 정의

교대 튜링 기계(ATM)는 5-튜플

M=(Q,\Gamma,\delta,q_0,g)

로 형식적으로 정의된다. 각 요소는 다음과 같다.

$Q$ : 상태의 유한 집합
$\Gamma$ : 테이프 알파벳의 유한 집합
$\delta:Q\times\Gamma\rightarrow\mathcal{P}(Q\times\Gamma\times\{L,R\})$ : 전이 함수 (''L''은 테이프를 왼쪽으로, ''R''은 헤드를 오른쪽으로 이동)
$q_0\in Q$ : 초기 상태
$g:Q\rightarrow\{\wedge,\vee,accept,reject\}$ : 각 상태의 유형을 나타내는 함수

M

의 상태

q\in Q

에 대해,

g(q)=accept

이면 해당 구성은 '수락',

g(q)=reject

이면 '거부' 상태이다.

g(q)=\wedge

인 구성은 한 번에 접근 가능한 모든 구성이 수락 상태일 때만 수락, 하나라도 거부이면 거부 상태가 된다.

g(q)=\vee

인 구성은 한 번에 접근 가능한 구성 중 하나라도 수락이면 수락, 모두 거부일 때만 거부 상태가 된다.

M

은 초기 구성이 수락 상태일 때 입력 ''w''를 수락하고, 거부 상태일 때 입력을 거부한다.

2. 3. 계산 자원

교대 튜링 기계(ATM)는 길이

n

의 입력이 특정 형식 언어에 속하는지 여부를 시간

t(n)

안에 결정한다. 즉, 초기 구성이 수락 상태인지 거부 상태인지를 최대

t(n)

단계까지의 구성을 조사하여 판단한다. ATM이 사용하는 공간은

s(n)

으로 충분하다.

ATM에서 어떤 상수

c>0

에 대해 시간

c\cdot t(n)

내에 결정되는 언어는 클래스

\mathsf{ATIME}(t(n))

에 속한다. 공간

c\cdot s(n)

내에 결정되는 언어는 클래스

\mathsf{ASPACE}(s(n))

에 속한다.^[1]

ATM의 구성을 수락 또는 거부 상태로 결정할 때, 현재 구성에서 도달 가능한 모든 구성을 반드시 조사할 필요는 없다. 특히, 존재적 구성은 후속 구성 중 하나라도 수락 상태이면 수락으로 표시할 수 있으며, 보편적 구성은 후속 구성 중 하나라도 거부 상태이면 거부로 표시할 수 있다.^[1]

3. 복잡도 클래스

교대 튜링 기계(ATM)를 사용하여 정의하는 복잡도 클래스는 다음과 같다.

$\mathsf{AP}=\bigcup_{k>0}\mathsf{ATIME}(n^k)$ : 다항 시간 내에 결정 가능한 언어이다.
$\mathsf{APSPACE}=\bigcup_{k>0}\mathsf{ASPACE}(n^k)$ : 다항 공간 내에 결정 가능한 언어이다.
$\mathsf{AEXPTIME}=\bigcup_{k>0}\mathsf{ATIME}(2^{n^k})$ : 지수 시간 내에 결정 가능한 언어이다.

이들은 결정적 튜링 기계가 아닌 ATM이 사용하는 계산 자원을 고려한다는 점을 제외하면 P, PSPACE, EXPTIME의 정의와 유사하다.

찬드라(Chandra), 코젠(Kozen), 스톡마이어(Stockmeyer)는 다음 정리를 증명했다.^[3]

ALOGSPACE = P
AP = PSPACE
APSPACE = EXPTIME
AEXPTIME = EXPSPACE
$\mathsf{ASPACE}(f(n))=\bigcup_{c>0}\mathsf{DTIME}(2^{cf(n)})=\mathsf{DTIME}(2^{O(f(n))})$
$\mathsf{ATIME}(g(n))\subseteq \mathsf{DSPACE}(g(n))$
$\mathsf{NSPACE}(g(n))\subseteq\bigcup_{c>0}\mathsf{ATIME}(c\times g(n)^2),$

여기서

f(n)\ge\log(n)

및

g(n)\ge\log(n)

이다.

이러한 관계의 더 일반적인 형태는 병렬 계산 가설로 표현된다.

4. 제한된 교대

''k''회 교대하는 교대 튜링 기계는 존재적 상태에서 전칭적 상태로, 또는 그 반대로 전환이 ''k''회 이상 발생하지 않는 기계이다. 이 기계의 상태는 ''k''개의 집합으로 나뉜다. 짝수 번호 집합의 상태는 전칭적이고, 홀수 번호 집합의 상태는 존재적이다(또는 그 반대). 집합 ''i''의 상태와 ''j'' < ''i''인 집합 ''j''의 상태 사이에는 전이가 없다.^[1]

예를 들어 회로 최소화 문제를 생각해 보자. 어떤 부울 함수 ''f''를 계산하는 회로 ''A''와 숫자 ''n''이 주어졌을 때, 최대 ''n''개의 논리 게이트로 동일한 함수 ''f''를 계산하는 회로가 존재하는지 확인하는 문제이다. 1회 교대하는 교대 튜링 기계는 존재적 상태에서 시작하여 이 문제를 다항 시간 안에 풀 수 있다. 최대 ''n''개의 게이트를 가진 회로 ''B''를 추측하고, 전칭 상태로 교대하여 입력을 추측하고, ''B''의 출력과 ''A''의 출력을 비교한다.

''k''회 교대하는 교대 튜링 기계가 존재적 상태에서 시작하면 $\Sigma_k\rm{P}$ 에 속하는 문제를 다항 시간 안에 풀 수 있다(전칭적 상태에서 시작하면 $\Pi_k\rm{P}$ ). 자세한 내용은 다항식 계층을 참조하라.

4. 1. 정의

''k''번 교대하는 교대 튜링 기계는 존재 상태에서 보편 상태로, 또는 그 반대로 최대 ''k''-1번 전환하는 기계이다. 이는 상태가 ''k''개의 집합으로 나뉘는 교대 튜링 기계이다. 짝수 번호 집합의 상태는 보편적이고 홀수 번호 집합의 상태는 존재적이다(또는 그 반대). 기계는 집합 ''i''의 상태와 ''i''보다 작은 집합 ''j''의 상태 사이에는 전환이 없다.^[1]

''k''회 교대가 있는 교대 튜링 기계란, 존재적 상태에서 전칭적 상태로의 전환, 혹은 그 반대의 전환이 ''k''회 이상 발생하지 않는 교대 튜링 기계이다. 이 경우, 상태는 ''k''개의 집합으로 분할된다. 상태가 짝수 개의 집합으로 분할되면 전체적으로 전칭적이며, 홀수 개이면 존재적이 된다(혹은 그 반대. 초기 상태가 어느 쪽인지에 따라 달라진다). 집합 ''i''에 포함된 상태와, ''j'' < ''i''인 집합 ''j''에 포함된 상태 사이에는 전이가 존재하지 않는다.^[1]

4. 2. 예시

회로 최소화 문제를 생각해 보자. 부울 함수 ''f''를 계산하는 회로 ''A''와 숫자 ''n''이 주어졌을 때, 최대 ''n''개의 게이트를 가진 회로가 존재하는지 결정해야 한다. 존재 상태에서 시작하여 한 번의 교대를 하는 교대 튜링 기계는 이 문제를 다항 시간 내에 해결할 수 있다. 즉, 최대 ''n''개의 게이트를 가진 회로 ''B''를 추측한 다음, 범용 상태로 전환하여 입력을 추측하고 해당 입력에 대한 ''B''의 출력이 해당 입력에 대한 ''A''의 출력과 일치하는지 확인한다.

4. 3. 클래스 붕괴

이머만-셀레프체니 정리의 결과로, 로그 공간 계층 구조는 첫 번째 레벨로 붕괴된다.^[4] 결과적으로,

f=\Omega(\log)

가 공간 구성 가능할 때

\mathsf{SPACE}(f)

계층 구조는 첫 번째 레벨로 붕괴된다.

4. 4. 특수 경우

교대 튜링 기계가 존재적 상태(또는 보편적 상태)에서 시작하여 다항 시간 내에 ''k''번 교대하는 경우, 클래스

\Sigma_k^p

(또는

\Pi_k^p

)에 속하는 모든 문제를 결정할 수 있다.^[5] 이러한 클래스는 때때로

\Sigma_k\rm{P}

및

\Pi_k\rm{P}

로 표기된다. 자세한 내용은 다항식 계층 문서를 참조하면 된다.

시간 계층의 또 다른 특수한 경우는 로그 계층이다.

''k''회 교대가 있는 교대 튜링 기계란, 존재적 상태에서 전칭적 상태로의 전환, 혹은 그 반대의 전환이 ''k''회 이상 발생하지 않는 교대 튜링 기계를 말한다. 이 경우, 상태는 ''k''개의 집합으로 분할된다. 상태가 짝수 개의 집합으로 분할되면 전체적으로 전칭적이며, 홀수 개이면 존재적이 된다(혹은 그 반대. 초기 상태가 어느 쪽인지에 따라 달라진다). 집합 ''i''에 포함된 상태와, ''j'' < ''i''인 집합 ''j''에 포함된 상태 사이에는 전이가 존재하지 않는다.

예시로 회로 최소화 문제를 들어 보자. 어떤 부울 함수 ''f''를 계산하는 회로 ''A''와 수 ''n''이 있을 때, 최대 ''n''개의 논리 게이트로 동일한 함수 ''f''를 계산하는 회로가 존재하는지 여부를 결정하는 문제이다. 1회의 교대가 있는 교대 튜링 기계로 존재적 상태에서 동작을 시작하는 경우, 이 문제를 다항 시간 내에 풀 수 있다. 최대 ''n''개의 게이트를 가진 회로 ''B''를 가정하고, 전칭 상태로 교대하여 입력을 가정하고, ''B''에 해당 입력을 넣었을 때의 출력과 ''A''에 동일한 입력을 넣었을 때의 출력을 비교한다.

''k''회 교대가 있는 교대 튜링 기계가 존재적 상태에서 동작을 시작하는 경우, 클래스

\Sigma_k\rm{P}

에 속하는 문제를 다항 시간 내에 풀 수 있다(또는, 전칭적 상태에서 동작을 시작하는 경우에는

\Pi_k\rm{P}

). 자세한 내용은 다항식 계층을 참조하면 된다.

5. 예제

한정 기호가 붙은 부울식 문제는 충족 가능성 문제를 확장하여 각 변수가 존재 한정 기호 또는 전칭 한정 기호로 제한되도록 한 문제이다. 교대 튜링 기계는 존재 한정된 변수에 대해서는 존재적으로 분기하여 가능한 모든 값을 시도하고, 전칭 한정된 변수에 대해서는 전칭적으로 분기하여 가능한 모든 값을 시도한다. 이를 한정되는 순서대로 왼쪽에서 오른쪽으로 보아간다. 모든 한정 변수의 값을 결정한 후, 논리식에 해당 값들을 적용하여 그 진리값에 따라 수락 또는 거절을 결정한다.^[1]

이러한 기계는 한정 기호가 붙은 부울식을 시간 $n^2$ 과 영역 $n$ 으로 결정한다.^[1]

충족 가능성 문제는 모든 변수가 존재 한정된 특수한 경우로 볼 수 있으며, 존재적 방식만으로 효율적으로 풀 수 있다.^[1]

참조

_[1] 학회인용 Alternation
_[2] 학회인용 On parallelism in Turing machines
_[3] 학술지 Alternation http://users.cis.fiu[...]
_[4] 학술지 Nondeterministic space is closed under complementation http://www.cs.umass.[...]
_[5] 서적 Theory of Computation https://archive.org/[...] Springer-Verlag

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

문의하기 : help@durumis.com