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>m\,\!</math> есть строка <math>z\#_qyb</math>, где <math>b\,\!</math> — строка, состоящая из такого количества пробелов, чтобы длина всего МО была <math>t + 1.\,\!</math>
