@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.
   },
}