Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/3SAT→3Coloring — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) |
|||
| Строка 2: | Строка 2: | ||
число выполняющих наборов переменных для 3SAT задачи, равнялось бы шестикратному количеству раскрасок в три цвета. | число выполняющих наборов переменных для 3SAT задачи, равнялось бы шестикратному количеству раскрасок в три цвета. | ||
| − | [[Category: | + | [[Category:На проверку]] |
| − | <!-- | + | |
| + | ==Стенин Сергей группа 974== | ||
| + | |||
| + | <m> | ||
| + | |||
| + | 1. Число раскрасок в 3 цвета кратно шести, так как перестановка цветов в правильной раскраске по-прежнему является правильной раскраской, а всего таких перестановок $3! = 6$. | ||
| + | |||
| + | 2. Пусть нам дана КНФ из $m$ дизъюнкций с $n$ переменными. Построим граф, соответствующий этой КНФ, следующим образом. Число вершин в нем будет равно $|V| = 7m + 2n + 3$. Для описания того, как граф устроен, пометим часть вершин. Три вершины пометим числами $0,1,2$. Каждым литералом ($x_i$ и $\overline{x_i}$) пометим еще по одной вершине. Остальные $7m$ вершин разобьем на группы по 7 штук, одна группа будет соответствовать одной дизъюнкции. | ||
| + | |||
| + | 3. Теперь расставим в графе ребра. Вершины $0,1,2$ соединим между собой ребрами. Для каждой $x_i$ соединим $x_i$, $\overline{x_i}$ и вершину $2$ в треугольник. | ||
| + | |||
| + | </m> | ||
| + | |||
| + | [[Файл:2014-11-23 20-59-35 Скриншот экрана.png|обрамить|центр|Добавление ребер в граф]] | ||
| + | |||
| + | <m> | ||
| + | |||
| + | Для каждого дизъюнкта для литералов $l_1, l_2, l_3$, входящих в этот дизъюнкт, добавим к вершинам, соответствующим текущему дизъюнкту, ребра так, как показано на рисунке в. При этом некоторые ребра мы перечислили по нескольку раз. | ||
| + | |||
| + | Очевидно, что описанное построение можно выполнить за полиномиальное время от $n$ и $m$. Теперь надо доказать корректность. | ||
| + | |||
| + | 4. Рассмотрим правильные покраски в 3 цвета для полученного графа. Будем считать, что мы из шести возможных перестановок трех цветов зафиксировали какую-то одну. Поэтому без ограничения общности, пусть вершины $0,1,2$ покрашены в цвета $0,1,2$. Тогда вершины $x_i$ и $\overline{x_i}$ покрашены в цвета $0$ и $1$, причем в разные. Для графа на рисунке (в) прямым перебором проверяется, что выполнено следующее свойство. Если покрасить вершины, соответствующие литералам в дизъюнкции в цвет $0$ или $1$, а отрицания литералов - в противоположные цвета, то есть в $1$ или $0$, то правильная раскраска графа в три цвета существует и единственна тогда и только тогда, когда хотя бы одно из значений литералов отлично от нуля. | ||
| + | |||
| + | Таки образом, показано, что правильные раскраски графа в три цвета так, что вершинам $0,1,2$ соответствуют цвета $0,1,2$, находятся во взаимно однозначном соответствии с выполняющими наборами 3-КНФ, при этом, в силу наличия шести перестановок трех цветов, число выполняющих наборов для 3-КНФ равно шестикратному количеству раскрасок в три цвета. | ||
| + | |||
| + | </m> | ||
Версия 18:40, 23 ноября 2014
Постройте полиномиальное сведение задачи 3SAT к задаче Vertex 3 coloring, такое, что число выполняющих наборов переменных для 3SAT задачи, равнялось бы шестикратному количеству раскрасок в три цвета.
Стенин Сергей группа 974
Добавление ребер в граф