Класс NTIME — различия между версиями
(Новая страница: «Классом NTIME(f) по аналогии с DTIME называется класс языков(задач), для которых суще…») |
|||
| Строка 2: | Строка 2: | ||
<tex>NTIME(f(n)) = \{ L | \exists НМТ m : L(m)=L, T(m,x) \le f(|x|) \}</tex>. | <tex>NTIME(f(n)) = \{ L | \exists НМТ m : L(m)=L, T(m,x) \le f(|x|) \}</tex>. | ||
| + | |||
| + | [[Категория:Классы сложности]] | ||
Версия 13:06, 14 ноября 2018
Классом NTIME(f) по аналогии с DTIME называется класс языков(задач), для которых существует недетерминированная машина Тьюринга, такая, что она всегда останавливается, и время ее работы не превосходит , где - длина входа.
.
