In recent years statistical physics and computational complexity have found mutually interesting subjects of research. The theory of spin glasses from statistical physics has been successfully applied to the boolean satisfiability problem, which is the canonical topic of computational complexity.
The study of spin glasses originated from experimental studies of the magnetic properties of impure metallic alloys, but soon the study of the theoretical models outshone the interest in the experimental systems. The model studied in this thesis is that of Ising spins with random interactions. In this thesis we discuss two analytical derivations on spin glasses: the famous replica trick on the Sherrington-Kirkpatrick model and the cavity method on a Bethe lattice spin glass.
Computational complexity theory is a branch of theoretical computer science that studies how the running time of algorithms scales with the size of the input. Two important classes of algorithms or problems are P and NP, or colloquially easy and hard problems. The first problem to be proven to belong to the class of NP-complete problems is that of boolean satisfiability, i.e., the study of whether there is an assignment of variables for a random boolean formula so that the formula is satisfied. The boolean satisfiability problem can be tackled with spin glass theory; the cavity method can be applied to it.
Boolean satisfiability exhibits a phase transition. As one increases the ratio of constraints to variables the probability of a random formula being satisfiable drops from unity to zero. This transition of random formulas from satisfiable to unsatisfiable is continuous for small formulas. It grows sharper with increasing problem size and becomes discrete at the limit of an infinite number of variables. The cavity method gives a value for the location of the phase transition that is in agreement with the numerical value.
The cavity method is an analytical tool for studying average values over a distribution, but it introduces so called surveys that can also be calculated numerically for a single instance. These surveys inspire the survey propagation algorithm that is implemented as a numerical program to efficiently solve large instances of random boolean satisfiability problems.
In this thesis I present a parallel version of survey propagation that achieves a speedup by a factor of 3 with 4 processors. With the improved version we are able to gain further knowledge on the detailed workings of survey propagation. It is found, firstly, that the number of iterations needed for one convergence of survey propagation depends on the number of variables, seemingly as ln(N). Secondly, it is found that the constraint to variable ratio for which survey propagation succeeds is dependent on the number of variables.
