Worst-case upper bounds

Evgeny Dantsin, Edward A. Hirsch

Research outputpeer-review

26 Citations (Scopus)


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
Number of pages22
ISBN (Print)9781586039295
Publication statusPublished - 1 Jan 2009

Publication series

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

Scopus subject areas

  • Artificial Intelligence

Cite this

Dantsin, E., & Hirsch, E. A. (2009). Worst-case upper bounds. In Handbook of Satisfiability (1 ed., pp. 403-424). (Frontiers in Artificial Intelligence and Applications; Vol. 185, No. 1). IOS Press. https://doi.org/10.3233/978-1-58603-929-5-403