NTIME

계산 복잡도 이론에서, 복잡도 종류 NTIME(f(n))는 시간 O(f(n)) 안에 실행되는 비결정론적 튜링 기계에 의해 해결될 수 있는 결정 문제들의 집합이다. 여기서 O는 점근 표기법이고, f는 어떤 함수이며, n은 입력의 크기(문제를 결정해야 하는 대상)이다.

이것은 크기 n의 주어진 입력에 대해 시간 O(f(n)) 안에 실행될 (즉, n이 어떤 값보다 클 때 f(n)의 상수배 내에서 실행될) 비결정론적 기계가 존재하며, 결정 문제의 답이 해당 입력에 대해 "아니오"인 경우 항상 입력을 "거부"하고, 답이 "예"인 경우 기계는 적어도 하나의 계산 경로에 대해 해당 입력을 "수락"한다는 것을 의미한다. 동등하게, O(f(n)) 시간 안에 실행되고 입력에 대한 O(f(n)) 길이의 인증서를 확인할 수 있는 결정론적 튜링 기계 M이 존재한다. 입력이 "예" 사례인 경우 적어도 하나의 인증서가 수락되고, 입력이 "아니오" 사례인 경우 어떤 인증서도 기계를 수락하게 만들 수 없다.

기계에 사용 가능한 공간은 제한되지 않지만 O(f(n))을 초과할 수 없다. 왜냐하면 사용 가능한 시간이 테이프의 접근 가능량을 제한하기 때문이다.

잘 알려진 복잡도 종류인 NP는 NTIME을 사용하여 다음과 같이 정의할 수 있다:

N P = ⋃ k ∈ N N T I M E ( n k ) {\displaystyle {\mathsf {NP}}=\bigcup _{k\in \mathbb {N} }{\mathsf {NTIME}}(n^{k})}

마찬가지로, 종류 NEXP는 NTIME을 사용하여 다음과 같이 정의된다:

N E X P = ⋃ k ∈ N N T I M E ( 2 n k ) {\displaystyle {\mathsf {NEXP}}=\bigcup _{k\in \mathbb {N} }{\mathsf {NTIME}}(2^{n^{k}})}

비결정론적 시간 위계 정리는 비결정론적 기계가 점근적으로 더 많은 시간에 더 많은 문제를 해결할 수 있다고 말한다.

NTIME은 다음 방식으로 DSPACE와도 관련이 있다. 모든 시간 구성 가능 함수 t(n)에 대해 다음이 성립한다:

N T I M E ( t ( n ) ) ⊆ D S P A C E ( t ( n ) ) {\displaystyle {\mathsf {NTIME}}(t(n))\subseteq {\mathsf {DSPACE}}(t(n))} .

NTIME의 일반화는 교대 튜링 기계로 정의되는 ATIME이다. 다음이 성립하는 것으로 밝혀졌다:

N T I M E ( t ( n ) ) ⊆ A T I M E ( t ( n ) ) ⊆ D S P A C E ( t ( n ) ) {\displaystyle {\mathsf {NTIME}}(t(n))\subseteq {\mathsf {ATIME}}(t(n))\subseteq {\mathsf {DSPACE}}(t(n))} .