Изменения
Нет описания правки
<tex>SAT \in NPC</tex>, если
*<tex>SAT \in</tex> [[NP|<tex>NP</tex><ref>[[NP|Класс NP]]</ref>*<tex>SAT \in </tex> [[NP-полнота|<tex>NPH</tex><ref>[[NP-полнота|NP-трудные задачи]]</ref>
=== Доказательство того, что ''SAT'' ∈ ''NP'' ===
=== Доказательство того, что ''SAT'' ∈ ''NPH'' ===
Теперь докажем, что <tex>SAT \in NPH.</tex> Для этого сведём проблему [[NP-полнота_задачи_BH1N|<tex>BH_{1N}</tex><ref>[[NP-полнота_задачи_BH1N]]</ref>, которая, как нам известно, <tex>NP</tex>-полна, к проблеме <tex>SAT.</tex> Тогда получится, что любая проблема из <tex>NP</tex> может быть сведена по Карпу к проблеме <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> шагов и допускает это слово.
== Ссылки ==
# [http://infolab.stanford.edu/~ullman/ialc.html Хопкрофт Дж., Мотвани Р., Ульман Дж., "Введение в теорию автоматов, языков и вычислений"]
<references/>
