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

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

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


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