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