Entropy landscape and non-Gibbs solutions in constraint satisfaction problems

Details Entropy landscape and non-Gibbs solutions in constraint satisfaction problems Entropy landscape and non-Gibbs solutions in constraint satisfaction problems

2008-01-18

arxiv.org/abs/0801.2890v1

Phys. Rev. E 77, 031118 (2008)

Physics

Condensed Matter

Statistical Mechanics

38 pages, 10 figures

Scientific paper

10.1103/PhysRevE.77.031118

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.

Affiliated with

Also associated with

No associations

Rating

Entropy landscape and non-Gibbs solutions in constraint satisfaction problems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Entropy landscape and non-Gibbs solutions in constraint satisfaction problems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Entropy landscape and non-Gibbs solutions in constraint satisfaction problems will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-691248