Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/ex-2sat-in-p — различия между версиями
Материал из DISCOPAL
(AD) |
(→Стенин Сергей группа 974) |
||
Строка 23: | Строка 23: | ||
<m> | <m> | ||
+ | |||
доказано, что 2-КНФ выполнима тогда и только тогда, когда $\forall\quad i\quad x_i\quad and \quad\overline{x_i}$ не принадлежат одной и той же связной компоненте в полученном направленном графе. Связные компоненты находятся в графе за $O(|E| + |V|)$, за столько же можно сделать проверку на наличие переменной и ее отрицания в одной и той же связной компоненте. Поэтому 2-SAT $\in P$ | доказано, что 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