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

Solution of a 20-variable 3-SAT problem on a DNA computer.

Ravinderjit S Braich1, Nickolas Chelyapov, Cliff Johnson

  • 1University of Southern California, Laboratory for Molecular Science, Los Angeles, CA 90089-1340, USA.

Science (New York, N.Y.)
|March 16, 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

Author Correction: Modular RNA motifs for orthogonal phase separated compartments.

Nature communications·2025
Same author

Modular DNA origami-based electrochemical detection of DNA and proteins.

Proceedings of the National Academy of Sciences of the United States of America·2025
Same author

Modular RNA motifs for orthogonal phase separated compartments.

Nature communications·2024
Same author

Co-transcriptional production of programmable RNA condensates and synthetic organelles.

Nature nanotechnology·2024
Same author

Digital nanoreactors to control absolute stoichiometry and spatiotemporal behavior of DNA receptors within lipid bilayers.

Nature communications·2023
Same author

Autologous NK cells propagated and activated <i>ex vivo</i> decrease senescence markers in human PBMCs.

Biochemistry and biophysics reports·2022
Same journal

A native sulfur deposit in Gale crater, Mars.

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

Coordinated demise of harmful algal blooms.

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

Genetic effects put into context.

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

Bacteria share proteins to survive antibiotics.

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

Impacts shaped Earth's first continents.

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

Erratum for the Report "Covalently bonded single-molecule junctions with stable and reversible photoswitched conductivity" by C. Jia <i>et al</i>.

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

Researchers solved a complex 20-variable problem using a DNA computer, exploring over a million possibilities. This demonstrates a significant advancement in solving large computational problems with biological means.

Area of Science:

  • Biocomputing
  • Computational Complexity Theory
  • Molecular Computing

Background:

  • The three-satisfiability (3-SAT) problem is a fundamental NP-complete problem in computer science.
  • Solving large instances of 3-SAT is computationally challenging for traditional electronic computers.

Purpose of the Study:

  • To demonstrate the capability of a simple DNA computer for solving complex computational problems.
  • To investigate the feasibility of using biological molecules for large-scale computation.

Main Methods:

  • A 20-variable instance of the 3-SAT problem was encoded and solved using a DNA-based computational approach.
  • The DNA computer performed an exhaustive search of over 1 million (2^20) possibilities to find the unique solution.

Related Experiment Videos

Main Results:

  • The DNA computer successfully identified the unique solution to the 20-variable 3-SAT problem.
  • This represents one of the largest computational problems solved to date using nonelectronic, biological methods.

Conclusions:

  • DNA computing offers a viable alternative for tackling computationally intensive problems.
  • The scale of this solution suggests potential for DNA computers in addressing problems beyond human or conventional computational limits.