53
правки
Изменения
Нет описания правки
=== Доказательство того, что ''SAT'' ∈ ''NPH'' ===
Теперь докажем, что <tex>SAT \in NPH.</tex> Для этого сведём проблему <tex>BH_{1N}</tex><ref>[[NP-полнота_задачи_BH1N|NP-полнота задачи <math>BH_{1N}</math>]]</ref>, которая, как нам известно, <tex>NP</tex>-полна, к проблеме <tex>SAT.</tex> Тогда получится, что любая проблема из <tex>NP</tex> может быть сведена по Карпу<ref>[[Сведение_по_Карпу|Сведение сведена по Карпу]]</ref> к проблеме <tex>BH_{1N}</tex>, и, по транзитивности сведения по Карпу, к <tex>SAT.</tex>
По условию проблемы <tex>BH_{1N}</tex>, у нас есть недетерминированная машина Тьюринга <tex>m</tex>, причём можно считать, что её лента односторонняя и что машина не пишет на ленту пробелы, входное слово <tex>x</tex> и время <tex>t</tex>, заданное в унарной системе счисления. Нам же надо построить такую булеву формулу <tex>\phi</tex>, что она выполнима тогда, и только тогда, когда <tex>m</tex>, получив на вход <tex>x</tex>, делает не более <tex>t</tex> шагов и допускает это слово.
