Entropy landscape and non-Gibbs solutions in constraint satisfaction problems

Abstract

We study the entropy landscape of solutions for the bicoloring problem in random graphs, a representative difficult constraint satisfaction problem. Our goal is to classify which type of clusters of solutions are addressed by different algorithms. In the first part of the study we use the cavity method to obtain the number of clusters with a given internal entropy and determine the phase diagram of the problem, e.g. dynamical, rigidity and SAT-UNSAT transitions. In the second part of the paper we analyze different algorithms and locate their behavior in the entropy landscape of the problem. For instance we show that a smoothed version of a decimation strategy based on Belief Propagation is able to find solutions belonging to sub-dominant clusters even beyond the so called rigidity transition where the thermodynamically relevant clusters become frozen. These non-equilibrium solutions belong to the most probable unfrozen clusters.

38 pages, 10 figures

References in corpus (5)

• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• A Landscape Analysis of Constraint Satisfaction Problems
• Efficient supervised learning in networks with binary synapses
• On the freezing of variables in random constraint satisfaction problems
• Statistical mechanics of combinatorial auctions

Cited by in corpus (5)

• Hiding Quiet Solutions in Random Constraint Satisfaction Problems
• 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