Clusters of solutions and replica symmetry breaking in random k-satisfiability

Abstract

We study the set of solutions of random k-satisfiability formulae through the cavity method. It is known that, for an interval of the clause-to-variables ratio, this decomposes into an exponential number of pure states (clusters). We refine substantially this picture by: (i) determining the precise location of the clustering transition; (ii) uncovering a second `condensation' phase transition in the structure of the solution set for k larger or equal than 4. These results both follow from computing the large deviation rate of the internal entropy of pure states. From a technical point of view our main contributions are a simplified version of the cavity formalism for special values of the Parisi replica symmetry breaking parameter m (in particular for m=1 via a correspondence with the tree reconstruction problem) and new large-k expansions.

30 pages, 14 figures, typos corrected, discussion of appendix C expanded with a new figure

References in corpus (7)

• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• Rigorous Inequalities between Length and Time Scales in Glassy Systems
• A Landscape Analysis of Constraint Satisfaction Problems
• Mosaic multi-state scenario vs. one-state description of supercooled liquids
• On the freezing of variables in random constraint satisfaction problems
• Potts Glass on Random Graphs
• Near optimal configurations in mean field disordered systems

Cited by in corpus (7)

• Cavity method for quantum spin glasses on the Bethe lattice
• Locked constraint satisfaction problems
• Constraint satisfaction problems with isolated solutions are hard
• Exhaustive enumeration unveils clustering and freezing in random 3-SAT
• From one solution of a 3-satisfiability formula to a solution cluster: Frozen variables and entropy
• Ground-State Entropy of the Random Vertex-Cover Problem
• $T\to 0$ mean-field population dynamics approach for the random 3-satisfiability problem