Name
Abstract | ||
|---|---|---|
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 it) the case of 2-SAT, obtaining an expected O(n(2)) time bound. The novelty here is to restart (lie 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 (4/3)(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. |
Year | DOI | Venue |
|---|---|---|
2002 | 10.1007/s00453-001-0094-7 | Algorithmica |
Keywords | Field | DocType |
polynomial factorization,local search,satisfiability,probabilistic algorithm,np complete problem | Discrete mathematics,Randomized algorithm,Combinatorics,Polynomial,Boolean satisfiability problem,Propositional calculus,Probabilistic analysis of algorithms,Probability distribution,Expected value,Local search (optimization),Mathematics | Journal |
Volume | Issue | ISSN |
32 | 4 | 0178-4617 |
Citations | PageRank | References |
38 | 1.76 | 5 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Uwe Schöning | 1 | 998 | 105.69 |