Phase Transitions and Computational Difficulty in Random Constraint Satisfaction Problems

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.

• Publication year

  2007

• Venue

  arXiv.org

• Publication date

  2007-11-01

• Fields of study

  Mathematics, Physics, Computer Science

• Identifiers
  DOI 10.1088/1742-6596/95/1/012012arXiv 0711.0110
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Potts glass on random graphs

  2007influential reference
• A Landscape Analysis of Constraint Satisfaction Problems

  2007cited by this paper
• Phase Transitions in the Coloring of Random Graphs

  2007cited by this paper
• Solving Constraint Satisfaction Problems through Belief Propagation-guided decimation

  2007influential reference
• On the Freezing of Variables in Random Constraint Satisfaction Problems

  2007influential reference
• Behavior of heuristics on large and hard satisfiability problems.

  2006cited by this paper
• Gibbs states and the set of solutions of random constraint satisfaction problems

  2006cited by this paper
• Clustering of solutions in the random satisfiability problem

  2005cited by this paper
• Survey-propagation decimation through distributed local computations

  2005cited by this paper
• Reconstruction on Trees and Spin Glass Transition

  2005cited by this paper
• On the rigidity of amorphous solids

  2005cited by this paper
• On the Dynamics of the Glass Transition on Bethe Lattices

  2005cited by this paper
• Rigorous location of phase transitions in hard optimization problems

  2005cited by this paper
• Landscape of solutions in constraint satisfaction problems

  2005cited by this paper
• Threshold values, stability analysis and high-q asymptotics for the coloring problem on random graphs

  2004cited by this paper
• Instability of one-step replica-symmetry-broken phase in satisfiability problems

  2003cited by this paper
• Exploring artificial intelligence in the new millennium

  2003cited by this paper
• Jamming at zero temperature and zero applied stress: the epitome of disorder.

  2003cited by this paper
• Polynomial iterative algorithms for coloring and analyzing random graphs.

  2003cited by this paper
• Replica Bounds for Optimization Problems and Diluted Spin Systems

  2002cited by this paper
• Coloring random graphs

  2002cited by this paper
• Random graph coloring: statistical physics approach.

  2002cited by this paper
• Analytic and Algorithmic Solution of Random Satisfiability Problems

  2002cited by this paper
• Random K-satisfiability problem: from an analytic solution to an efficient algorithm.

  2002cited by this paper
• Uniqueness of uniform random colorings of regular trees

  2002cited by this paper
• The 3-SAT problem with large number of clauses in the ∞-replica symmetry breaking scheme

  2001cited by this paper
• The Bethe lattice spin glass revisited

  2000cited by this paper
• THE EUROPEAN PHYSICAL JOURNAL B c○ EDP Sciences

  2000cited by this paper
• The K-SAT Problem in a Simple Limit

  2000cited by this paper
• Determining computational complexity from characteristic ‘phase transitions’

  1999cited by this paper
• A Sharp Threshold for k-Colorability

  1999cited by this paper
• Sharp thresholds of graph properties, and the -sat problem

  1999cited by this paper
• Nonlinear dynamics: Jamming is not just cool any more

  1998cited by this paper
• Thermodynamics of glasses: a first principles computation

  1998cited by this paper
• Critical Behavior in the Computational Cost of Satisfiability Testing

  1996cited by this paper
• NUCLEAR PHYSICS B

  1994cited by this paper
• The chromatic number of random graphs

  1991cited by this paper
• Probabilistic reasoning in intelligent systems: Networks of plausible inference

  1991cited by this paper
• Scaling concepts for the dynamics of viscous liquids near an ideal glassy state.

  1989cited by this paper
• Graph optimisation problems and the Potts glass

  1987cited by this paper
• Spin Glass Theory and Beyond

  1987influential reference
• Mean-field theory of the Potts glass.

  1985cited by this paper
• Spin glasses with p-spin interactions

  1985cited by this paper

• Harnessing Computational Complexity Theory to Model Human Decision-making and Cognition

  2023cites this paper
• Boolean constraint satisfaction problems for reaction networks

  2019cites this paper
• Enhanced Multiple-Point Statistical Simulation with Backtracking, Forward Checking and Conflict-Directed Backjumping

  2019cites this paper
• Biased landscapes for random constraint satisfaction problems

  2018cites this paper
• The difficulty of folding self-folding origami

  2018influential citation
• The Complexity of Folding Self-Folding Origami

  2017influential citation
• Constructing SAT Filters with a Quantum Annealer

  2015cites this paper
• Symmetry and Collective Fluctuations in Evolutionary Games

  2015cites this paper
• Difficulty Rating of Sudoku Puzzles: An Overview and Evaluation

  2014influential citation
• Function simulation, graph grammars and colourings

  2013cites this paper
• Boolean constraint satisfaction problems for reaction networks

  2013cites this paper
• Mean-field disordered systems : glasses and optimization problems, classical and quantum

  2013cites this paper
• Entropy landscape of solutions in the binary perceptron problem

  2013cites this paper
• Asymmetric Continuous-Time Neural Networks without Local Traps for Solving Constraint Satisfaction Problems

  2013cites this paper
• Statistical Mechanical Formulation and Simulation of Prime Factorization of Integers

  2013cites this paper
• Physical Models in Community Detection with Applications to Identifying Structure in Complex Amorphous Systems

  2010cites this paper
• Phase transitions in random Potts systems and the community detection problem: spin-glass type and dynamic perspectives

  2010cites this paper
• On state space structure and average case complexity in random K-SAT problems

  2008cites this paper
• Statistical Physics of Hard Optimization Problems

  2008cites this paper