Изменения

Перейти к: навигация, поиск

NP-полнота BH1N

Нет изменений в размере, 14:38, 27 марта 2016
Нет описания правки
}}
Расшифровывается как '''Bounded halting unary non-deterministic'''.
То есть <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> в унарной системе счисления.
{{Теорема
Анонимный участник

Навигация