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

Simplest random K-satisfiability problem.

F Ricci-Tersenghi1, M Weigt, R Zecchina

  • 1The Abdus Salam International Centre for Theoretical Physics, Condensed Matter Group, Strada Costiera 11, P.O. Box 586, I-34100 Trieste, Italy. riccife@ictp.trieste.it

Physical Review. E, Statistical, Nonlinear, and Soft Matter Physics
|April 20, 2001
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

Quantifying Memory in Spin Glasses.

Physical review letters·2025
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

Erratum: Numerical test of the replica-symmetric Hamiltonian for correlations of the critical state of spin glasses in a field [Phys. Rev. E 105, 054106 (2022)].

Physical review. E·2024
Same author

Structure of the space of folding protein sequences defined by large language models.

Physical biology·2024
Same author

Numerical test of the replica-symmetric Hamiltonian for correlations of the critical state of spin glasses in a field.

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

We present a solvable model for random satisfiability problems, offering insights into computational complexity. Our findings reveal structures driving phase transitions and complexity in local search algorithms.

Area of Science:

  • Computational complexity theory
  • Statistical mechanics
  • Satisfiability problems

Background:

  • Random satisfiability problems (RSPs) are crucial in computer science and AI.
  • Many RSPs are computationally intractable for local search algorithms.
  • Understanding the phase transitions and complexity onset in RSPs is a key challenge.

Purpose of the Study:

  • To introduce and analyze a simple, exactly solvable model for generating RSPs.
  • To investigate the statistical properties and underlying structures of these problems.
  • To elucidate the origins of computational complexity in local search methods.

Main Methods:

  • Utilizing the replica method from statistical mechanics for exact analysis.
  • Employing a simple global solution method for polynomial-time instance analysis.

Related Experiment Videos

  • Conducting numerical analysis on large samples to characterize critical scaling behavior.

    • Main Results:

    • The model allows for exact statistical analysis and efficient single-instance solving.
    • Identified geometrical and topological structures responsible for phase transitions.
    • Characterized the onset of computational complexity in local search for these problems.

    Conclusions:

    • The developed model provides a tractable framework for studying complex satisfiability problems.
    • The analysis offers a deeper understanding of phase transitions and computational hardness.
    • This work contributes to the theoretical foundations of satisfiability and algorithm design.