Jove
Visualize
Contact Us
JoVE
x logofacebook logolinkedin logoyoutube logo
ABOUT JoVE
OverviewLeadershipBlogJoVE Help Center
AUTHORS
Publishing ProcessEditorial BoardScope & PoliciesPeer ReviewFAQSubmit
LIBRARIANS
TestimonialsSubscriptionsAccessResourcesLibrary Advisory BoardFAQ
RESEARCH
JoVE JournalMethods CollectionsJoVE Encyclopedia of ExperimentsArchive
EDUCATION
JoVE CoreJoVE BusinessJoVE Science EducationJoVE Lab ManualFaculty Resource CenterFaculty Site
Terms & Conditions of Use
Privacy Policy
Policies

Related Experiment Videos

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

Wolfgang Barthel1, Alexander K Hartmann, Martin Weigt

  • 1Institut für Theoretische Physik, Universität Göttingen, D-37073 Göttingen, Germany.

Physical Review. E, Statistical, Nonlinear, and Soft Matter Physics
|October 26, 2005
PubMed
Summary

Stochastic local search algorithms efficiently solve random satisfiability problems in linear time when constraintness is low. However, higher constraintness leads to exponential solution times, with rare fluctuations enabling eventual problem resolution.

Related Concept Videos

You might also read

Related Articles

Articles linked to this work by shared authors, journal, and citation graph.

Sort by
Same author

Numerical estimation of limiting large-deviation rate functions.

Physical review. E·2026
Same author

Rare events of host switching for diseases using a susceptible-infected-recovered model with mutations.

Physical review. E·2026
Same author

Author Correction: Exploring the space of self-reproducing ribozymes using generative models.

Nature communications·2025
Same author

adabmDCA 2.0-A Flexible but Easy-to-Use Package for Direct Coupling Analysis.

Methods in molecular biology (Clifton, N.J.)·2025
Same author

Distribution of the Number of Paths in Two-Dimensional Directed Percolation.

Entropy (Basel, Switzerland)·2025
Same author

Diffusion with stochastic resetting on a lattice.

Physical review. E·2025

Area of Science:

  • Computer Science
  • Artificial Intelligence
  • Computational Complexity

Background:

  • Stochastic local search (SLS) algorithms are widely applied to complex combinatorial optimization and decision problems.
  • Understanding the dynamics of SLS algorithms is crucial for predicting their performance on challenging problem instances.

Purpose of the Study:

  • To analyze the dynamics of SLS algorithms applied to random satisfiability (SAT) problems.
  • To identify different dynamical regimes and their dependence on problem characteristics, specifically constraintness.

Main Methods:

  • Numerical simulations of SLS algorithms on random SAT instances.
  • Approximate analytical descriptions of algorithm dynamics.
  • Characterization of dynamical regimes based on constraintness per variable.

Related Experiment Videos

Main Results:

  • Two distinct dynamical regimes were observed: efficient (linear time) solving for low constraintness and exponential time solving for high constraintness.
  • Algorithm dynamics exhibit rapid equilibration followed by fluctuations around an equilibrium point.
  • Solutions are found through exponentially rare fluctuations, particularly when the algorithm runs for extended periods.

Conclusions:

  • The efficiency of SLS algorithms on SAT problems is highly sensitive to the problem's constraintness.
  • The observed dynamics suggest a phase transition in algorithmic performance related to constraintness.
  • Further investigation into rare event dynamics could yield insights into improving SLS algorithm design for hard problems.