Landscape of solutions in constraint satisfaction problems

Abstract

We present a theoretical framework for characterizing the geometrical properties of the space of solutions in constraint satisfaction problems, together with practical algorithms for studying this structure on particular instances. We apply our method to the coloring problem, for which we obtain the total number of solutions and analyze in detail the distribution of distances between solutions.

4 pages, 4 figures. Replaced with published version

References in corpus (10)

• The Bethe lattice spin glass revisited
• The random K-satisfiability problem: from an analytic solution to an efficient algorithm
• Clustering of solutions in the random satisfiability problem
• Coloring random graphs
• On the nature of the low-temperature phase in discontinuous mean-field spin glasses
• A variational description of the ground state structure in random satisfiability problems
• Polynomial iterative algorithms for coloring and analyzing random graphs
• Threshold values, stability analysis and high-q asymptotics for the coloring problem on random graphs
• The cavity method for large deviations
• Source coding by efficient selection of ground states clusters

Cited by in corpus (31)

• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• Phase Transitions in the Coloring of Random Graphs
• A Landscape Analysis of Constraint Satisfaction Problems
• Clusters of solutions and replica symmetry breaking in random k-satisfiability
• Hiding Quiet Solutions in Random Constraint Satisfaction Problems
• On the freezing of variables in random constraint satisfaction problems
• Entropy landscape and non-Gibbs solutions in constraint satisfaction problems
• Glassy Phase of Optimal Quantum Control
• The Phase Diagram of 1-in-3 Satisfiability Problem
• Potts Glass on Random Graphs
• Geometrical organization of solutions to random linear Boolean equations
• Random subcubes as a toy model for constraint satisfaction problems
• Threshold Saturation in Spatially Coupled Constraint Satisfaction Problems
• Statistical Mechanics of maximal independent sets
• From one solution of a 3-satisfiability formula to a solution cluster: Frozen variables and entropy
• Statistical mechanics of error exponents for error-correcting codes
• Communities of solutions in single solution clusters of a random K-Satisfiability formula
• Ground-State Entropy of the Random Vertex-Cover Problem
• $T\to 0$ mean-field population dynamics approach for the random 3-satisfiability problem
• Phase Transitions and Computational Difficulty in Random Constraint Satisfaction Problems
• Minimizing Unsatisfaction in Colourful Neighbourhoods
• Glassy Behavior and Jamming of a Random Walk Process for Sequentially Satisfying a Constraint Satisfaction Formula
• Toward a Theory of Phase Transitions in Quantum Control Landscapes
• Circular Coloring of Random Graphs: Statistical Physics Investigation
• Clustering of solutions in hard satisfiability problems
• Theory of simple glasses
• Counting and Hardness-of-Finding Fixed Points in Cellular Automata on Random Graphs
• The network source location problem: ground state energy, entropy and effects of freezing
• Barriers and local minima in energy landscapes of stochastic local search
• Order-to-chaos transition in the hardness of random Boolean satisfiability problems
• Far-from-equilibrium complex landscapes