Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/3КНФ→Клика — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) |
|||
Строка 1: | Строка 1: | ||
Постройте полиномиальную сводимость задачи 3SAT к задаче CLIQUE. | Постройте полиномиальную сводимость задачи 3SAT к задаче CLIQUE. | ||
− | [[Category: | + | [[Category:На проверку]] |
<!--Вообще-то, решения уже есть--> | <!--Вообще-то, решения уже есть--> | ||
+ | |||
+ | ===Стенина Мария, группа 974=== | ||
+ | <latex> | ||
+ | Рассмотрим вариант задачи 3SAT, в котором все дизъюнкции имеют длину 3 (решение для дизъюнкций меньшей длины будет аналогичным). Пусть задана КНФ $\varphi = C_1 \cap \ldots \cap C_k$, состоящая из $k$ дизъюнкций. Каждая дизъюнкция состоит из $C_i = l_i^1 \cup l_i^2 \cup l_i^3$. Построим граф с $3k$ вершинами. С каждой вершиной соотнесем литерал $l_i^s$, $i = 1, \ldots, k$, $s = 1, 2, 3$. | ||
+ | $$ | ||
+ | V = \{ l_i^s \mid i = 1, \ldots, k; s = 1, 2, 3 \}. | ||
+ | $$ | ||
+ | Ребрами соединим вершины, относящиеся к разным дизъюнкциям и такими, что $l_i^s \neq \bar{l_j^r}$ | ||
+ | $$ | ||
+ | E = \{ (l_i^r, l_j^r) \mid i \neq j, l_i^s \neq \bar{l_j^r} \}. | ||
+ | $$ | ||
+ | |||
+ | Если $\varphi$ выполнима, то для каждого $i$ найдется $s$, такое что $l_i^s = 1$. Выберем в графе вершины, соответствующие этим литералам, и получим клику размера $k$, потому что все эти вершины в графе соединены между собой по построению. Мы соединяли вершины, соответствующие разным дизъюнкциям, за исключением тех, которые являются отрицанием друг друга. Поэтому, если рассматриваемая КНФ выполнима, то в построенном графе найдется клика размера $k$. | ||
+ | |||
+ | Пусть в графе есть клика размера $k$. Присвоим всем литералам, попавшим в клику, значение 1, не попавшим - значение 0. Так как по построению графа в клику не могли попасть литералы из одной дизъюнкции, то в КНФ в каждой скобке окажется литерал, равный 1, а значит, вся КНФ выполнима. | ||
+ | |||
+ | </latex> |
Версия 14:21, 9 ноября 2014
Постройте полиномиальную сводимость задачи 3SAT к задаче CLIQUE.
Стенина Мария, группа 974