Solving satisfiability problems by fluctuations: The dynamics of stochastic local search algorithms

Abstract

Stochastic local search algorithms are frequently used to numerically solve hard combinatorial optimization or decision problems. We give numerical and approximate analytical descriptions of the dynamics of such algorithms applied to random satisfiability problems. We find two different dynamical regimes, depending on the number of constraints per variable: For low constraintness, the problems are solved efficiently, i.e. in linear time. For higher constraintness, the solution times become exponential. We observe that the dynamical behavior is characterized by a fast equilibration and fluctuations around this equilibrium. If the algorithm runs long enough, an exponentially rare fluctuation towards a solution appears.

21 pages, 18 figures, revised version, to app. in PRE (2003)

References in corpus (18)

• The random K-satisfiability problem: from an analytic solution to an efficient algorithm
• The number of guards needed by a museum: A phase transition in vertex covering of random graphs
• Statistical mechanics of the random K-SAT model
• Phase Transition in the Number Partitioning Problem
• Coloring random graphs
• Boosting search by rare events
• A variational description of the ground state structure in random satisfiability problems
• A ferromagnet with a glass transition
• Simplest random K-satisfiability problem
• Random Costs in Combinatorial Optimization
• Trajectories in phase diagrams, growth processes and computational complexity: how search algorithms solve the 3-Satisfiability problem
• Weight Space Structure and Internal Representations: a Direct Approach to Learning and Generalization in Multilayer Neural Network
• Analysis of the computational complexity of solving random satisfiability problems using branch and bound search algorithms
• Minimal vertex covers on finite-connectivity random graphs - a hard-sphere lattice-gas picture
• Relaxation and Metastability in the RandomWalkSAT search procedure
• Typical solution time for a vertex-covering algorithm on finite-connectivity random graphs
• Dynamics of heuristic optimization algorithms on random graphs
• Exponentially hard problems are sometimes polynomial, a large deviation analysis of search algorithms for the random Satisfiability problem, and its application to stop-and-restart resolutions

Cited by in corpus (31)

• Mean field theory of hard sphere glasses and jamming
• Focused Local Search for Random 3-Satisfiability
• Circumspect descent prevails in solving random 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
• On large deviation properties of Erdos-Renyi random graphs
• Relaxation and Metastability in the RandomWalkSAT search procedure
• Field theoretic approach to metastability in the contact process
• Reducing Frustration in Spin Systems: Social Balance as an XOR-SAT problem
• Approximation schemes for the dynamics of diluted spin models: the Ising ferromagnet on a Bethe lattice
• Mechanism for the failure of the Edwards hypothesis in the SK spin glass
• Aging dynamics of heterogeneous spin models
• Quantum adiabatic optimization and combinatorial landscapes
• A hard-sphere model on generalized Bethe lattices: Statics
• A theory of non-equilibrium local search on random satisfaction problems
• Learning by random walks in the weight space of the Ising perceptron
• Solution to Satisfiability problem by a complete Grover search with trapped ions
• Combined local search strategy for learning in networks of binary synapses
• Perturbative large deviation analysis of non-equilibrium dynamics
• Clustering of solutions in hard satisfiability problems
• Critical behaviour of combinatorial search algorithms, and the unitary-propagation universality class
• Entropic barriers as a reason for hardness in both classical and quantum algorithms
• A hard-sphere model on generalised Bethe lattices: Dynamics
• Barriers and local minima in energy landscapes of stochastic local search
• Percolation of satisfiability in finite dimensions
• Two Combinatorial Models with identical Statics yet different Dynamics
• Spanning Trees in Random Satisfiability Problems
• Finite-size scaling in random $K$-satisfiability problems
• On the dynamics of Social Balance on general networks (with an application to XOR-SAT)
• Interactive Particle Systems on Hypergraphs, Drift Analysis and the WalkSAT algorithm
• From random point processes to hierarchical Cavity Master Equations for the stochastic dynamics of disordered systems in Random Graphs: Ising models and epidemics