Search
 
loader loading subjects...
cover
Chapter 16. Worst-Case Upper Bounds
Evgeny Dantsin, Edward A. Hirsch
669 - 692
10.3233/FAIA200999
Research Article
Frontiers in Artificial Intelligence and Applications
Volume 336: Handbook of Satisfiability
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.

$35.00 / €27.50 / £22.00
Add PDF to cart