Exhaustive enumeration unveils clustering and freezing in random 3-SAT

Abstract

We study geometrical properties of the complete set of solutions of the random 3-satisfiability problem. We show that even for moderate system sizes the number of clusters corresponds surprisingly well with the theoretic asymptotic prediction. We locate the freezing transition in the space of solutions which has been conjectured to be relevant in explaining the onset of computational hardness in random constraint satisfaction problems.

4 pages, 3 figures

References in corpus (15)

• 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
• Phase Transitions in the Coloring of Random Graphs
• Clustering of solutions in the random satisfiability problem
• A Landscape Analysis of Constraint Satisfaction Problems
• A variational description of the ground state structure in random satisfiability problems
• Clusters of solutions and replica symmetry breaking in random k-satisfiability
• Instability of one-step replica-symmetry-broken phase in satisfiability problems
• On the freezing of variables in random constraint satisfaction problems
• Entropy landscape and non-Gibbs solutions in constraint satisfaction problems
• Behavior of heuristics and state space structure near SAT/UNSAT transition
• Survey-propagation decimation through distributed local computations
• Phase coexistence and finite-size scaling in random combinatorial problems
• On the critical exponents of random k-SAT

Cited by in corpus (23)

• A better algorithm for random k-SAT
• Constraint satisfaction problems with isolated solutions are hard
• The backtracking survey propagation algorithm for solving random K-SAT problems
• Following Gibbs States Adiabatically - The Energy Landscape of Mean Field Glassy Systems
• The large deviations of the whitening process in random constraint satisfaction problems
• From one solution of a 3-satisfiability formula to a solution cluster: Frozen variables and entropy
• Energy landscapes of combinatorial optimization in Ising machines
• Communities of solutions in single solution clusters of a random K-Satisfiability formula
• Numerical Solution-Space Analysis of Satisfiability Problems
• Weight space structure and analysis using a finite replica number in the Ising perceptron
• On belief propagation guided decimation for random k-SAT
• Phase Transitions of the Typical Algorithmic Complexity of the Random Satisfiability Problem Studied with Linear Programming
• Ground-state configuration space heterogeneity of random finite-connectivity spin glasses and random constraint satisfaction problems
• Glassy Behavior and Jamming of a Random Walk Process for Sequentially Satisfying a Constraint Satisfaction Formula
• Learning by random walks in the weight space of the Ising perceptron
• Random Constraint Satisfaction Problems
• Combined local search strategy for learning in networks of binary synapses
• Understanding the computational difficulty of a binary-weight perceptron and the advantage of input sparseness
• Cutting-Plane Algorithms and Solution Whitening for the Vertex-Cover Problem
• Solution space heterogeneity of the random K-satisfiability problem: Theory and simulations
• Order-to-chaos transition in the hardness of random Boolean satisfiability problems
• Algorithmic thresholds in combinatorial optimization depend on the time scaling
• Complete Realization of Energy Landscape and Non-equilibrium Trapping Dynamics in Spin Glass and Optimization Problem