Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/ex-2sat-in-p — различия между версиями
Материал из DISCOPAL
StasFomin (обсуждение | вклад) |
|||
Строка 1: | Строка 1: | ||
Покажите, что задача 2SAT лежит в P. | Покажите, что задача 2SAT лежит в P. | ||
− | [[Category: | + | [[Category:На проверку]] |
− | < | + | |
+ | ==Стенин Сергей группа 974== | ||
+ | |||
+ | <m> | ||
+ | |||
+ | В задаче 2-SAT каждая элементарная дизъюнкция имеет длину $k\leq 2$. Для начала покажем, что можно исключить дизъюнкты, которые состоят из одного терма. | ||
+ | |||
+ | Если встретился дизъюнкт $x_i$, то положим $x_i\equiv 1$. Тогда можно выкинуть из формулы сам дизъюнкт $x_i$. Также можно выкинуть из КНФ все скобки, куда $x_i$ входит в первой степени. В дизъюнктах, где встречается $\overline{x_i}$, можно выкинуть $\overline{x_i}$, так как он равен нулю. Если после всех упрощений есть еще и дизъюнкт $\overline{x_i}$, то формула неразрешима. Для $\overline{x_i}$ рассуждения аналогичны. | ||
+ | |||
+ | Описанным выше алгоритмом 2-SAT приводится к виду, когда в формуле дизъюнкты только из двух термов. | ||
+ | |||
+ | Далее заметим, что $(x\bigvee y) \equiv (\overline{x} \to y) \bigwedge (\overline{y}\to x)$ | ||
+ | |||
+ | Построим граф, который соответствует рассматриваемой | ||
+ | КНФ, в котором $2n$ узлов, соответствующих $\forall i x_i, \overline{x_i}$, и $2m$ направленных ребер - дизъюнкции $(x\bigvee y)$ соответствуют ребра $(\overline{x} \to y)$ и $(\overline{y}\to x)$. | ||
+ | |||
+ | В статье http://www.math.ucsd.edu/~sbuss/CourseWeb/Math268_2007WS/2SAT.pdf доказано, что 2-КНФ выполнима тогда и только тогда, когда $\forall i x_i and \overline{x_i}$ не принадлежат одной и той же связной компоненте в полученном направленном графе. Связные компоненты находятся в графе за $O(|E| + |V|)$, за столько же можно сделать проверку на наличие переменной и ее отрицания в одной и той же связной компоненте. Поэтому 2-SAT $\in P$ | ||
+ | |||
+ | </m> |
Версия 14:56, 22 ноября 2014
Покажите, что задача 2SAT лежит в P.
Стенин Сергей группа 974