1
$\begingroup$

I want to understand the proof in the following link that 2SAT is in P. What is the need for the last corollary? Wouldn't be enough to just prove the case for the graph with the help of the path search?

Furthermore, is the proof for the corollary correct? The algorithm is presented there without proof.

Improve this question
$\endgroup$
1
  • $\begingroup$ "The same graph construction can be used to construct a satisfying assignment for $\Psi$ (if it is satisfiable)." $\endgroup$
    – Yuval Filmus
    Commented Apr 21, 2022 at 8:11

1 Answer 1

Reset to default
1
$\begingroup$

You don't need the corollary in order to show that 2SAT is in P. Rather, it uses the same techniques to give a fast algorithm for finding a satisfying assignment for satisfiable 2CNFs.

If you're not sure whether the algorithm actually works, try proving it.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.