Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/3КНФ→Клика — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
(Массовая правка: замена :Нерешенные задачи]] на :Решенные задачи]])
(не показано 14 промежуточных версий этого же участника)
Строка 1: Строка 1:
 
Постройте полиномиальную сводимость задачи 3SAT к задаче CLIQUE.
 
Постройте полиномиальную сводимость задачи 3SAT к задаче CLIQUE.
  
[[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>
+

Версия 15:49, 20 мая 2020

Постройте полиномиальную сводимость задачи 3SAT к задаче CLIQUE.