2003/01/20 by T. Schoning · 7 citations
Computer Science · #Constraint Satisfaction and Optimization #Advanced Graph Theory Research #Logic, Reasoning, and Knowledge
paper · doi:10.1109/sffcs.1999.814612
openalex publication_date 2003/01/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
We present a simple probabilistic algorithm for solving k-SAT and more generally, for solving constraint satisfaction problems (CSP). The algorithm follows a simple local search paradigm (S. Minton et al., 1992): randomly guess an initial assignment and then, guided by those clauses (constraints) that are not satisfied, by successively choosing a random literal from such a clause and flipping the corresponding bit, try to find a satisfying assignment. If no satisfying assignment is found after O(n) steps, start over again. Our analysis shows that for any satisfiable k-CNF-formula with n variables this process has to be repeated only t times, on the average, to find a satisfying assignment, where t is within a polynomial factor of (2(1-1/k))/sup n/. This is the fastest (and also the simplest) algorithm for 3-SAT known up to date. We consider also the more general case of a CSP with n variables, each variable taking at most d values, and constraints of order l, and analyze the complexity of the corresponding (generalized) algorith m. It turns out that any CSP can be solved with complexity at most (d/spl middot/(1-1/l)+/spl epsiv/)/sup n/.