Изменения

=== Доказательство принадлежности задачи классу NPH ===

[[Файл:3cnfsat.png|thumb|350px|Граф, построенный по формуле <tex refresh dpi=100> (x_1 \lor \lnot x_2 \lor \lnot x_3) \land (\lnot x_1 \lor x_2 \lor \lnot x_3) \land (\lnot x_1 \lor \lnot x_2 \lor x_3)</tex>]]

Пусть дана формула <tex> \varphi = (a_1 \lor b_1 \lor c_1) \land (a_2 \lor b_2 \lor c_2) \land ... \land (a_m \lor b_m \lor c_m) </tex>, где <tex>a_i</tex>, <tex>b_i</tex> и <tex>c_i</tex> &mdash; переменные или их отрицания (возможно, с повторениями). Сами переменные будем обозначать <tex> \{x_i\}_{i=1}^n </tex>.<br/> Заметим следующие тривиальные факты, которые будут использованы при построении графа:

# Ровно одно выражение из <tex> \{x_i, \lnot {x_i}\} </tex> истинно;