NTIME

Класс NTIME(t(n)) означает класс задач, разрешимых на недетерминированной машине Тьюринга за время t(n).

Более формально:

Язык $L \subset \Sigma^*$ принадлежит классу ${\cal DTIME}(t(n))$, если существует недетерминированная машина Тьюринга T, разрешающая данный язык, и сложность ее работы в наихудшем случае, $time_{T(n)} \leq t(n)$, то есть не превышает t(n), где n-длина входного слова.

По крайней мере часть этого текста взята с ресурса http://lib.custis.ru/ под лицензией GDFL.Список авторов доступен на этом ресурсе в статье под тем же названием.