Search
 
loader loading subjects...
cover
Worst-Case Upper Bounds
Evgeny Dantsin, Edward A. Hirsch
403 - 424
10.3233/978-1-58603-929-5-403
Chapter 12
Frontiers in Artificial Intelligence and Applications
Volume 185: 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