|
|
Строка 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)$.
| + | |
− | | + | |
− | В статье
| + | |
− | </m>
| + | |
− | http://www.math.ucsd.edu/~sbuss/CourseWeb/Math268_2007WS/2SAT.pdf
| + | |
− | | + | |
− | <m>
| + | |
− | | + | |
− | доказано, что 2-КНФ выполнима тогда и только тогда, когда $\forall\quad i\quad x_i\quad and \quad\overline{x_i}$ не принадлежат одной и той же связной компоненте в полученном направленном графе. Связные компоненты находятся в графе за $O(|E| + |V|)$, за столько же можно сделать проверку на наличие переменной и ее отрицания в одной и той же связной компоненте. Поэтому 2-SAT $\in P$
| + | |
− | | + | |
− | </m>
| + | |
Покажите, что задача 2SAT лежит в P.