Sch¨ oning's random-restart hill-climbing k-SAT algorithm
David Eppstein · 2000
If this sequence of random experiments ever finds a satisfying assignment, we know that the formula is satisfiable and can halt. Each trial can be performed in timeO(mn), where m is the number of clauses and n the number of variables, so the overall running time is K times a polynomial. The question is, how big does K need to be to have high probability of finding a satisfying assignment? To analyze this algorithm, assume that the formula is satisfiable, and let A∗ be some particular satisfying assignment (choose one arbitrarily if there is more than one). Then, for any other truth assignment A, define d(A) to be the Hamming distance from A to A∗; that is, the number of variables that would have to be flipped to get to the satisfying assignment A∗. What happens to d(A) in the inner loop of the algorithm? At each step, we pick an unsatisfied clause of the formula. Since this clause is satisfied by A∗, we know that A and A∗ differ on at least one of the k variables of this clause. By flipping a randomly chosen variable, we know that with probability at least 1/k we choose one of the variables where they differ, and reduce d by one. With probability at most (k− 1)/k, though, we can increase d by one.