Теорема Кука

Определение

Проблема [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], на котором верификатор выдаёт единицу, то, значит, и формула является удовлетворимой.