DTIME

Материал из свободной русской энциклопедии «Традиция»
Перейти к: навигация, поиск

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