2-SAT (X1V-X2)^(X2V-X3)^(X4VX3)A(x5VX1)A(X4V-X5) clauses X1 X2 X3 Xa X5 current F T F F T Find an unsatisfied clause:(X4VX3) flip one of the value of x3 and x4 randomly If we flip x3,then we jump from 2 to 3 If we flip x4,then we jump from 2 to 32-SAT • (x1∨¬x2 )∧(x2∨¬x3 )∧(x4∨x3 )∧(x5∨x1 )∧(x4∨¬x5 ) • Find an unsatisfied clause: (x4∨x3 ) • flip one of the value of x3 and x4 randomly – If we flip x3 , then we jump from 2 to 3 – If we flip x4 , then we jump from 2 to 3 x1 x2 x3 x4 x5 current F T F F T clauses