Изменения
→Доказательство
Для начала докажем, что <tex>BH_{1N}</tex> принадлежит классу <tex>NP</tex>.
За время <tex>t</tex> машина Тьюринга может сделать не более <tex>t</tex> недетерминированных выборов. Сертификатом будет множество этих выборов. Проверяющая сертификаты программа <tex>R(\langle m, x, 1^{t}\rangle, y)</tex> эмулирует работу недетерминированной машины Тьюринга <tex>m</tex> на слове <tex>x</tex>. Там, где у машины <tex>m</tex> было несколько выборов, она совершает действие согласно сертификату. При этом проверяется корректность всех действий и замеряется время работы <tex>m</tex>. Сертификатом выбираем недетерминированные выборы <tex>m</tex>. Длина сертификата по длине меньше, чем <tex>c*t^{2}</tex>. Проверяющая программа может проэмулировать <tex>m</tex>, затратив полиномиальное количество времени.
Если НМТ (Недетерминированная машина Тьюринга) <tex>m</tex> допускает слово <tex>x</tex> за время <tex>t</tex>, то существует последовательность действий, которые совершает машина <tex>m</tex>, среди которых могут быть и недетерминированные. Следовательно, существует сертификат <tex>y</tex>. Если же слово не допускается или допускается, но за время, большее <tex>t</tex>, то любая последовательность действий не ведет к допуску слова, а значит нет и последовательности недетерминированных выборов, которые могла бы сделать машина <tex>m</tex>.
Все условия принадлежности классу <tex>NP</tex> выполнены. Что и требовалось доказать.
Теперь докажем, что <tex>BH_{1N}</tex> принадлежит классу <tex>NPH</tex>.
