Optimization problems and replica symmetry breaking in finite connectivity spin glasses

A formalism capable of handling the first step of hierarchical replica symmetry breaking (RSB) in finite-connectivity models is introduced. The emerging order parameter is claimed to be a probability distribution over the space of field distributions (or, equivalently magnetization distributions) inside the cluster of states. The approach is shown to coincide with previous works in the replica-symmetric case and in the two limiting cases m = 0 and 1 where m is Parisi's break point. As an application to the study of optimization problems, the GS properties of the random 3-satisfiability problem are investigated and we present a first RSB solution improving replica-symmetric results.