The 2SAT Problem

External

• https://www.coursera.org/learn/algorithms-npcomplete/lecture/ERxmM/the-2-sat-problem
• https://www.coursera.org/learn/algorithms-npcomplete/lecture/kRmJe/random-walks-on-a-line
• https://www.coursera.org/learn/algorithms-npcomplete/lecture/YltoR/analysis-of-papadimitrious-algorithm

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

Algorithms

• Reduction to computing strongly connected components.
• "Backtracking"
• Papadimitriou's 2SAT randomized local search. Generally, local search heuristics are not guaranteed to run in polynomial time. This 2SAT problem is one of the rare cases when we can prove it is guaranteed to converge with the correct answer quickly.