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

Hiding solutions in random satisfiability problems: a statistical mechanics approach.

W Barthel1, A K Hartmann, M Leone

  • 1Institute for Theoretical Physics, University of Göttingen, Bunsenstrasse 9, 37073 Göttingen, Germany.

Physical Review Letters
|May 15, 2002
PubMed
Summary

This study introduces novel random generators for creating difficult 3-satisfiability problem instances. These generators, based on statistical mechanics, produce hard test cases with known properties for evaluating search algorithms.

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

The PIDDosome controls cardiomyocyte polyploidization during postnatal heart development.

Cell death and differentiation·2026
Same author

Quantifying Memory in Spin Glasses.

Physical review letters·2025
Same author

In and beyond the Griffiths phase: A large-deviation study of the magnetic susceptibility of the two-dimensional bond-diluted Ising model.

Physical review. E·2024
Same author

Author Correction: Understanding epistatic networks in the B1 β-lactamases through coevolutionary statistical modeling and deep mutational scanning.

Nature communications·2024
Same author

Understanding epistatic networks in the B1 β-lactamases through coevolutionary statistical modeling and deep mutational scanning.

Nature communications·2024
Same author

Statistical methods for linking material composition to recombination losses in optoelectronic devices.

The Review of scientific instruments·2024

Area of Science:

  • Computer Science
  • Artificial Intelligence
  • Computational Complexity

Background:

  • Evaluating stochastic local search algorithms for NP-complete problems requires systematic generation of hard test instances.
  • Existing methods lack systematic generation of instances with known properties of optimal solutions.

Purpose of the Study:

  • To propose random generators for hard and satisfiable instances of the 3-satisfiability problem.
  • To leverage statistical mechanics results for designing challenging problem instances.

Main Methods:

  • Utilizing statistical mechanics principles, specifically first-order ferromagnetic phase transitions and the glassy nature of excited states.
  • Developing random instance generators for the 3-satisfiability problem.

Related Experiment Videos

Main Results:

  • Successfully generated hard and satisfiable instances for the 3-satisfiability problem.
  • Analytical predictions regarding instance hardness were corroborated by numerical results.
  • Demonstrated the effectiveness of the proposed generators with both complete and stochastic local algorithms.

Conclusions:

  • The proposed random generators provide a systematic method for creating hard 3-satisfiability instances.
  • This approach aids in the rigorous evaluation of stochastic local search algorithms.
  • The findings are grounded in statistical mechanics and validated through empirical testing.