A deterministic (2 - 2/(k + 1))n algorithm for k-SAT based on local search

Evgeny Dantsin, Andreas Goerdt, Edward A. Hirsch, Ravi Kannan, Jon Kleinberg, Christos Papadimitriou, Prabhakar Raghavan, Uwe Schöning

Research output

118 Citations (Scopus)

Abstract

Local search is widely used for solving the propositional satisfiability problem. Papadimitriou (1991) showed that randomized local search solves 2-SAT in polynomial time. Recently, Schöning (1999) proved that a close algorithm for k-SAT takes time (2 - 2/k)n up to a polynomial factor. This is the best known worst-case upper bound for randomized 3-SAT algorithms (cf. also recent preprint by Schuler et al.). We describe a deterministic local search algorithm for k-SAT running in time (2 - 2/(k + 1))n up to a polynomial factor. The key point of our algorithm is the use of covering codes instead of random choice of initial assignments. Compared to other "weakly exponential" algorithms, our algorithm is technically quite simple. We also describe an improved version of local search. For 3-SAT the improved algorithm runs in time 1.481n up to a polynomial factor. Our bounds are better than all previous bounds for deterministic k-SAT algorithms.

Original languageEnglish
Pages (from-to)69-83
Number of pages15
JournalTheoretical Computer Science
Volume289
Issue number1
DOIs
Publication statusPublished - 23 Oct 2002

Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'A deterministic (2 - 2/(k + 1))<sup>n</sup> algorithm for k-SAT based on local search'. Together they form a unique fingerprint.

  • Cite this

    Dantsin, E., Goerdt, A., Hirsch, E. A., Kannan, R., Kleinberg, J., Papadimitriou, C., Raghavan, P., & Schöning, U. (2002). A deterministic (2 - 2/(k + 1))n algorithm for k-SAT based on local search. Theoretical Computer Science, 289(1), 69-83. https://doi.org/10.1016/S0304-3975(01)00174-8