Изменения

==Определение языка BH<texsub>BH_{1N}</texsub>== Языком '''BH<texsub>BH_{1N}</texsub>''' (от англ. bounded halting unary) называется множество троек <tex>\langle m, x, 1^{t} \rangle</tex>, где <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>.: '''BH<texsub>BH_{1N} </sub>''' = <tex>\{ \langle m, x, 1^{t} \rangle | m </tex> &mdash; НМТ, <tex> m(x)=1, T(m, x)\le t \}</tex>.Так же Также можно рассматривать языки '''BH<texsub>BH_{1D}</texsub>''', '''BH<texsub>BH_{2N}</texsub>''', '''BH<texsub>BH_{2D}</texsub>''', отличающиеся от '''BH<texsub>BH_{1N}</texsub> ''' только детерминированностью машин Тьюринга (<tex>D</tex> - детерминированная, <tex>N</tex> - недетерминированная) или системой счисления, в которой представляется время (1 - унарная, 2 - бинарная).

Язык '''BH<texsub>BH_{1N}</texsub> ''' является <tex>'''NP</tex>'''-полным: '''BH<texsub>BH_{1N}\in NPC</texsub>''' ∈ '''NPC'''. 

Для того, чтобы доказать [[Понятие_NP-трудной_и_NP-полной_задачи|'''NP'''-полноту]] '''BH<texsub>BH_{1}1N</texsub> ''' необходимо установить следующие факты:# '''BH<texsub> BH_{1N} \in NP </texsub>.''' ∈ '''NP''';# '''BH<texsub> BH_{1N} \in NPH </texsub>;''' ∈ '''NPH'''.

===Доказательство принадлежности BH<texsub>BH_{1N}</texsub> классу NP===Будем использовать в качестве сертификата <tex>y</tex> последовательность недетерминированных выборов, которые должна сделать машина <tex>m</tex>, чтобы допустить слово <tex>x</tex>. Длина сертификата меньше, чем <tex>ctCt</tex> для некоторого <tex>C</tex>.

Все условия принадлежности классу '''NP''' выполнены. ===Доказательство принадлежности BH_1N классу NPH===Теперь докажем, что '''BH_1N''' принадлежит классу '''NPH'''.Рассмотрим произвольный язык <tex>L</tex>из класса '''NP'''. Для него существует машина Тьюринга <tex>m</tex>, такая что <tex>T(m, x)\le p(|x|), L(m) = L</tex>.Докажем, что <tex>L</tex> выполненысводится по Карпу к '''BH_1N'''. Рассмотрим функцию <tex>f(x) = \langle m, x, 1^{p(|x|)}\rangle</tex> по входным данным возвращающую тройку из машины Тьюринга, попадающую под описанные выше условия, входных данных и времени <tex>p(|x|)</tex> в унарной системе счисления. Эта функция существует, она своя для каждого языка. Проверим, что <tex>x \in L \Leftrightarrow f(x)</tex> ∈ '''BH_1N'''.

===Доказательство принадлежности Пусть <tex>BH_{1N}x \in L</tex> классу NPH===Теперь докажем, что . Тогда <tex>BH_{1N}m(x) = 1</tex> принадлежит классу . Время работы <tex>NPHm</tex>.Рассмотрим произвольный язык не больше <tex>Lp(|x|)</tex> из класса , а значит слово <tex>NPx</tex>. Для него существует машина Тьюринга будет допущено машиной <tex>m</tex>за время не больше, такая что чем <tex>Tp(|x|)</tex>. А тогда тройка <tex>\langle m, x)\le , 1^{p(|x|), L}\rangle = f(mx) = L</tex>будет входить в '''BH_1N''' согласно его определению.Докажем, что Пусть <tex>x \not\in L</tex> сводится по Карпу к . Тогда <tex> BH_{1N}m(x) = 0</tex>. Рассмотрим функцию Но тогда тройка <tex>f(x) = \langle m, x, 1^{p|x|)t}\rangle</tex> по входным данным возвращающую тройку из машины Тьюринга, попадающую под описанные выше условия, входных данных и времени не принадлежит '''BH_1N''' при любом <tex>p(|x|)t</tex> в унарной системе счисления. Эта функция существует, она своя для каждого языка. Проверим, что а значит и при <tex>x \in L \Leftrightarrow ft = p(|x|) \in BH_{1N}</tex>.

Пусть Значит произвольный язык из класса '''NP''' сводится по Карпу к '''BH<texsub>x \in L</tex>. Тогда <tex>m(x) = 1</tex>. Время работы <tex>m</tex> не больше <tex>p(|x|)1N</texsub>''', а значит слово <tex>x</tex> будет допущено машиной <tex>m</tex> за время не больше, чем <tex>p(|x|)</tex>. А тогда тройка <tex>\langle m,x, 1^{p(|x|)}\rangle = f(x)то есть '''BH</texsub> будет входить в <tex>BH_{1N}</tex> согласно его определению.Пусть <tex>x \not\in L</tex>. Тогда <tex>m(x) = 0</texsub>''' ∈ '''NPC'''. Но тогда тройка <tex>\langle m, x, 1^{t}\rangle</tex> не принадлежит <tex>BH_{1N}</tex> при любом <tex>t</tex>, а значит Что и при <tex>t = p(|x|)</tex>требовалось доказать.

Значит произвольный язык из класса <tex>[[Категория:NP</tex> сводится по Карпу к <tex>BH_{1N}</tex>, и <tex>BH_{1N} \in NPC</tex>. Что и требовалось доказать.]]