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 )) на входе; если на входе указан экземпляр «да», то принимается хотя бы один сертификат, если на входе — экземпляр «нет», ни один сертификат не может заставить машину принять.

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

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

Связь с другими классами сложности

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

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

Аналогичным образом класс NEXP определяется в терминах NTIME:

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

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

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

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

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

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

Ссылки

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