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

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

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


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