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

Area of Science:

• Statistical physics
• Theoretical computer science
• Network science

Background:

• The bicoloring problem in random graphs is a complex constraint satisfaction problem.
• Understanding the structure of solution spaces is crucial for algorithm design.

Purpose of the Study:

• To classify solution clusters in random graph bicoloring.
• To map algorithm behavior onto the problem's entropy landscape.
• To identify which solution clusters are targeted by different algorithms.

Main Methods:

• Cavity method to determine the number and entropy of solution clusters.
• Analysis of phase transitions (dynamical, rigidity, SAT-UNSAT).
• Evaluation of algorithms, including a smoothed decimation strategy based on belief propagation.

Main Results:

• The study determines the phase diagram of the bicoloring problem.
• It identifies that a smoothed belief propagation strategy can access subdominant solution clusters.
• This algorithm finds solutions beyond the rigidity transition, in previously inaccessible clusters.

Conclusions:

• The entropy landscape provides a framework for understanding algorithm performance in constraint satisfaction problems.
• Specific algorithms, like smoothed belief propagation, can overcome limitations imposed by thermodynamic transitions.
• Non-equilibrium solutions in subdominant clusters are accessible even when dominant clusters freeze.