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.
|Title of host publication||Handbook of Satisfiability|
|Number of pages||22|
|Publication status||Published - 1 Jan 2009|
|Name||Frontiers in Artificial Intelligence and Applications|
Scopus subject areas
- Artificial Intelligence