NTIME

U računarskoj teoriji složenosti, klasa složenosti NTIME(f(n)) je skup problema odlučivosti koji mogu da budu rešeni pomoću nedeterminističke Tjuringove mašine u vremenu O(f(n)). Ovde je O veliko O notacija, f neka funkcija i n dužina ulaza (za koji problem treba da bude odlučen).

Značenje

Ovo znači da postoji nedeterministička mašina koja za zadati ulaz dužine n ima vreme izvršenja u okviru O(f(n)) (tj. u okviru konstantnog multipla od f(n), za n veće od neke zadate vrednosti) i koja će uvek će odbijati ulaze, ako je odgovor da problem odlučivanja „ne“, a ako je „da“, mašina će prihvatiti ulaz, barem po jednoj putanji izvršenja. Isto tako, postoji deterministička Tjuringova mašina M koja radi u vremenu O(f(n)) i u stanju da proveri sertifikat polinomijalne dužine za zadati ulaz. Ako je ulaz slučaj „da“ tada će barem jedan sertifikat biti prihvaćen, a ako je „ne“ nijedan sertifikat neće moći da proizvede prihvat ulaza.

Prostorna ograničenja

Prostor koji je na raspolaganju mašini nije ograničen, ali ne može da pređe preko O(f(n)) zato što vreme ograničava koliko trake je dostupno.

Relacije prema drugim klasama složenosti

Dobro poznata klasa složenosti NP može da se definiše u terminima NTIME na sledeći način:

${\mbox{NP}}=\bigcup _{k\in \mathbb {N} }{\mbox{NTIME}}(n^{k})$

Slično se klasa NEXP definiše na osnovu NTIME:

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

Nedeterministička teorema hijerarhije vremena, kaže da nedeterminističke mašine mogu da reše problem u okviru asimptotski više vremena. NTIME je u relaciji sa DSPACE na sledeći način: za svaku vremenski izgradivu funkciju t(n) imamo da je:

${\mbox{NTIME}}(t(n))\subseteq {\mbox{DSPACE}}(t(n))$.

Generalizacija NTIME je ATIME, definisana kod alternirajuće Tjuringove mašine. Tako se dobija da je:

${\mbox{NTIME}}(t(n))\subseteq {\mbox{ATIME}}(t(n))\subseteq {\mbox{DSPACE}}(t(n))$.