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

Random K-satisfiability problem: from an analytic solution to an efficient algorithm.

Marc Mézard1, Riccardo Zecchina

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

Physical Review. E, Statistical, Nonlinear, and Soft Matter Physics
|January 7, 2003
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

Sampling the space of solutions of an artificial neural network.

Physical review. E·2025
Same author

Dynamical regimes of diffusion models.

Nature communications·2024
Same author

Exponential Capacity of Dense Associative Memories.

Physical review letters·2024
Same author

Typical and atypical solutions in nonconvex neural networks with discrete and continuous weights.

Physical review. E·2023
Same author

Matrix factorization with neural networks.

Physical review. E·2023
Same author

Learning through atypical phase transitions in overparameterized neural networks.

Physical review. E·2022
Same journal

Tension on dsDNA bound to ssDNA-RecA filaments may play an important role in driving efficient and accurate homology recognition and strand exchange.

Physical review. E, Statistical, nonlinear, and soft matter physics·2016
Same journal

Publisher's Note: Amplitude-phase coupling drives chimera states in globally coupled laser networks [Phys. Rev. E 91, 040901(R) (2015)].

Physical review. E, Statistical, nonlinear, and soft matter physics·2016
Same journal

Erratum: Shapes of sedimenting soft elastic capsules in a viscous fluid [Phys. Rev. E 92, 033003 (2015)].

Physical review. E, Statistical, nonlinear, and soft matter physics·2016
Same journal

Erratum: Attenuation of excitation decay rate due to collective effect [Phys. Rev. E 90, 022142 (2014)].

Physical review. E, Statistical, nonlinear, and soft matter physics·2016
Same journal

Publisher's Note: Role of connectivity and fluctuations in the nucleation of calcium waves in cardiac cells [Phys. Rev. E 92, 052715 (2015)].

Physical review. E, Statistical, nonlinear, and soft matter physics·2016
Same journal

Publisher's Note: Lattice Boltzmann approach for complex nonequilibrium flows [Phys. Rev. E 92, 043308 (2015)].

Physical review. E, Statistical, nonlinear, and soft matter physics·2016
See all related articles

Researchers explored the K=3 Boolean satisfiability problem using the cavity method. They discovered an intermediate phase linked to metastable states, impacting algorithm performance and enabling new problem-solving approaches.

Area of Science:

  • Computational complexity theory
  • Statistical physics applied to computer science
  • Boolean satisfiability problems

Background:

  • The Boolean satisfiability problem (SAT) is a fundamental NP-complete problem.
  • Randomly generated SAT instances can exhibit complex phase transitions.
  • Search algorithms often face performance bottlenecks due to the problem's structure.

Purpose of the Study:

  • To investigate the phase diagram of the K=3 Boolean satisfiability problem.
  • To understand the role of metastable states in algorithm slowdown.
  • To develop novel algorithms for combinatorial optimization problems.

Main Methods:

  • Application of the cavity method at zero temperature.
  • Analysis of the phase diagram for K=3 SAT.

Related Experiment Videos

  • Computation of the fundamental order parameter (local magnetic fields).

    • Main Results:

    • Identification of a distinct intermediate phase within the satisfiable region for K=3 SAT.
    • Demonstration that metastable states contribute to the slowdown of search algorithms.
    • Development of a new algorithm for K=3 SAT based on cavity method insights, showing strong performance.

    Conclusions:

    • The K=3 SAT problem exhibits a complex phase structure with implications for computational complexity.
    • Metastable states are crucial for understanding algorithmic limitations in SAT.
    • The cavity method provides a powerful framework for developing efficient combinatorial optimization algorithms.