Изменения
Нет описания правки
==== Доказательство корректности сведения ====
Покажем теперь, что такой граф будет <tex>(n+1)</tex>-раскрашиваемым тогда и только тогда, когда исходная формула принадлежит <tex> 3CNFSAT </tex>.
# <tex> \Rightarrow </tex>. Из построения ясно, что можно покрасить вершины полученного графа, соответствующие истинным термам набора, обращающего формулу в истину, в цвет <tex>c0c_0</tex>, а вершины, соответствующие ложным термам, — в соответствующие "ложные" цвета.
# <tex> \Leftarrow </tex>. Построим по раскраске графа набор переменных <tex> \{x_i\}_{i=1}^n </tex>, в котором <tex> x_i </tex> истинно тогда и только тогда, когда <tex> v_i </tex> покрашена в цвет <tex> c_0 </tex>. Этот набор непротиворечив (мы не попытались одну и ту же переменную сделать и истинной, и ложной одновременно). Он также обращает формулу в истинную, так как по постронию в каждой скобке есть хотя бы один истинный терм.
