@misc{steinruecken2006a,
title = {{SAT}-solving: Performance analysis of Survey Propagation and {DPLL}},
author = {Christian Steinruecken},
year = {2006},
month = jun,
url = {http://cstein.kings.cam.ac.uk/~chris/satcmp.pdf},
howpublished = {Technical Report, Cavendish Laboratory, University of Cambridge},
abstract = {
The Boolean Satisfiability Problem (SAT) belongs to the class
of NP-complete problems, meaning that there is no known
deterministic algorithm that can solve an arbitrary problem
instance in less than exponential time (parametrized on the
length of the input). There is great industrial demand for
solving SAT, motivating the need for algorithms which perform
well. I present a comparison of two approaches for solving SAT
instances: DPLL (an exact algorithm from classical computer
science) and Survey Propagation (a probabilistic algorithm from
statistical physics). The two algorithms were compared on
randomly generated 3-SAT problems with varying clause to
variable ratios.
},
}