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

Analytic and algorithmic solution of random satisfiability problems.

M Mézard1, G Parisi, R Zecchina

  • 1Laboratoire de Physique Théorique et Modèles Statistiques, CNRS and Université Paris Sud, Bât. 100, 91405 Orsay Cedex, France.

Science (New York, N.Y.)
|June 29, 2002
PubMed
Summary
This summary is machine-generated.

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

Meat quality of a slow-growing chicken breed fed soybean meal-free diets.

Animal : an international journal of animal bioscience·2026
Same author

Correction: Robotic uterine transposition for fertility preservation in patients undergoing pelvic radiotherapy: a narrative review of surgical evolution, technical strategies, and emerging evidence.

Journal of robotic surgery·2026
Same author

Robotic uterine transposition for fertility preservation in patients undergoing pelvic radiotherapy: a narrative review of surgical evolution, technical strategies, and emerging evidence.

Journal of robotic surgery·2026
Same author

Specific hepatic gene responses to dietary fat levels during the finisher phase in a slow-growing chicken breed.

Poultry science·2025
Same author

Quantifying Memory in Spin Glasses.

Physical review letters·2025
Same author

Aesthetic perception of patient in developmental age in interceptive orthodontic treatment.

European journal of paediatric dentistry·2024
Same journal

Erratum for the Research Article "Detecting supramolecular organic nanoparticles during heat wave".

Science (New York, N.Y.)·2026
Same journal

Local signals, systemic decline.

Science (New York, N.Y.)·2026
Same journal

The mechanics of liver regeneration.

Science (New York, N.Y.)·2026
Same journal

Computing in a memory with physics.

Science (New York, N.Y.)·2026
Same journal

Retraction.

Science (New York, N.Y.)·2026
Same journal

Making time.

Science (New York, N.Y.)·2026
See all related articles

Researchers explored K-satisfiability complexity in random Boolean expressions. They identified an intermediate phase below the satisfiability threshold, characterized by metastable states, and developed new algorithms to address this complexity.

Area of Science:

  • Computer Science
  • Computational Complexity
  • Artificial Intelligence

Background:

  • The K-satisfiability problem is a fundamental challenge in computational complexity.
  • Understanding the phase transition in random Boolean expressions is crucial for algorithm design.

Purpose of the Study:

  • To investigate the onset of complexity in K-satisfiability problems.
  • To identify the role of metastable states in search algorithm performance.
  • To develop novel optimization algorithms for complex satisfiability instances.

Main Methods:

  • Analysis of random Boolean expressions with varying clause-to-variable ratios (alpha).
  • Identification of an intermediate phase below the satisfiability threshold (alphac).
  • Development and testing of a new class of optimization algorithms designed for metastable states.

Related Experiment Videos

Main Results:

  • Established the existence of an intermediate phase below alphac where complexity arises.
  • Demonstrated that metastable states are responsible for increased search difficulty.
  • Successfully tested a novel optimization algorithm on large K-satisfiability benchmarks.

Conclusions:

  • The study reveals a critical intermediate phase in K-satisfiability, impacting algorithm performance.
  • New optimization algorithms show promise in tackling complex, metastable problem instances.
  • Findings contribute to a deeper understanding of computational complexity and satisfiability problems.