Изменения
→Определение языка BH_{1N}
==Определение языка BH_{1N}==
Языком <tex>BH_{1N}</tex>(от англ. bounded halting unary) называется множество троек, где <tex>m</tex> - недетерминированная машина Тьюринга, <tex>x</tex> - входные данные и <tex>t</tex> - времея в унарной системе счисления, таких, что <tex>m(x)=1</tex> и время работы машины <tex>m</tex> на входе <tex>x</tex> <tex>T(m, x)\le t</tex>.
<tex>BH_{1N} = </tex>{<tex>\langle m, x, 1^{t} \rangle | m </tex> - недетерменированная недетерминированная машина Тьюринга, <tex>m(x)=1, T(m, x)\le t</tex>}.Так же существуют языки <tex>BH_{1D}</tex>, <tex>BH_{2N}</tex>, <tex>BH_{2D}</tex>, отличающиеся от <tex>BH_{1N}</tex> только детерменированностью детерминированностью машин Тьюринга (<tex>D</tex> - детерменированнаядетерминированная, <tex>N</tex> - недетерменированнаянедетерминированная) или системой счисления, в которой представляется время (1 - унарная, 2 - бинарная).
==Теорема==
Язык <tex>BH_{1N}</tex> принадлежит классу <tex>NP</tex>-полных задач: <tex>BH_{1N}\in NPC</tex>.
