NAME: SAT-solving: Performance analysis of Survey Propagation and DPLL
NamE: {SAT}-solving: Performance analysis of Survey Propagation and {DPLL}
AUTH: Christian Steinruecken
YEAR: 2006
MNTH: 06
ABST: 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.
HWPB: Technical Report, Cavendish Laboratory, University of Cambridge
XURL: http://cstein.kings.cam.ac.uk/~chris/satcmp.pdf
WGET: http://cstein.kings.cam.ac.uk/~chris/satcmp.pdf
SHA1: 67498d7d2dcd2f2b46f5f0808d58564de020f2f4
FILE: steinruecken2006a.pdf