The chapter is a survey of ideas and techniques behind satisfiability algorithms with the currently best asymptotic upper bounds on the worst-case running time. The survey also includes related structural-complexity topics such as Schaefer's dichotomy theorem, reductions between various restricted cases of SAT, the exponential time hypothesis, etc.

Original languageEnglish
Title of host publicationHandbook of Satisfiability
PublisherIOS Press
Pages403-424
Number of pages22
Edition1
ISBN (Print)9781586039295
DOIs
StatePublished - 1 Jan 2009

Publication series

NameFrontiers in Artificial Intelligence and Applications
Number1
Volume185
ISSN (Print)0922-6389

    Scopus subject areas

  • Artificial Intelligence

ID: 49827781