Изменения

Пусть <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} \in NPC</tex>. Что и требовалось доказать.