Worst-case upper bounds

Evgeny Dantsin, Edward A. Hirsch

Research outputpeer-review

26 Citations (Scopus)

Abstract

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
Publication statusPublished - 1 Jan 2009

Publication series

NameFrontiers in Artificial Intelligence and Applications
Number1
Volume185
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