Полиномиальные сводимости и NP-полные задачи. Классы NP, coNP, NPC/Задачи/ex-2sat-in-p — различия между версиями

<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>