The random K-satisfiability problem: from an analytic solution to an efficient algorithm

Abstract

We study the problem of satisfiability of randomly chosen clauses, each with K Boolean variables. Using the cavity method at zero temperature, we find the phase diagram for the K=3 case. We show the existence of an intermediate phase in the satisfiable region, where the proliferation of metastable states is at the origin of the slowdown of search algorithms. The fundamental order parameter introduced in the cavity method, which consists of surveys of local magnetic fields in the various possible states of the system, can be computed for one given sample. These surveys can be used to invent new types of algorithms for solving hard combinatorial optimizations problems. One such algorithm is shown here for the 3-sat problem, with very good performances.

38 pages, 13 figures; corrected typos

References in corpus (4)

• Rigorous decimation-based construction of ground pure states for spin glass models on random lattices
• Typical random 3-SAT formulae and the satisfiability threshold
• The cavity method at zero temperature
• Alternative solutions to diluted p-spin models and XORSAT problems

Cited by in corpus (195)

• Critical phenomena in complex networks
• Phase Transitions in the Coloring of Random Graphs
• Towards Understanding and Harnessing the Potential of Clause Learning
• Clustering of solutions in the random satisfiability problem
• Coloring random graphs
• Survey propagation: an algorithm for satisfiability
• Loop series for discrete statistical models on graphs
• A Landscape Analysis of Constraint Satisfaction Problems
• The number of matchings in random graphs
• Cluster Variation Method in Statistical Physics and Probabilistic Graphical Models
• Learning by message-passing in networks of discrete synapses
• Survey Propagation as local equilibrium equations
• Clusters of solutions and replica symmetry breaking in random k-satisfiability
• Hiding Quiet Solutions in Random Constraint Satisfaction Problems
• 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
• Efficient supervised learning in networks with binary synapses
• Polynomial iterative algorithms for coloring and analyzing random graphs
• Optimization by Quantum Annealing: Lessons from hard 3-SAT cases
• Modern computational studies of the glass transition
• On the freezing of variables in random constraint satisfaction problems
• Replica bounds for diluted non-Poissonian spin systems
• Training A Quantum Optimizer
• Focused Local Search for Random 3-Satisfiability
• Solving Constraint Satisfaction Problems through Belief Propagation-guided decimation
• On adaptability and "intermediate phase" in randomly connected networks
• Inducing Effect on the Percolation Transition in Complex Networks
• Landscape of solutions in constraint satisfaction problems
• Cavity method for quantum spin glasses on the Bethe lattice
• Entropy landscape and non-Gibbs solutions in constraint satisfaction problems
• On the cavity method for decimated random constraint satisfaction problems and the analysis of belief propagation guided decimation algorithms
• Behavior of heuristics and state space structure near SAT/UNSAT transition
• Survey-propagation decimation through distributed local computations
• Threshold values, stability analysis and high-q asymptotics for the coloring problem on random graphs
• Message passing for vertex covers
• Lossy data compression with random gates
• Local entropy as a measure for sampling solutions in Constraint Satisfaction Problems
• Relaxation and Metastability in the RandomWalkSAT search procedure
• Locked constraint satisfaction problems
• Constraint satisfaction problems with isolated solutions are hard
• The backtracking survey propagation algorithm for solving random K-SAT problems
• Phase transitions in semisupervised clustering of sparse networks
• Pairs of SAT Assignment in Random Boolean Formulae
• Solving satisfiability problems by fluctuations: The dynamics of stochastic local search algorithms
• Networking - A Statistical Physics Perspective
• The Phase Diagram of 1-in-3 Satisfiability Problem
• Improved message passing for inference in densely connected systems
• On the exactness of the cavity method for Weighted b-Matchings on Arbitrary Graphs and its Relation to Linear Programs
• Community detection in networks with unequal groups
• Quantum algorithm for energy matching in hard optimization problems
• Minimal contagious sets in random regular graphs
• Long Range Frustrations in a Spin Glass Model of the Vertex Cover Problem
• Potts Glass on Random Graphs
• Effective optimization using sample persistence: A case study on quantum annealers and various Monte Carlo optimization methods
• Random multi-index matching problems
• Geometrical organization of solutions to random linear Boolean equations
• On the number of circuits in random graphs
• Spintronics-compatible approach to solving maximum satisfiability problems with probabilistic computing, invertible logic and parallel tempering
• The property of kappa-deformed statistics for a relativistic gas in an electromagnetic field: kappa parameter and kappa-distribution
• Random subcubes as a toy model for constraint satisfaction problems
• The Competition for Shortest Paths on Sparse Graphs
• Finite-Connectivity Spin-Glass Phase Diagrams and Low Density Parity Check Codes
• Exhaustive enumeration unveils clustering and freezing in random 3-SAT
• Threshold Saturation in Spatially Coupled Constraint Satisfaction Problems
• Statistical Mechanics of maximal independent sets
• TASI lectures on complex structures
• The hard-core model on random graphs revisited
• Relaxed Survey Propagation for The Weighted Maximum Satisfiability Problem
• Minimizing energy below the glass thresholds
• Statistical Mechanics of the Hyper Vertex Cover Problem
• Clustering analysis of the ground-state structure of the vertex-cover problem
• Replica Cluster Variational Method
• Decentralized Constraint Satisfaction
• The stochastic matching problem
• Near optimal configurations in mean field disordered systems
• Stability analysis on the finite-temperature replica-symmetric and first-step replica-symmetry-broken cavity solutions of the random vertex cover problem
• Comparing Beliefs, Surveys and Random Walks
• Intrinsic limitations of inverse inference in the pairwise Ising spin glass
• Hiding Satisfying Assignments: Two are Better than One
• Inference and Optimization of Real Edges on Sparse Graphs - A Statistical Physics Perspective
• From one solution of a 3-satisfiability formula to a solution cluster: Frozen variables and entropy
• A Cavity Master Equation for the continuous time dynamics of discrete spins models
• A rigorous proof of the cavity method for counting matchings
• Finding long cycles in graphs
• Mapping between Spin-Glass Three-Dimensional (3D) Ising Model and Boolean Satisfiability Problem
• Aging dynamics of heterogeneous spin models
• Assessing and Advancing the Potential of Quantum Computing: A NASA Case Study
• Replica Cluster Variational Method: the Replica Symmetric solution for the 2D random bond Ising model
• Bicoloring Random Hypergraphs
• Von Neumann's expanding model on random graphs
• Characterizing and Improving Generalized Belief Propagation Algorithms on the 2D Edwards-Anderson Model
• Stochastic optimization by message passing
• The cavity method for large deviations
• Exactly solvable models of adaptive networks
• Long range frustration in finite connectivity spin glasses: A mean field theory and its application to the random $K$-satisfiability problem
• Approximate analysis of search algorithms with "physical" methods
• Statistical physics of hard combinatorial optimization: The vertex cover problem
• $T\to 0$ mean-field population dynamics approach for the random 3-satisfiability problem
• The theoretical capacity of the Parity Source Coder
• Numerical Solution-Space Analysis of Satisfiability Problems
• Tap Complexity, the Cavity Method and Supersymmetry
• Phase transition for cutting-plane approach to vertex-cover problem
• Grover-QAOA for 3-SAT: Quadratic Speedup, Fair-Sampling, and Parameter Clustering
• A hard-sphere model on generalized Bethe lattices: Statics
• Replicated Bethe Free Energy: A Variational Principle behind Survey Propagation
• Solution space structure of random constraint satisfaction problems with growing domains
• A very fast inference algorithm for finite-dimensional spin glasses: Belief Propagation on the dual lattice
• Some spin glass ideas applied to the clique problem
• Zero temperature solutions of the Edwards-Anderson model in random Husimi Lattices
• The Peculiar Phase Structure of Random Graph Bisection
• A matrix product algorithm for stochastic dynamics on networks, applied to non-equilibrium Glauber dynamics
• Phase Transitions and Computational Difficulty in Random Constraint Satisfaction Problems
• Message passing and Monte Carlo algorithms: connecting fixed points with metastable states
• Phase Transitions of the Typical Algorithmic Complexity of the Random Satisfiability Problem Studied with Linear Programming
• Source coding by efficient selection of ground states clusters
• Good speciation and endogenous business cycles in a constraint satisfaction macroeconomic model
• Properties of atypical graphs from negative complexities
• Glassy Behavior and Jamming of a Random Walk Process for Sequentially Satisfying a Constraint Satisfaction Formula
• Metastable configurations on the Bethe lattice
• Ground-state configuration space heterogeneity of random finite-connectivity spin glasses and random constraint satisfaction problems
• Fast inference of ill-posed problems within a convex space
• Multi-body quenched disordered $XY$ and $p$-clock models on random graphs
• Statistical mechanics of budget-constrained auctions
• Solution-space structure of (some) optimization problems
• Survey propagation at finite temperature: application to a Sourlas code as a toy model
• Minimal Dominating Set problem studied by simulated annealing and cavity method: Analytics and population dynamics
• Optimal control of a quantum sensor: A fast algorithm based on an analytic solution
• Fluctuations in the random-link matching problem
• Scaling Analysis of Affinity Propagation
• Cavity approach to the Sourlas code system
• Satisfiability, sequence niches, and molecular codes in cellular signaling
• Optimal Resource Allocation in Random Networks with Transportation Bandwidths
• Spin glass phase transitions in the random feedback vertex set problem
• The matrix product approximation for the dynamic cavity method
• Statistical mechanics of combinatorial auctions
• Optimal Location of Sources in Transportation Networks
• Constraint optimization and landscapes
• Maximally flexible solutions of a random $K$-satisfiability formula
• Classification and sparse-signature extraction from gene-expression data
• Clustering of solutions in hard satisfiability problems
• Statistical-mechanical iterative algorithms on complex networks
• Coordinating Dynamical Routes with Statistical Physics on Space-time Networks
• Statistical Physics of Group Testing
• A spin glass approach to the directed feedback vertex set problem
• Low-temperature excitations within the Bethe approximation
• The Ising spin glass on random graphs at zero temperature: not all spins are glassy in the glassy phase
• Counting and Hardness-of-Finding Fixed Points in Cellular Automata on Random Graphs
• Adversarial Satisfiability Problem
• Coverage versus Supply Cost in Facility Location: Physics of Frustrated Spin Systems
• Statistical Mechanics of the Quantum K-Satisfiability problem
• Long-range frustration in T=0 first-step replica-symmetry-broken solutions of finite-connectivity spin glasses
• Boltzmann distribution of free energies in a finite-connectivity spin-glass system and the cavity approach
• Susceptibility Propagation for Constraint Satisfaction Problems
• Thermodynamics of the Fredrickson-Andersen Model on the Bethe Lattice
• Cavity approach to sphere packing in Hamming space
• Bethe free-energy approximations for disordered quantum systems
• Inference by replication in densely connected systems
• Quantum Cluster Variational Method and Message Passing Algorithms Revisited
• What makes a phase transition? Analysis of the random satisfiability problem
• The solution space structure of planted constraint satisfaction problems with growing domains
• Cutting-Plane Algorithms and Solution Whitening for the Vertex-Cover Problem
• Biased random satisfiability problems: From easy to hard instances
• On the behaviour of random K-SAT on trees
• Asymptotic Exceptional Steady States in Dissipative Dynamics
• A high-performance analog Max-SAT solver and its application to Ramsey numbers
• Survey propagation for the cascading Sourlas code
• Spanning Trees in Random Satisfiability Problems
• Statistical physics of loopy interactions: Independent-loop approximation and beyond
• Optimally coordinated traffic diversion by statistical physics
• Optimization and Physics: On the satisfiability of random Boolean formulae
• Decimation flows in constraint satisfaction problems
• Biased thermodynamics can explain the behaviour of smart optimization algorithms that work above the dynamical threshold
• Finite-size scaling in random $K$-satisfiability problems
• Multilayer wave functions: A recursive coupling of local excitations
• Retrieving information from a noisy "knowledge network"
• Complex Cooperative Behaviour in Range-free Frustrated Many-body Systems
• Constructing Concrete Hard Instances of the Maximum Independent Set Problem
• On one-step replica symmetry breaking in the Edwards-Anderson spin glass model
• Fluctuation Distributions of Energy Minima in Complex Landscapes
• Approaching the ground states of the random maximum two-satisfiability problem by a greedy single-spin flipping process
• Energy Spectrum and Exact Cover in an Extended Quantum Ising Model
• Quantum Adiabatic Evolution Algorithm and Quantum Phase Transition in 3-Satisfiability Problem
• It's Quick to be Square: Fast Quadratisation for Quantum Toolchains
• Algorithmic thresholds in combinatorial optimization depend on the time scaling
• The large-scale logico-chemical structure of a transcriptional regulation network
• Witness of unsatisfiability for a random 3-satisfiability formula
• Statistical mechanics of optimization problems
• The closest vector problem and the zero-temperature p-spin landscape for lossy compression
• Simplifying Random Satisfiability Problem by Removing Frustrating Interactions
• A Model of Random Industrial SAT
• Efficient Digital Quadratic Unconstrained Binary Optimization Solvers for SAT Problems
• The replica symmetric solution for Orthogonally Constrained Heisenberg Model on Bethe lattice
• Complete Realization of Energy Landscape and Non-equilibrium Trapping Dynamics in Spin Glass and Optimization Problem
• Low Auto-correlation Binary Sequences explored using Warning Propagation
• The Directed Dominating Set problem studied by cavity method: Warning propagation and population dynamics