NTIME - 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 _ {к \ 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 )) .