NTIME

В теории сложности вычислений , то класс сложности NTime ( е ( п )) есть множество проблем , принятие решений , которые могут быть решены с помощью недетерминистических машин Тьюринга , которая проходит по времени O ( F ( п )). Здесь O - большая нотация O , f - некоторая функция, а n - размер входных данных (для которых проблема должна быть решена).

Значение [ править ]

Это означает, что существует недетерминированная машина, которая для данного ввода размера n будет работать за время O ( f ( n )) (то есть в пределах постоянного кратного f ( n ), если n больше некоторого значения) , и всегда будет «отклонять» ввод, если ответ на проблему решения - «нет» для этого ввода, в то время как если ответ «да», машина «примет» этот ввод по крайней мере для одного пути вычисления. Эквивалентно,существует детерминированная машина Тьюринга M, которая работает за время O ( f ( n )) и может проверять O ( f (n )) - сертификат длины для входа; если ввод - экземпляр «да», то принимается по крайней мере один сертификат, если ввод - экземпляр «нет», ни один сертификат не может заставить машину принять.

Ограничения по пространству [ править ]

Пространство, доступное для машины, не ограничено, хотя оно не может превышать O ( f ( n )), поскольку доступное время ограничивает доступность ленты.

Отношение к другим классам сложности [ править ]

Хорошо известный класс сложности NP можно определить в терминах NTIME следующим образом:

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

Точно так же класс NEXP определяется в терминах NTIME:

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

Недетерминирована теорема времени иерархии говорит , что недетерминированные машины могут решить больше проблем в асимптотический больше времени.

NTIME также связано с DSPACE следующим образом. Для любой функции, построенной по времени t ( n ), мы имеем

${\ Displaystyle {\ mathsf {NTIME}} (т (п)) \ substeq {\ mathsf {DSPACE}} (т (п))}$.

Обобщением NTIME является ATIME , определяемый чередующимися машинами Тьюринга . Оказывается, что

${\ Displaystyle {\ mathsf {NTIME}} (т (п)) \ substeq {\ mathsf {ATIME}} (t (п)) \ substeq {\ mathsf {DSPACE}} (т (п))}$.

Ссылки [ править ]

Зоопарк сложности : NTIME ( f ( n )) .