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

Schöning, U.

Algorithmica 32, No. 4, 615-623 (2002).

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.

MSC:

68Q25	Analysis of algorithms and problem complexity
68W20	Randomized algorithms
68P10	Searching and sorting

Keywords:

satisfiability problem; NP-completeness