Изворни код странице 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 на следећи начин:

:<math>\mbox{NP} = \bigcup_{k\in\mathbb{N}} \mbox{NTIME}(n^k)</math>

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

:<math>\mbox{NEXP} = \bigcup_{k\in\mathbb{N}} \mbox{NTIME}(2^{n^k})</math>

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

:<math>\mbox{NTIME}(t(n)) \subseteq \mbox{DSPACE}(t(n))</math>.

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

:<math>\mbox{NTIME}(t(n)) \subseteq \mbox{ATIME}(t(n)) \subseteq \mbox{DSPACE}(t(n))</math>.

{{нормативна контрола}}

[[Категорија:Класе комплексности]]