A simple probabilistic algorithm for solving the NP‐complete problem k ‐SAT is reconsidered. This algorithm follows a well‐known local‐search paradigm: randomly guess an initial assignment and then, guided by those clauses that are not satisfied, by successively choosing a random literal from such a clause and changing the corresponding truth value, try to find a satisfying assignment. Papadimitriou [11] introduced this random approach and applied it to the case of 2‐SAT, obtaining an expected O(n2) time bound. The novelty here is to restart the algorithm after 3n unsuccessful steps of local search. The analysis shows that for any satisfiable k ‐CNF formula with n variables the expected number of repetitions until a satisfying assignment is found this way is (2· (k‐1)/ k)n . Thus, for 3‐SAT the algorithm presented here has a complexity which is within a polynomial factor of (\frac 4 3 )n . This is the fastest and also the simplest among those algorithms known up to date for 3‐SAT achieving an o(2n) time bound. Also, the analysis is quite simple compared with other such algorithms considered before.
