Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/ex-2sat-in-p — различия между версиями
Материал из DISCOPAL
(AD) |
|||
| Строка 18: | Строка 18: | ||
КНФ, в котором $2n$ узлов, соответствующих $\forall i x_i, \overline{x_i}$, и $2m$ направленных ребер - дизъюнкции $(x\bigvee y)$ соответствуют ребра $(\overline{x} \to y)$ и $(\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> | ||
| + | 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> | </m> | ||
Версия 14:57, 22 ноября 2014
Покажите, что задача 2SAT лежит в P.
Стенин Сергей группа 974
http://www.math.ucsd.edu/~sbuss/CourseWeb/Math268_2007WS/2SAT.pdf