# <tex> 3SAT \in NPH </tex>;
----
# Для того, чтобы доказать, что <tex>3SAT \in NP </tex>, предъявим сертификат: набор <tex>x_1 \ldots x_{n}</tex>, удовлетворяющий формулу.
----Для того, чтобы доказать первый факт, предъявим сертификат: набор <tex>x_1 \ldots x_{n}</tex>, удовлетворяющий формулу.
Теперь докажем <tex>NP</tex>-трудность <tex>3SAT</tex>.
Для этого покажем, что <tex>CNFSAT \le 3SAT</tex>, то есть <tex>CNFSAT</tex> сводится по Куку к <tex>3SAT</tex>.
