45
правок
Изменения
Нет описания правки
Сертификатом для решения данной задачи будет последовательность <math> \{c_i\}_ {i=1}^{n}</math>, где <math> n = |V| </math>, а <math> c_i </math> обозначает цвет i-ой вершины. Проверку корректности такого сертификата легко осуществить за полиномиальное время, например, перебором всех пар вершин и проверкой того, что в случае, когда они соединены ребром, они имеют разные цвета, лежащие на отрезке <math> [1, k] </math>.
=== Доказательство принадлежности задачи классу NPH ===
Сведем задачу 3CNFSAT к данной.<br/>
Пусть дана <math> \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) </math>, где <math>a_i</math>, <math>b_i</math> и <math>c_i</math> - переменные или их отрицания (возможно, с повторениями). Сами переменные будем обозначать <math> \{x_i\}_{i=1}^n </math>.
