2-SAT .Given (X1V-X2)A(X2V-X3)A(X4 VX3)A(X5 VX1)A(X4V-X5) .(X1,X2,X3,X4,Xs)=(T,T,T,T,T)is a satisfying assignment. Suppose you do not know about this solution You do not even know if there exists a solution for this formula How to decide if there is one using randomness?2-SAT • Given (x1∨¬x2 )∧(x2∨¬x3 )∧(x4∨x3 )∧(x5∨x1 )∧(x4∨¬x5 ) • (x1 , x2 , x3 , x4 , x5 ) = (T, T, T, T, T) is a satisfying assignment. • Suppose you do not know about this solution • You do not even know if there exists a solution for this formula • How to decide if there is one using randomness?