### 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 worst-case 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.481^{n}.

Original language | English |
---|---|

Title of host publication | Automata, Languages and Programming - 27th International Colloquium, ICALP 2000, Proceedings |

Editors | Ugo Montanari, Emo Welzl, Jose D. P. Rolim |

Publisher | Springer Nature |

Pages | 236-247 |

Number of pages | 12 |

ISBN (Print) | 9783540450221 |

Publication status | Published - 1 Jan 2000 |

Event | 27th International Colloquium on Automata, Languages and Programming, ICALP 2000 - Geneva Duration: 9 Jul 2000 → 15 Jul 2000 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 1853 |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Conference

Conference | 27th International Colloquium on Automata, Languages and Programming, ICALP 2000 |
---|---|

Country | Switzerland |

City | Geneva |

Period | 9/07/00 → 15/07/00 |

### Scopus subject areas

- Theoretical Computer Science
- Computer Science(all)

## Fingerprint Dive into the research topics of 'Deterministic algorithms for k-SAT based on covering codes and local search'. Together they form a unique fingerprint.

## Cite this

Dantsin, E., Goerdt, A., Hirsch, E. A., & Schöning, U. (2000). Deterministic algorithms for k-SAT based on covering codes and local search. In U. Montanari, E. Welzl, & J. D. P. Rolim (Eds.),

*Automata, Languages and Programming - 27th International Colloquium, ICALP 2000, Proceedings*(pp. 236-247). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 1853). Springer Nature.