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

Материал из DISCOPAL
Перейти к: навигация, поиск
Строка 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