1632
правки
Изменения
м
Расшифровывается как '''Bounded halting unary non-deterministic'''.
rollbackEdits.php mass rollback
{{Определение
|definition=<tex> \mathrm{BH_{1N}} </tex> (от ''bounded halting unary non-deterministic'') <tex>= \lbrace \langle m, x, 1^t \rangle \mid m </tex> {{---}} [[Недетерминированные вычисления|недетерминированная машина Тьюринга]], <tex> m(x) = 1, T(m,x) \leqslant t \rbrace </tex>.
}}
То есть <tex> \mathrm{BH_{1N}} </tex> {{---}} язык троек <tex> \langle m, x, 1^t \rangle </tex> таких, что недетерминированная машина Тьюринга <tex> m </tex> на входной строке <tex> x </tex> возращает <tex>1</tex> за время <tex> T(m, x) \leqslant t </tex> и <tex> 1^{t} </tex> {{---}} запись <tex> t </tex> в унарной системе счисления.
[[Категория: Теория сложности]]
[[Категория: Контекстно-свободные грамматикиДетерминированные и недетерминированные вычисления, сложность по времени и по памяти ]]
[[Категория: Классы P и NP, NP-полнота]]
