Papadimitriou's 2SAT Algorithm

External

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

Internal

• Local Search
• The 2SAT Problem

Overview

Generally, local search heuristics are not guaranteed to run in polynomial time. The randomized local search algorithm for the 2SAT problem is one of the rare cases when we can prove it is guaranteed to converge with the correct answer quickly.