Изменения
→Доказательство
Теперь докажем, что <tex>BH_{1N}</tex> принадлежит классу <tex>NPH</tex>.
Рассмотрим произвольный язык <tex>L</tex> из класса <tex>NP</tex>. Для него существует машина Тьюринга <tex>m</tex>, такая что <tex>T(m, x)\le p(|x|), L(m) = L</tex>.
Докажем, что <tex>L</tex> сводится по Карпу к <tex>ВH_BH_{1N}</tex>. Рассмотрим функцию <tex>f(x) = \langle m, x, 1^{p|x|)}\rangle</tex> по входным данным возвращающую тройку из машины Тьюринга, попадающую под описанные выше условия, входных данных и времени <tex>p(|x|)</tex> в унарной системе счисления. Эта функция существует, она своя для каждого языка. Проверим, что <tex>x \in L \Leftrightarrow f(x) \in BH_{1N}</tex>.
Пусть <tex>x \in L</tex>. Тогда <tex>m(x) = 1</tex>. Время работы <tex>m</tex> не больше <tex>p(|x|)</tex>, а значит слово <tex>x</tex> будет допущено машиной <tex>m</tex> за время не больше, чем <tex>p(|x|)</tex>. А тогда тройка <tex>\langle m,x, 1^{p(|x|)}\rangle = f(x)</tex> будет входить в <tex>BH_{1N}</tex> согласно его определению.
Пусть <tex>x \not\in L</tex>. Тогда <tex>m(x) = 0</tex>. Но тогда тройка <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}</tex> принадлежит <tex>\in NPC</tex>, что . Что и требовалось доказать.
