A probabilistic algorithm for \(k\)-SAT based on limited local search and restart. (English) Zbl 1050.68049

Summary: 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. C. H. Papadimitriou [“On selecting a satisfying truth assignment”, Proc. 32nd Annual IEEE Symposium on the Foundations of Computer Science, 163–169 (1991)] introduced this random approach and applied it to the case of 2-SAT, obtaining an expected \(O(n^2)\) 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\cdot(k-1)/k)^n\). Thus, for 3-SAT the algorithm presented here has a complexity which is within a polynomial factor of \((\frac 43)^n\). This is the fastest and also the simplest among those algorithms known up to date for 3-SAT achieving an \(o(2^n)\) time bound. Also, the analysis is quite simple compared with other such algorithms considered before.


68Q25 Analysis of algorithms and problem complexity
68W20 Randomized algorithms
68P10 Searching and sorting
Full Text: DOI