|
|
(не показано 15 промежуточных версий этого же участника) |
Строка 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>
| + | |
Постройте полиномиальную сводимость задачи 3SAT к задаче CLIQUE.