Approximate analysis of search algorithms with "physical" methods
arXiv:cs/0302003
Abstract
An overview of some methods of statistical physics applied to the analysis of algorithms for optimization problems (satisfiability of Boolean constraints, vertex cover of graphs, decoding, ...) with distributions of random inputs is proposed. Two types of algorithms are analyzed: complete procedures with backtracking (Davis-Putnam-Loveland-Logeman algorithm) and incomplete, local search procedures (gradient descent, random walksat, ...). The study of complete algorithms makes use of physical concepts such as phase transitions, dynamical renormalization flow, growth processes, ... As for local search procedures, the connection between computational complexity and the structure of the cost function landscape is questioned, with emphasis on the notion of metastability.
28 pages, 23 figures
References in corpus (22)
- The structural glass transition and the entropy of the metastable states
- 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
- Phase Transition in the Number Partitioning Problem
- Rigorous decimation-based construction of ground pure states for spin glass models on random lattices
- A variational description of the ground state structure in random satisfiability problems
- Freezing in Ising Ferromagnets
- Simplest random K-satisfiability problem
- Core percolation in random graphs: a critical phenomena analysis
- Dynamics of glassy systems
- Trajectories in phase diagrams, growth processes and computational complexity: how search algorithms solve the 3-Satisfiability problem
- The Dynamic Phase Transition for Decoding Algorithms
- Minimal vertex covers on finite-connectivity random graphs - a hard-sphere lattice-gas picture
- Extreme Value Statistics and Traveling Fronts: An Application to Computer Science
- Typical solution time for a vertex-covering algorithm on finite-connectivity random graphs
- Relaxation in graph coloring and satisfiability problems
- Jamming Model for the Extremal Optimization Heuristic
- Freezing in random graph ferromagnets
- 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
- Some remarks on the survey decimation algorithm for K-satisfiability
- Cluster expansions in dilute systems: applications to satisfiability problems and spin glasses