Изменения

=== Доказательство того, что ''SAT'' ∈ ''NP'' ===

Прежде всего докажем, что <tex>SAT \in NP.</tex>

В качестве сертификата берём набор нулей и единиц в количестве <tex>n\,\!</tex> штук, соответствующих значениям аргументов функции <tex>\phi\,\!</tex>. Длина этого сертификата явно будет меньше или равна, чем полином от длины строки, кодирующей формулу <tex>\phi\,\!</tex>.