Name
Abstract | ||
|---|---|---|
We show that satisfiability of formulas in k-CNF can be decided deterministically in time close to (2k=(k + 1))n, where n is the number of variables in the input formula. This is the best known worstcase upper bound for deterministic k-SAT algorithms. Our algorithm can be viewed as a derandomized version of Schöning's probabilistic algorithm presented in [15]. The key point of our algorithm is the use of covering codes together with local search. Compared to other "weakly exponential" algorithms, our algorithm is technically quite simple. We also show how to improve the bound above by moderate technical effort. For 3-SAT the improved bound is 1:481n. |
Year | Venue | Keywords |
|---|---|---|
2000 | ICALP | deterministic algorithms,moderate technical effort,local search,weakly exponential,probabilistic algorithm,input formula,time close,key point,deterministic k-sat algorithm,covering codes,derandomized version,upper bound |
Field | DocType | Volume |
Randomized algorithm,Discrete mathematics,Combinatorics,Exponential function,Upper and lower bounds,Computer science,Satisfiability,Algorithm,Probabilistic analysis of algorithms,Local search (optimization),Deterministic algorithm,Propositional formula | Conference | 1853 |
ISSN | ISBN | Citations |
0302-9743 | 3-540-67715-1 | 12 |
PageRank | References | Authors |
1.43 | 11 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Evgeny Dantsin | 1 | 576 | 49.92 |
| Andreas Goerdt | 2 | 441 | 36.15 |
| Edward A. Hirsch | 3 | 422 | 38.02 |
| Uwe Schöning | 4 | 998 | 105.69 |