A theory of non-equilibrium local search on random satisfaction problems

Abstract

We study local search algorithms to solve instances of the random $k$-satisfiabi lity problem, equivalent to finding (if they exist) zero-energy ground states of statistical models with disorder on random hypergraphs. It is well known that the best such algorithms are akin to non-equilibrium processes in a high-dimensional space. In particular, algorithms known as focused, and which do not obey detailed balance, outperform simulated annealing and related methods in the task of finding the solution to a complex satisfiability problem, that is to find (exactly or approximately) the minimum in a complex energy landscape. A physical question of interest is if the dynamics of these processes can be well predicted by the well-developed theory of equilibrium Gibbs states. While it has been known empirically for some time that this is not the case, an alternative systematic theory that does so has been lacking. In this paper we introduce such a theory based on the recently developed technique of cavity master equations and test it on the paradigmatic random $3$-satisfiability problem. Our theory predicts the solution process very accurately away from the algorithm phase boundary and also predicts the qualitative form of this boundary.

4 pages + Supp. Material

References in corpus (23)

• Stochastic thermodynamics, fluctuation theorems, and molecular machines
• Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications
• Gibbs States and the Set of Solutions of Random Constraint Satisfaction Problems
• Fluctuation Theorems
• Coloring random graphs
• Quantum versus Classical Annealing of Ising Spin Glasses
• Unreasonable Effectiveness of Learning Neural Networks: From Accessible States and Robust Ensembles to Basic Algorithmic Schemes
• Glassy Chimeras could be blind to quantum speedup: Designing better benchmarks for quantum annealing machines
• Nonstoquastic Hamiltonians and Quantum Annealing of an Ising Spin Glass
• Focused Local Search for Random 3-Satisfiability
• Exponential Speedup of Quantum Annealing by Inhomogeneous Driving of the Transverse Field
• Circumspect descent prevails in solving random constraint satisfaction problems
• Behavior of heuristics and state space structure near SAT/UNSAT transition
• The backtracking survey propagation algorithm for solving random K-SAT problems
• Majority dynamics on trees and the dynamic cavity method
• Solving satisfiability problems by fluctuations: The dynamics of stochastic local search algorithms
• Approximation schemes for the dynamics of diluted spin models: the Ising ferromagnet on a Bethe lattice
• Constrained quantum annealing of graph coloring
• Biased landscapes for random Constraint Satisfaction Problems
• A Cavity Master Equation for the continuous time dynamics of discrete spins models
• Ground-State Entropy of the Random Vertex-Cover Problem
• A matrix product algorithm for stochastic dynamics on networks, applied to non-equilibrium Glauber dynamics
• Exploring the diluted ferromagnetic p-spin model with a Cavity Master Equation

Cited by in corpus (5)

• The Cavity Master Equation: average and fixed point of the ferromagnetic model in random graphs
• A closure for the Master Equation starting from the Dynamic Cavity Method
• Biased thermodynamics can explain the behaviour of smart optimization algorithms that work above the dynamical threshold
• Nonequilibrium steady-state dynamics of Markov processes on graphs
• From random point processes to hierarchical Cavity Master Equations for the stochastic dynamics of disordered systems in Random Graphs: Ising models and epidemics