Deterministic algorithms for k-SAT based on covering codes and local search

Evgeny Dantsin, Andreas Goerdt, Edward A. Hirsch, Uwe Schöning

Research output

24 Citations (Scopus)

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.481n.

Original languageEnglish
Title of host publicationAutomata, Languages and Programming - 27th International Colloquium, ICALP 2000, Proceedings
EditorsUgo Montanari, Emo Welzl, Jose D. P. Rolim
PublisherSpringer Nature
Pages236-247
Number of pages12
ISBN (Print)9783540450221
Publication statusPublished - 1 Jan 2000
Event27th International Colloquium on Automata, Languages and Programming, ICALP 2000 - Geneva
Duration: 9 Jul 200015 Jul 2000

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume1853
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference27th International Colloquium on Automata, Languages and Programming, ICALP 2000
CountrySwitzerland
CityGeneva
Period9/07/0015/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.