Solving satisfiability problems by fluctuations: The dynamics of stochastic local search algorithms

Details Solving satisfiability problems by fluctuations: The dynamics of stochastic local search algorithms Solving satisfiability problems by fluctuations: The dynamics of stochastic local search algorithms

2003-01-15

arxiv.org/abs/cond-mat/0301271v2

Phys. Rev. E 67, 066104 (2003)

Physics

Condensed Matter

Statistical Mechanics

21 pages, 18 figures, revised version, to app. in PRE (2003)

Scientific paper

10.1103/PhysRevE.67.066104

Stochastic local search algorithms are frequently used to numerically solve hard combinatorial optimization or decision problems. We give numerical and approximate analytical descriptions of the dynamics of such algorithms applied to random satisfiability problems. We find two different dynamical regimes, depending on the number of constraints per variable: For low constraintness, the problems are solved efficiently, i.e. in linear time. For higher constraintness, the solution times become exponential. We observe that the dynamical behavior is characterized by a fast equilibration and fluctuations around this equilibrium. If the algorithm runs long enough, an exponentially rare fluctuation towards a solution appears.

Affiliated with

Also associated with

No associations

Rating

Solving satisfiability problems by fluctuations: The dynamics of stochastic local search algorithms 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 Solving satisfiability problems by fluctuations: The dynamics of stochastic local search algorithms, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Solving satisfiability problems by fluctuations: The dynamics of stochastic local search algorithms will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-497742