Name
Abstract | ||
|---|---|---|
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: 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))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) algorithm. It turns out that any CSP can be solved with complexity about (d(1-1/l))n. |
Year | Venue | Keywords |
|---|---|---|
1999 | FOCS | simple local-search paradigm,n variable,satisfying assignment,Constraint Satisfaction Problems,order l,simple probabilistic algorithm,corresponding bit,constraint satisfaction problem,initial assignment,polynomial factor,general case,Probabilistic Algorithm |
DocType | ISBN | Citations |
Conference | 0-7695-0409-4 | 134 |
PageRank | References | Authors |
10.87 | 10 | 1 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Uwe Schöning | 1 | 998 | 105.69 |