10
правок
Изменения
Нет описания правки
Если же у нас существует такой сертификат <math>y\,\!</math>, на котором верификатор выдаёт единицу, то, значит, и формула является удовлетворимой.
Теперь докажем, что <math>SAT \in NPH.</math> Для этого сведём проблему <math>BH_{1N}\,\!</math>, которая, как нам известно, <math>NP\,\!</math>-полна, к проблеме <math>SAT.\,\!</math> Тогда получится, что любая проблема из <math>NP\,\!</math> может быть сведена по Карпу к проблеме <math>BH_{1N}\,\!</math>, и, соответственнопо транзитивности сведения по Карпу, к <math>SAT.\,\!</math>
По условию проблемы <math>BH_{1N}\,\!</math>, у нас есть недетерминированная машина Тьюринга <math>m\,\!</math>, причём можно считать, что её лента односторонняя и что машина не пишет на ленту пробелы, входное слово <math>x\,\!</math> и время <math>t\,\!</math>, заданное в унарной системе счисления. Нам же надо построить такую булеву формулу <math>\phi\,\!</math>, что она выполнима тогда, и только тогда, когда <math>m\,\!</math>, получив на вход <math>x\,\!</math>, делает не более <math>t\,\!</math> шагов и допускает это слово.
