DTIME

From Традиция
Jump to navigation Jump to search

Класс DTIME(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.Список авторов доступен на этом ресурсе в статье под тем же названием.