Relaxation and Metastability in the RandomWalkSAT search procedure
arXiv:cond-mat/0301272 · doi:10.1103/PhysRevE.67.066103
Abstract
An analysis of the average properties of a local search resolution procedure for the satisfaction of random Boolean constraints is presented. Depending on the ratio alpha of constraints per variable, resolution takes a time T_res growing linearly (T_res \sim tau(alpha) N, alpha < alpha_d) or exponentially (T_res \sim exp(N zeta(alpha)), alpha > alpha_d) with the size N of the instance. The relaxation time tau(alpha) in the linear phase is calculated through a systematic expansion scheme based on a quantum formulation of the evolution operator. For alpha > alpha_d, the system is trapped in some metastable state, and resolution occurs from escape from this state through crossing of a large barrier. An annealed calculation of the height zeta(alpha) of this barrier is proposed. The polynomial/exponentiel cross-over alpha_d is not related to the onset of clustering among solutions.
23 pages, 11 figures. A mistake in sec. IV.B has been corrected
References in corpus (7)
- The random K-satisfiability problem: from an analytic solution to an efficient algorithm
- Coloring random graphs
- Rigorous decimation-based construction of ground pure states for spin glass models on random lattices
- Typical random 3-SAT formulae and the satisfiability threshold
- Dynamics of glassy systems
- Solving satisfiability problems by fluctuations: The dynamics of stochastic local search algorithms
- Alternative solutions to diluted p-spin models and XORSAT problems
Cited by in corpus (35)
- Mean field theory of hard sphere glasses and jamming
- Differential equation approximations for Markov chains
- 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
- Solving satisfiability problems by fluctuations: The dynamics of stochastic local search algorithms
- 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
- Biased landscapes for random Constraint Satisfaction Problems
- The large deviations of the whitening process in random constraint satisfaction problems
- Aging dynamics of heterogeneous spin models
- Quantum adiabatic optimization and combinatorial landscapes
- A hard-sphere model on generalized Bethe lattices: Statics
- Learning by random walks in the weight space of the Ising perceptron
- Combined local search strategy for learning in networks of binary synapses
- Universal Non-Landau, Self-Organized, Lattice Disordering Percolative Dopant Network Sub-Tc Phase Transitions in Ceramic Superconductors
- Clustering of solutions in hard satisfiability problems
- Perturbative large deviation analysis of non-equilibrium dynamics
- Solving Satisfiability Problems by the Ground-State Quantum Computer
- Quantum Algorithm to Solve 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
- Self-planting: digging holes in rough landscapes
- Two Combinatorial Models with identical Statics yet different Dynamics
- Percolation of satisfiability in finite dimensions
- Dissipative quantum disordered models
- Finite-size scaling in random -satisfiability problems
- From random point processes to hierarchical Cavity Master Equations for the stochastic dynamics of disordered systems in Random Graphs: Ising models and epidemics
- Interactive Particle Systems on Hypergraphs, Drift Analysis and the WalkSAT algorithm
- On the dynamics of Social Balance on general networks (with an application to XOR-SAT)