test=== Определение ===Проблема <math>SAT = \{\phi(x_1, ..., x_n)\ |\ \exists \{y_1, ..., y_n\} : \phi(y_1, ..., y_n) = 1\}</math> — проблема выполнимости булевых формул. Докажем, что эта проблема <math>NP\,\!</math>-полна. == Формулировка =='''Теорема Кука''' гласит, что <math>SAT \in NPC.</math> == Доказательство ==<math>SAT \in NPC</math>, если*<math>SAT \in NP</math>*<math>SAT \in NPH</math>Прежде всего докажем, что <math>SAT \in NP.</math> Так как <math>NP = \Sigma_1\,\!</math>, то достаточно показать, что <math>SAT \in \Sigma_1</math> В качестве сертификата берём набор нулей и единиц в количестве <math>n\,\!</math> штук, соответствующих значениям аргументов функции <math>\phi\,\!</math>. Длина этого сертификата явно будет меньше или равна, чем полином от длины строки, кодирующей формулу <math>\phi\,\!</math>. Верификатор просто подставит эти значения в формулу <math>\phi\,\!</math> и выдаст значение формулы на данном входе. Таким образом, если формула действительно удовлетворима, то для неё найдётся такой сертификат, на котором она, и, соответственно, верификатор, выдадут единицу. Если же у нас существует такой сертификат <math>y\,\!</math>, на котором верификатор выдаёт единицу, то, значит, и формула является удовлетворимой.
