Phase Transitions and Computational Difficulty in Random Constraint Satisfaction Problems

Abstract

We review the understanding of the random constraint satisfaction problems, focusing on the q-coloring of large random graphs, that has been achieved using the cavity method of the physicists. We also discuss the properties of the phase diagram in temperature, the connections with the glass transition phenomenology in physics, and the related algorithmic issues.

10 pages, Proceedings of the International Workshop on Statistical-Mechanical Informatics 2007, Kyoto (Japan) September 16-19, 2007

References in corpus (21)

• Jamming at Zero Temperature and Zero Applied Stress: the Epitome of Disorder
• The Bethe lattice spin glass revisited
• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• The random K-satisfiability problem: from an analytic solution to an efficient algorithm
• Thermodynamics of glasses: a first principle computation
• On the Rigidity of Amorphous Solids
• Phase Transitions in the Coloring of Random Graphs
• Clustering of solutions in the random satisfiability problem
• Coloring random graphs
• A Landscape Analysis of Constraint Satisfaction Problems
• Reconstruction on trees and spin glass transition
• A variational description of the ground state structure in random satisfiability problems
• Instability of one-step replica-symmetry-broken phase in satisfiability problems
• Polynomial iterative algorithms for coloring and analyzing random graphs
• On the dynamics of the glass transition on Bethe lattices
• Landscape of solutions in constraint satisfaction problems
• Behavior of heuristics and state space structure near SAT/UNSAT transition
• Survey-propagation decimation through distributed local computations
• Threshold values, stability analysis and high-q asymptotics for the coloring problem on random graphs
• Random Graph Coloring - a Statistical Physics Approach
• The 3-SAT problem with large number of clauses in $\infty$-replica symmetry breaking scheme

Cited by in corpus (7)

• Phase transitions in random Potts systems and the community detection problem: spin-glass type and dynamic perspectives
• Entropy landscape of solutions in the binary perceptron problem
• Biased landscapes for random Constraint Satisfaction Problems
• From one solution of a 3-satisfiability formula to a solution cluster: Frozen variables and entropy
• The difficulty of folding self-folding origami
• The stability to instability transition in the structure of large scale networks
• Statistical Mechanical Formulation and Simulation of Prime Factorization of Integers