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

Материал из DISCOPAL
Перейти к: навигация, поиск
Строка 1: Строка 1:
 
Докажите NP-полноту следующей проблемы. Исходное данное: конечное семейство конечных множеств и натуральное <m>k</m>. Существует ли подсемейство, состоящее из <m>k</m> попарно непересекающихся множеств?
 
Докажите NP-полноту следующей проблемы. Исходное данное: конечное семейство конечных множеств и натуральное <m>k</m>. Существует ли подсемейство, состоящее из <m>k</m> попарно непересекающихся множеств?
  
−
[[Category:Нерешенные задачи]]
+
[[Category:На проверку]]
 +
 
 +
<latex>
 +
Решение (Целых Влады, 974 группа):
 +
\begin{enumerate}
 +
  \item Сначала покажем, что задача принадлежит классу NP.
 +
  Действительно, если искомые множества существуют, то подсказка $y$---это $k$ попарно непересекающихся множеств,
 +
  причем проверку можно осуществить за полиномиальное время, используя память не больше полиномиального объема.
 +
  \item Покажем, что NP-полная задача существования независимого множества из $k$ вершин в графе (IS, Independent Set) полиномиально
 +
  сводится к рассматриваемой задаче.
 +
  Рассмотрим неориентированный связный граф $G=(V,E)$. Спрашивается, существует ли независимое множество из $k$ вершин
 +
  (таких, что никакие две
 +
  вершины множества не соединены ребром). Каждой вершине $v_i$ сопоставим множество инцидентных ей ребер
 +
  $S_{i} = \{(v_i, v_j)\in E\}$. Таким образом, рассматривается семейство из $|V|$ множеств. Если в полученной системе множеств существует $k$ попарно непересекающихся множеств,
 +
  то в графе существует независимое множество мощности $k$ (для этого достаточно взять из каждого из $k$ множеств
 +
  по соответствующей вершине). Наоборот, если в графе существует независимое множество вершин, то $k$ образованных ими множеств $S_i$
 +
  будут попарно непересекающимися. 
 +
  \item Осталось пояснить, почему IS - задача о существовании независимого множества из $k$ вершин в графе
 +
  является NP-полной. Принадлежность к классу $NP$ следует из того, что в качестве подсказки в случае
 +
  ответа "да" можно взять
 +
  $k$ вершин, образующих независимое множество (проверка занимает полиномиальное время).
 +
  Покажем, что задача 3-SAT полиномиально сводится к задаче IS.
 +
 
 +
  Пусть дана конъюнкция из $m$ 3-элементных дизъюнкций $C_1,\dots C_m$, образованных переменными $x_1,\dots x_n$ и
 +
  их отрицаниями $\bar x_1,\dots \bar x_n$. Построим граф $G$ следующим образом. Каждой из $m$ дизъюнкций
 +
  поставим в соответствие ``треугольник'' ---3 вершины, соединенные ребрами (например, если $C_1=x_1 \vee \bar x_2 \vee x_3$, то в графе $G$
 +
  существуют вершины $x_1,\bar x_2,x_3$, между которыми проведены 3 ребра). Таким образом, всего в графе $G$
 +
  $3\cdot m$ вершин. Проведем также ребра между всеми вершинами вида $x_i$ и $\bar x_i$.
 +
  Если конъюнкция выполнима, то в графе существует $m$-элементное независимое множество
 +
  (в каждом ``треугольнике'' выбирается вершина, соответствующая переменной, принимающей значение $1$ в данной конъюнкции). И наоборот, если
 +
  в графе существует $m$-элементное независимое множество $S$, то в него входит по одной вершине из каждого ``треугольника''.
 +
  Кроме того, вершины вида $x_i$ и $\bar x_i$ не могут входить в него одновременно (т.к. тогда множество не будет независимым).
 +
  Набор переменных $x_i = 1$, если $x_i\in S$ и $x_j = 0$, если $x_j \not \in S$ будет выполняющим ДНФ.
 +
  Таким образом, задача IS является NP-полной.
 +
\end{enumerate}
 +
 
 +
 
 +
</latex>

Версия 12:14, 12 декабря 2014

Докажите NP-полноту следующей проблемы. Исходное данное: конечное семейство конечных множеств и натуральное . Существует ли подсемейство, состоящее из попарно непересекающихся множеств?

Источник — «https://discopal.ispras.ru/index.php?title=Полиномиальные_сводимости_и_NP-полные_задачи._Классы_NP,_coNP,_NPC/Задачи/k-подсемейство_множеств_-_NPC&oldid=3241»