2-SAT (X1V-X2)(X2V-X3)(X4VX3)(X5VX)(X4V-X5) 0 Start with a random assignment, -say (X1,X2,X3,Xa,Xs)=(F,T,F,F,T) Number of xis that agrees with the solution(i.e.number of i such thatx;=T) 0 2 3 52-SAT • (x1∨¬x2 )∧(x2∨¬x3 )∧(x4∨x3 )∧(x5∨x1 )∧(x4∨¬x5 ) • Start with a random assignment, – say (x1 , x2 , x3 , x4 , x5 ) = (F, T, F, F, T) 0 1 2 3 4 5 Number of xi s that agrees with the solution (i.e. number of i such that xi = T)