A variational description of the ground state structure in random satisfiability problems

Abstract

A variational approach to finite connectivity spin-glass-like models is developed and applied to describe the structure of optimal solutions in random satisfiability problems. Our variational scheme accurately reproduces the known replica symmetric results and also allows for the inclusion of replica symmetry breaking effects. For the 3-SAT problem, we find two transitions as the ratio $\alpha$ of logical clauses per Boolean variables increases. At the first one ${\alpha }_s\simeq 3.96$, a non-trivial organization of the solution space in geometrically separated clusters emerges. The multiplicity of these clusters as well as the typical distances between different solutions are calculated. At the second threshold ${\alpha }_c\simeq 4.48$, satisfying assignments disappear and a finite fraction $B_0\simeq 0.13$ of variables are overconstrained and take the same values in all optimal (though unsatisfying) assignments. These values have to be compared to ${\alpha }_c\simeq 4.27,B_0\simeq 0.4$ obtained from numerical experiments on small instances. Within the present variational approach, the SAT-UNSAT transition naturally appears as a mixture of a first and a second order transition. For the mixed $2+p$-SAT with $p<2/5$, the behavior is as expected much simpler: a unique smooth transition from SAT to UNSAT takes place at ${\alpha }_c=1/(1-p)$.

24 pages, 6 eps figures, to be published in Europ. Phys. J. B

Cited by in corpus (85)

• 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
• Anderson localization casts clouds over adiabatic quantum optimization
• The number of guards needed by a museum: A phase transition in vertex covering of random graphs
• Survey propagation: an algorithm for satisfiability
• Self-Organization and the Physics of Glassy Networks
• A Landscape Analysis of Constraint Satisfaction Problems
• Rigorous decimation-based construction of ground pure states for spin glass models on random lattices
• The number of matchings in random graphs
• Clusters of solutions and replica symmetry breaking in random k-satisfiability
• A ferromagnet with a glass transition
• Simplest random K-satisfiability problem
• Instability of one-step replica-symmetry-broken phase in satisfiability problems
• The Quantum Adiabatic Algorithm applied to random optimization problems: the quantum spin glass perspective
• Exact solutions for diluted spin glasses and optimization problems
• On the freezing of variables in random constraint satisfaction problems
• Hiding solutions in random satisfiability problems: A statistical mechanics approach
• Solving Constraint Satisfaction Problems through Belief Propagation-guided decimation
• The Dynamic Phase Transition for Decoding Algorithms
• Minimal vertex covers on finite-connectivity random graphs - a hard-sphere lattice-gas picture
• Landscape of solutions in constraint satisfaction problems
• On the cavity method for decimated random constraint satisfaction problems and the analysis of belief propagation guided decimation algorithms
• On quantum mean-field models and their quantum annealing
• Perspective: Gardner Physics in Amorphous Solids and Beyond
• Lossy data compression with random gates
• Relaxation and Metastability in the RandomWalkSAT search procedure
• Locked constraint satisfaction problems
• Constraint satisfaction problems with isolated solutions are hard
• Quantum annealing: the fastest route to quantum computation?
• Solving satisfiability problems by fluctuations: The dynamics of stochastic local search algorithms
• The Phase Diagram of 1-in-3 Satisfiability Problem
• Phase coexistence and finite-size scaling in random combinatorial problems
• Quantum algorithm for energy matching in hard optimization problems
• Can rare SAT formulas be easily recognized? On the efficiency of message passing algorithms for K-SAT at large clause-to-variable ratios
• Reducing Frustration in Spin Systems: Social Balance as an XOR-SAT problem
• Random subcubes as a toy model for constraint satisfaction problems
• Exhaustive enumeration unveils clustering and freezing in random 3-SAT
• Statistical mechanics of the vertex-cover problem
• The 3-SAT problem with large number of clauses in $\infty$-replica symmetry breaking scheme
• Approximation schemes for the dynamics of diluted spin models: the Ising ferromagnet on a Bethe lattice
• Entropy landscape of solutions in the binary perceptron problem
• Statistical Mechanics of the Hyper Vertex Cover Problem
• Minimizing energy below the glass thresholds
• Clustering analysis of the ground-state structure of the vertex-cover problem
• On random graphs and the statistical mechanics of granular matter
• Biased landscapes for random Constraint Satisfaction Problems
• Generating dense packings of hard spheres by soft interaction design
• Glassy dynamics in granular compaction: sand on random graphs
• Phase transitions in the $q$-coloring of random hypergraphs
• From one solution of a 3-satisfiability formula to a solution cluster: Frozen variables and entropy
• The large deviations of the whitening process in random constraint satisfaction problems
• Mapping between Spin-Glass Three-Dimensional (3D) Ising Model and Boolean Satisfiability Problem
• Bicoloring Random Hypergraphs
• Communities of solutions in single solution clusters of a random K-Satisfiability formula
• Approximate analysis of search algorithms with "physical" methods
• Numerical Solution-Space Analysis of Satisfiability Problems
• Discrete energy landscapes and replica symmetry breaking at zero temperature
• Some remarks on the survey decimation algorithm for K-satisfiability
• The Peculiar Phase Structure of Random Graph Bisection
• Phase Transitions and Computational Difficulty in Random Constraint Satisfaction Problems
• Cluster expansions in dilute systems: applications to satisfiability problems and spin glasses
• Source coding by efficient selection of ground states clusters
• Solution-space structure of (some) optimization 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
• On the survey-propagation equations for the random K-satisfiability problem
• The asymptotics of the clustering transition for random constraint satisfaction problems
• Clustering of solutions in hard satisfiability problems
• Statistical mechanics methods and phase transitions in optimization problems
• Relationship between clustering and algorithmic phase transitions in the random k-XORSAT model and its NP-complete extensions
• Counting and Hardness-of-Finding Fixed Points in Cellular Automata on Random Graphs
• Biased measures for random Constraint Satisfaction Problems: larger interaction range and asymptotic expansion
• Susceptibility Propagation for Constraint Satisfaction Problems
• Effect of Constraint Relaxation on the Minimum Vertex Cover Problem in Random Graphs
• A simple one dimensional glassy Kac model
• Optimization and Physics: On the satisfiability of random Boolean formulae
• A journey into localization, integrability and thermalization
• Calculation of 1RSB transition temperature of spin glass models on regular random graphs under the replica symmetric ansatz
• Finite-size scaling in random $K$-satisfiability problems
• Percolation on fitness landscapes: effects of correlation, phenotype, and incompatibilities
• Splitting pairs and the number of clusters generated by random pair incompatibilities
• Interacting Copies of Random Constraint Satisfaction Problems
• On the probabilistic approach to the random satisfiability problem
• A Phase Transition and Stochastic Domination in Pippenger's Probabilistic Failure Model for Boolean Networks with Unreliable Gates