SAT Solvers: Recent Theory

Minimal size of search tree



(Beame, Karp, et al. 1998)


Better worst-case: less than O(2^n)

backtrack style: O(2^(0.387n))
(Schiermeyer 1997; Paturi, et al. 1998)

local search: O(2^(c.n)) with c < 1
(Hirsch, 1998)

Previous slide

Next slide

Back to first slide

View graphic version