NTIME

У рачунарској теорији сложености, класа сложености NTIME(f(n)) је скуп проблема одлучивости који могу да буду решени помоћу недетерминистичке Тјурингове машине у времену O(f(n)). Овде је O велико O нотација, f нека функција и n дужина улаза (за који проблем треба да буде одлучен).

Значење

Ово значи да постоји недетерминистичка машина која за задати улаз дужине n има време извршења у оквиру O(f(n)) (тј. у оквиру константног мултипла од f(n), за n веће од неке задате вредности) и која ће увек ће одбијати улазе, ако је одговор да проблем одлучивања „не“, а ако је „да“, машина ће прихватити улаз, барем по једној путањи извршења. Исто тако, постоји детерминистичка Тјурингова машина M која ради у времену O(f(n)) и у стању да провери сертификат полиномијалне дужине за задати улаз. Ако је улаз случај „да“ тада ће барем један сертификат бити прихваћен, а ако је „не“ ниједан сертификат неће моћи да произведе прихват улаза.

Просторна ограничења

Простор који је на располагању машини није ограничен, али не може да пређе преко O(f(n)) зато што време ограничава колико траке је доступно.

Релације према другим класама сложености

Добро позната класа сложености NP може да се дефинише у терминима NTIME на следећи начин:

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

Слично се класа NEXP дефинише на основу NTIME:

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

Недетерминистичка теорема хијерархије времена, каже да недетерминистичке машине могу да реше проблем у оквиру асимптотски више времена. NTIME је у релацији са DSPACE на следећи начин: за сваку временски изградиву функцију t(n) имамо да је:

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

Генерализација NTIME је ATIME, дефинисана код алтернирајуће Тјурингове машине. Тако се добија да је:

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