Пређи на садржај

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 на следећи начин:

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

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

.

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

.