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

DNA solution of hard computational problems

R J Lipton1

  • 1Princeton University, NJ 08540, USA.

Science (New York, N.Y.)
|April 28, 1995
PubMed
Summary
This summary is machine-generated.

DNA computing offers a novel approach to solving complex computer science problems like the SAT problem. This method leverages massive parallelism for potential speedups over traditional computers.

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

Fidelity of enzymatic ligation for DNA computing.

Journal of computational biology : a journal of computational molecular cell biology·2001
Same author

Molecular computation: RNA solutions to chess problems.

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

Chess games: a model for RNA based computation.

Bio Systems·2000
Same author

Counting DNA: estimating the complexity of a test tube of DNA.

Bio Systems·2000
Same author

Botulinum toxin injection for adductor spastic dysphonia: patient self-ratings of voice and phonatory effort after three successive injections.

The Laryngoscope·1993
Same author

Noninvasive technique for estimating subglottic pressure and laryngeal efficiency.

The Annals of otology, rhinology, and laryngology·1992
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

Area of Science:

  • Computer Science
  • Biotechnology
  • Computational Complexity

Background:

  • The Satisfiability (SAT) problem is a fundamental challenge in computer science.
  • NP-complete problems represent a class of computationally difficult problems.
  • Conventional electronic computers face limitations in solving large-scale search problems.

Purpose of the Study:

  • To propose DNA-based experiments for solving the SAT problem.
  • To present a general method applicable to NP-complete problems using DNA computing.
  • To explore the potential of DNA computing for accelerating search algorithms.

Main Methods:

  • Utilizing DNA molecules for computation.
  • Exploiting the inherent parallelism of DNA-based systems.

Related Experiment Videos

  • Developing experimental protocols for DNA-based problem-solving.

    • Main Results:

    • Demonstration of a DNA-based approach to tackle the SAT problem.
    • Identification of a generalizable method for solving NP-complete problems.
    • Highlighting the significant parallel processing capabilities of DNA computing.

    Conclusions:

    • DNA computing presents a promising avenue for solving computationally intensive problems.
    • The inherent parallelism in DNA offers substantial speedup potential compared to electronic computers.
    • This research opens new possibilities for DNA-based solutions in computer science.