SAT is a classifical NP problem, now what is the best known algorithm for building an approximate solution? WalkSAT
Pick a random unsatisfied clauses
Consider 3 moves; flipping each variable
If (any improve the evaluation)
accept the best
probability 0.5 : take the least bad
probability 0.5: pick a random move
Impressive no? and what this algorithm reminds to you?