Statistical mechanics of the random K-SAT model

Abstract

The Random K-Satisfiability Problem, consisting in verifying the existence of an assignment of N Boolean variables that satisfy a set of M=alpha N random logical clauses containing K variables each, is studied using the replica symmetric framework of diluted disordered systems. We present an exact iterative scheme for the replica symmetric functional order parameter together for the different cases of interest K=2, K>= 3 and K>>1. The calculation of the number of solutions, which allowed us [Phys. Rev. Lett. 76, 3881 (1996)] to predict a first order jump at the threshold where the Boolean expressions become unsatisfiable with probability one, is thoroughly displayed. In the case K=2, the (rigorously known) critical value (alpha=1) of the number of clauses per Boolean variable is recovered while for K>=3 we show that the system exhibits a replica symmetry breaking transition. The annealed approximation is proven to be exact for large K.

34 pages + 1 table + 8 fig., submitted to Phys. Rev. E, new section added and references updated

References in corpus (1)

• The Entropy of the K-Satisfiability Problem

Cited by in corpus (94)

• The random K-satisfiability problem: from an analytic solution to an efficient algorithm
• Clustering of solutions in the random satisfiability problem
• The number of guards needed by a museum: A phase transition in vertex covering of random graphs
• The Scaling Window of the 2-SAT Transition
• Asymptotic Analysis of MAP Estimation via the Replica Method and Applications to Compressed Sensing
• Phase Transition in the Number Partitioning Problem
• A Landscape Analysis of Constraint Satisfaction Problems
• Optimisation problems and replica symmetry breaking in finite connectivity spin-glasses
• Clusters of solutions and replica symmetry breaking in random k-satisfiability
• Simplest random K-satisfiability problem
• The Quantum Adiabatic Algorithm applied to random optimization problems: the quantum spin glass perspective
• Polynomial iterative algorithms for coloring and analyzing random graphs
• Exact solutions for diluted spin glasses and optimization problems
• Hiding solutions in random satisfiability problems: A statistical mechanics approach
• First-order transitions and the performance of quantum algorithms in random optimization problems
• Trajectories in phase diagrams, growth processes and computational complexity: how search algorithms solve the 3-Satisfiability problem
• Replica bounds for diluted non-Poissonian spin systems
• Entropies of complex networks with hierarchically constrained topologies
• Minimal vertex covers on finite-connectivity random graphs - a hard-sphere lattice-gas picture
• On the path integral representation for quantum spin models and its application to the quantum cavity method and to Monte Carlo simulations
• Extreme Value Statistics and Traveling Fronts: An Application to Computer Science
• Entropy landscape and non-Gibbs solutions in constraint satisfaction problems
• Tricritical Points in Random Combinatorics: the (2+p)-SAT case
• On the cavity method for decimated random constraint satisfaction problems and the analysis of belief propagation guided decimation algorithms
• Glassy Phase of Optimal Quantum Control
• Finite Connectivity Attractor Neural Networks
• The high temperature region of the Viana-Bray diluted spin glass model
• Parallel dynamics of disordered Ising spin systems on finitely connected random graphs
• Relaxation and Metastability in the RandomWalkSAT search procedure
• Pairs of SAT Assignment in Random Boolean Formulae
• Solving satisfiability problems by fluctuations: The dynamics of stochastic local search algorithms
• Typical solution time for a vertex-covering algorithm on finite-connectivity random graphs
• Phase coexistence and finite-size scaling in random combinatorial problems
• Relaxation in graph coloring and satisfiability problems
• Can rare SAT formulas be easily recognized? On the efficiency of message passing algorithms for K-SAT at large clause-to-variable ratios
• Finitely connected vector spin systems with random matrix interactions
• Random Graph Coloring - a Statistical Physics Approach
• Statistical mechanics of the vertex-cover problem
• The 3-SAT problem with large number of clauses in $\infty$-replica symmetry breaking scheme
• Parallel dynamics of disordered Ising spin systems on finitely connected directed random graphs with arbitrary degree distributions
• The Little-Hopfield model on a Random Graph
• Cavity approach for real variables on diluted graphs and application to synchronization in small-world lattices
• Time scale separation and heterogeneous off-equilibrium dynamics in spin models over random graphs
• Clustering analysis of the ground-state structure of the vertex-cover problem
• Ground state of the Bethe-lattice spin glass and running time of an exact optimization algorithm
• A solvable model of quantum random optimization problems
• Generating dense packings of hard spheres by soft interaction design
• The influence of memory in deterministic walks in random media: analytical calculation within a mean field approximation
• Mapping between Spin-Glass Three-Dimensional (3D) Ising Model and Boolean Satisfiability Problem
• Signature of the Ground-State Topology in the Low-Temperature Dynamics of Spin Glasses
• Statistical Mechanics of an NP-complete Problem: Subset Sum
• Spin models on random graphs with controlled topologies beyond degree constraints
• Bicoloring Random Hypergraphs
• Quantum Adiabatic Algorithm and Large Spin Tunnelling
• Long range frustration in finite connectivity spin glasses: A mean field theory and its application to the random $K$-satisfiability problem
• $T\to 0$ mean-field population dynamics approach for the random 3-satisfiability problem
• Statistical physics of hard combinatorial optimization: The vertex cover problem
• Weight space structure and analysis using a finite replica number in the Ising perceptron
• The random 2-SAT partition function
• Quantum adiabatic optimization and combinatorial landscapes
• Cluster expansions in dilute systems: applications to satisfiability problems and spin glasses
• Criticality and Universality in the Unit-Propagation Search Rule
• Fermionic SK-models with Hubbard interaction: Magnetism and electronic structure
• Minimizing Unsatisfaction in Colourful Neighbourhoods
• Grand canonical ensembles of sparse networks and Bayesian inference
• Toward a Theory of Phase Transitions in Quantum Control Landscapes
• Spin glass phase transitions in the random feedback vertex set problem
• Geometrical Frustration and Cluster Spin Glass with Random Graphs
• Improved Pseudolikelihood Regularization and Decimation methods on Non-linearly Interacting Systems with Continuous Variables
• Statistical physics of exchangeable sparse simple networks, multiplex networks and simplicial complexes
• Belief propagation on networks with cliques and chordless cycles
• Locating phase transitions in computationally hard problems
• Maximally flexible solutions of a random $K$-satisfiability formula
• Plastic number and possible optimal solutions for an Euclidean 2-matching in one dimension
• Statistical Mechanics of the Quantum K-Satisfiability problem
• Inverse problem for multi-body interaction of nonlinear waves
• Numerical renormalization of glassy dynamics
• Slowly evolving random graphs II: Adaptive geometry in finite-connectivity Hopfield models
• A constrained TAP approach for disordered spin models: application to the mixed spherical case
• Effect of Constraint Relaxation on the Minimum Vertex Cover Problem in Random Graphs
• The effect of quantum fluctuations on the coloring of random graphs
• Biased random satisfiability problems: From easy to hard instances
• Multiple transitions in an infinite range p-spin random-crystal field Blume Capel model
• On the behaviour of random K-SAT on trees
• Network Meta-Analysis: A Statistical Physics Perspective
• Free energy of a diluted spin glass model with quadratic Hamiltonian
• Replica Symmetry and Replica Symmetry Breaking for the Traveling Salesperson Problem
• Spanning Trees in Random Satisfiability Problems
• Polynomial Observables in the Graph Partitioning Problem
• Phase transitions in integer linear problems
• Constructing Concrete Hard Instances of the Maximum Independent Set Problem
• The discrete random energy model and one step replica symmetry breaking
• Calculation of 1RSB transition temperature of spin glass models on regular random graphs under the replica symmetric ansatz
• Blume-Emery-Griffiths model on Random Graphs