The 2SAT Problem

External

• https://www.coursera.org/learn/algorithms-npcomplete/lecture/ERxmM/the-2-sat-problem

Internal

• NP Completeness
• Local Search

The Problem

Given a set of n boolean variables x₁, x₂, ..., x_n, that can be set to true or false and a set of m clauses of two literals each (a "literal" is a variable or the negation of the variable: x_i or !x_i). The output is determining whether there is a variable assignment that simultaneously satisfies every clause.

The 2SAT problem can be solved in polynomial time - it is not an NP-complete problem. Unlike 2SAT, the 3SAT problem is NP-complete.

Algorithms

• Reduction to computing strongly connected components.
• "Backtracking"
• Papadimitriou's 2SAT randomized local search.