Класс NTIME — различия между версиями
(Новая страница: «Классом NTIME(f) по аналогии с DTIME называется класс языков(задач), для которых суще…») |
м (rollbackEdits.php mass rollback) |
||
| (не показаны 2 промежуточные версии 2 участников) | |||
| Строка 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>. | ||
| + | |||
| + | [[Категория:Классы сложности]] | ||
Текущая версия на 11:44, 1 сентября 2022
Классом NTIME(f) по аналогии с DTIME называется класс языков(задач), для которых существует недетерминированная машина Тьюринга, такая, что она всегда останавливается, и время ее работы не превосходит , где - длина входа.
.
