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

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

2000-09-26

arxiv.org/abs/cond-mat/0009410v1

Physics

Condensed Matter

Disordered Systems and Neural Networks

Revtex file + 4 eps figures

Scientific paper

10.1103/PhysRevLett.86.1654

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.

Affiliated with

Also associated with

No associations

Rating

Trajectories in phase diagrams, growth processes and computational complexity: how search algorithms solve the 3-Satisfiability problem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Trajectories in phase diagrams, growth processes and computational complexity: how search algorithms solve the 3-Satisfiability problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Trajectories in phase diagrams, growth processes and computational complexity: how search algorithms solve the 3-Satisfiability problem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-631461