Random Walk

• Random walk SAT algorithm:

  1) Pick random truth assignment.
  
  2) Repeat until all clauses are satisfied: Flip random variable from unsatisfied clause.

• Solves 2SAT in O(n ) flips. (Papadimitriou 1992)

• Does not work for hard k-SAT (k >= 3).

2

Previous slide

Next slide

Back to first slide

View graphic version