45
правок
Изменения
Нет описания правки
# Ровно одно выражение из <math> \{x_i, \lnot {x_i}\} </math> истинно;
# <math> \varphi \in 3CNFSAT </math> тогда и только тогда, когда существует набор, обращающий каждую скобку в истину.
Построим множества V и E будущего графа следущим следующим образом:
* <math> V = \{c_i\}_{i=0}^n </math>;
* <math> E = \{<c_i, c_j>\}_{i,j=0, i \ne j}^n </math>.
