NTime(NTIME(NTIME)

계산 복잡도 이론에서, 복잡도 클래스 NTIME(f(n))는 시간 O(f(n))에서 실행되는 비결정론적 튜링 기계에 의해 해결될 수 있는 결정 문제의 집합이다.여기서 O는 빅 O 표기법, f는 일부 함수, n은 입력 크기입니다(문제가 특정됩니다).

의미.

즉, 크기 n의 입력에 대해 시간 O(f(n)(즉, 어떤 값보다 큰 n에 대해 f(n)의 상수 배수 내에서 실행되며, 해당 입력에 대해 "아니오"인 경우 항상 입력을 "거부"하는 비결정론적 기계가 존재함을 의미합니다.최소 1개의 계산 경로에 대해.마찬가지로 시간 O(f(n)에 동작하고 입력에 대해 O(f(n))-길이 증명서를 체크할 수 있는 결정론적 튜링 머신 M이 있다. 입력이 "예" 인스턴스일 경우 적어도 1개의 증명서가 받아들여지고 입력이 "아니오" 인스턴스일 경우 증명서는 기계를 받아들일 수 없다.

공간 제약

사용 가능한 시간은 테이프의 도달 가능한 양을 제한하기 때문에 머신에서 사용할 수 있는 공간은 제한되지 않지만 O(f(n)를 초과할 수 없습니다.

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

잘 알려진 복잡도 클래스 NP는 다음과 같이 NTIME으로 정의할 수 있습니다.

${\displaystyle {NP}=\bigcup_{k\in\mathbb {N}}{\mathsf {NTIME}}(n^{k})$

마찬가지로 클래스 NEXP는 NTIME으로 정의됩니다.

${\displaystyle {NEXP}=\bigcup _{k\in\mathbb {N}}{\mathsf {NTIME}}(2^{n^{k}})$

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

NTIME은 DSPACE와도 다음과 같은 관계가 있습니다.구성 가능한 함수 t(n)에 대하여, 우리는

${\displaystyle \mathsf{N}}$ ${\displaystyle \mathsf{T}}$ ${\displaystyle \mathsf{I}}$ M${\displaystyle \mathsf{E}}$ ( ${\displaystyle t}$(${\displaystyle n}$)${\displaystyle d\mathsf{}}$ ${\displaystyle \mathsf{D}}$ ${\displaystyle \mathsf{S}}$ ${\displaystyle \mathsf{P}}$ A${\displaystyle \mathsf{C}}$ E (${\displaystyle t}$(${\displaystyle n}$ )$$\ $display$style \ $mathsf${ $NTIME$} ($t$ ($n$ ) \ $subseteq$\ $mathsf${ $DSPACE$} ( $t ( n$ )$$。

NTIME의 일반화는 ATIME이며, 교대 튜링 기계로 정의됩니다.알고 보니

$display$$$$=parammathsf {DSPACE}}(t($n$)\}),$

레퍼런스

복잡성 동물원: NTIME(f(n)).