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

Biased random satisfiability problems: from easy to hard instances.

A Ramezanpour1, S Moghimi-Araghi

  • 1Institute for Advanced Studies in Basic Sciences, Zanjan 45195-1159, Iran. ramezanpour@iasbs.ac.ir

Physical Review. E, Statistical, Nonlinear, and Soft Matter Physics
|August 11, 2005
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

Statistical physics of principal minors: Cavity approach.

Physical review. E·2024
Same author

Statistical physics of loopy interactions: independent-loop approximation and beyond.

Physical review. E, Statistical, nonlinear, and soft matter physics·2015
Same author

Bethe free-energy approximations for disordered quantum systems.

Physical review. E, Statistical, nonlinear, and soft matter physics·2014
Same author

Computing loop corrections by message passing.

Physical review. E, Statistical, nonlinear, and soft matter physics·2013
Same author

Cavity approach to sphere packing in Hamming space.

Physical review. E, Statistical, nonlinear, and soft matter physics·2012
Same author

Inference and learning in sparse systems with multiple states.

Physical review. E, Statistical, nonlinear, and soft matter physics·2011
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

This study explores biased random K-satisfiability (K-SAT) problems, introducing variable negation probability to understand computational complexity. Results show a discontinuous SAT-UNSAT transition for K=3 at a critical probability, offering insights into problem hardness.

Area of Science:

  • Theoretical Computer Science
  • Statistical Physics

Background:

  • Random K-satisfiability (K-SAT) problems are fundamental in computational complexity.
  • Understanding the phase transition between satisfiable and unsatisfiable instances is crucial.
  • Biased K-SAT, with variable negation probability, offers a tunable model.

Purpose of the Study:

  • To investigate the computational complexity of biased random K-SAT problems.
  • To analyze the impact of variable negation probability on problem hardness.
  • To understand the nature of the satisfiability-unsatisfiability (SAT-UNSAT) transition.

Main Methods:

  • Exact solution for the 1-SAT case.
  • Application of the replica method within the replica symmetry framework.
  • Numerical solution of survey propagation equations for K=3.

Related Experiment Videos

Main Results:

  • Derived critical points and replica method results for biased K-SAT.
  • Found that for small negation probability p, alpha(c) is proportional to p^-(K-1).
  • Identified a critical probability p* ≈ 0.17 for K=3, below which replica symmetry is preserved.

Conclusions:

  • Biased K-SAT provides a bridge between easy and hard problem instances.
  • The SAT-UNSAT transition remains discontinuous below p* for K=3, even without replica symmetry breaking.
  • The study enhances understanding of typical complexity in random K-SAT problems.