|
|
| (не показано 15 промежуточных версий 2 участников) |
| Строка 1: |
Строка 1: |
| | Покажите, что задача 2SAT лежит в P. | | Покажите, что задача 2SAT лежит в P. |
| | | | |
| − | [[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>
| + | |