On the freezing of variables in random constraint satisfaction problems

Abstract

The set of solutions of random constraint satisfaction problems (zero energy groundstates of mean-field diluted spin glasses) undergoes several structural phase transitions as the amount of constraints is increased. This set first breaks down into a large number of well separated clusters. At the freezing transition, which is in general distinct from the clustering one, some variables (spins) take the same value in all solutions of a given cluster. In this paper we study the critical behavior around the freezing transition, which appears in the unfrozen phase as the divergence of the sizes of the rearrangements induced in response to the modification of a variable. The formalism is developed on generic constraint satisfaction problems and applied in particular to the random satisfiability of boolean formulas and to the coloring of random graphs. The computation is first performed in random tree ensembles, for which we underline a connection with percolation models and with the reconstruction problem of information theory. The validity of these results for the original random ensembles is then discussed in the framework of the cavity method.

32 pages, 7 figures

References in corpus (4)

• Broken Replica Symmetry Bounds in the Mean Field Spin Glass Model
• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• Clustering of solutions in the random satisfiability problem
• Threshold values, stability analysis and high-q asymptotics for the coloring problem on random graphs

Cited by in corpus (13)

• Jamming versus Glass Transitions
• Clusters of solutions and replica symmetry breaking in random k-satisfiability
• Hiding Quiet Solutions in Random Constraint Satisfaction Problems
• Critical scaling and heterogeneous superdiffusion across the jamming/rigidity transition of a granular glass
• Circumspect descent prevails in solving random constraint satisfaction problems
• Entropy landscape and non-Gibbs solutions in constraint satisfaction problems
• Constraint satisfaction problems with isolated solutions are hard
• Reconstruction of Random Colourings
• Identifying essential genes in E. coli from a metabolic optimization principle
• Random subcubes as a toy model for constraint satisfaction problems
• 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
• Reconstruction of symmetric Potts Models