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