Trajectories in phase diagrams, growth processes and computational complexity: how search algorithms solve the 3-Satisfiability problem

Abstract

Most decision and optimization problems encountered in practice fall into one of two categories with respect to any particular solving method or algorithm: either the problem is solved quickly (easy) or else demands an impractically long computational effort (hard). Recent investigations on model classes of problems have shown that some global parameters, such as the ratio between the constraints to be satisfied and the adjustable variables, are good predictors of problem hardness and, moreover, have an effect analogous to thermodynamical parameters, e.g. temperature, in predicting phases in condensed matter physics [Monasson et al., Nature 400 (1999) 133-137]. Here we show that changes in the values of such parameters can be tracked during a run of the algorithm defining a trajectory through the parameter space. Focusing on 3-Satisfiability, a recognized representative of hard problems, we analyze trajectories generated by search algorithms using growth processes statistical physics. These trajectories can cross well defined phases, corresponding to domains of easy or hard instances, and allow to successfully predict the times of resolution.

Revtex file + 4 eps figures

References in corpus (1)

• Typical solution time for a vertex-covering algorithm on finite-connectivity random graphs

Cited by in corpus (36)

• Phase Transitions in the Coloring of Random Graphs
• Boosting search by rare events
• Typical random 3-SAT formulae and the satisfiability threshold
• 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
• Extremal Optimization at the Phase Transition of the 3-Coloring Problem
• Extreme Value Statistics and Traveling Fronts: An Application to Computer Science
• Behavior of heuristics and state space structure near SAT/UNSAT transition
• Relaxation and Metastability in the RandomWalkSAT search procedure
• Solving satisfiability problems by fluctuations: The dynamics of stochastic local search algorithms
• Typical solution time for a vertex-covering algorithm on finite-connectivity random graphs
• Field theoretic approach to metastability in the contact process
• On the stochastic dynamics of disordered spin models
• Statistical mechanics of the vertex-cover problem
• Jamming Model for the Extremal Optimization Heuristic
• Quantum walk speedup of backtracking algorithms
• Ground state of the Bethe-lattice spin glass and running time of an exact optimization algorithm
• Biased landscapes for random Constraint Satisfaction Problems
• Hiding Satisfying Assignments: Two are Better than One
• The large deviations of the whitening process in random constraint satisfaction problems
• From one solution of a 3-satisfiability formula to a solution cluster: Frozen variables and entropy
• Numerical Solution-Space Analysis of Satisfiability Problems
• $T\to 0$ mean-field population dynamics approach for the random 3-satisfiability problem
• Approximate analysis of search algorithms with "physical" methods
• Phase transition for cutting-plane approach to vertex-cover problem
• Phase Transitions of Traveling Salesperson Problems solved with Linear Programming and Cutting Planes
• 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
• Phase Transitions of the Typical Algorithmic Complexity of the Random Satisfiability Problem Studied with Linear Programming
• The dynamics of proving uncolourability of large random graphs I. Symmetric Colouring Heuristic
• Glassy Behavior and Jamming of a Random Walk Process for Sequentially Satisfying a Constraint Satisfaction Formula
• Statistical mechanics methods and phase transitions in optimization problems
• Slowly evolving random graphs II: Adaptive geometry in finite-connectivity Hopfield models
• Computational Complexity for Physicists
• Statistical Mechanical Formulation and Simulation of Prime Factorization of Integers
• Phase transition in the bipartite z-matching
• Phase transition for parameter learning of Hidden Markov Models