Solution of a 20-Variable 3-SAT Problem on a DNA Computer
- 19 April 2002
- journal article
- research article
- Published by American Association for the Advancement of Science (AAAS) in Science
- Vol. 296 (5567), 499-502
- https://doi.org/10.1126/science.1069528
Abstract
A 20-variable instance of the NP-complete three-satisfiability (3-SAT) problem was solved on a simple DNA computer. The unique answer was found after an exhaustive search of more than 1 million (220) possibilities. This computational problem may be the largest yet solved by nonelectronic means. Problems of this size appear to be beyond the normal range of unaided human computation.Keywords
This publication has 20 references indexed in Scilit:
- Programmable and autonomous computing machine made of biomoleculesNature, 2001
- The evolution of cellular computing: nature’s solution to a computational problemBiosystems, 1999
- A Sticker-Based Model for DNA ComputationJournal of Computational Biology, 1998
- Making DNA AddScience, 1996
- Single-step assembly of a gene and entire plasmid from large numbers of oligodeoxyribonucleotidesGene, 1995
- Chlorite-rich ultramafic reaction zones in Colorado Plateau xenoliths: recorders of sub-Moho hydrationContributions to Mineralogy and Petrology, 1995
- DNA Solution of Hard Computational ProblemsScience, 1995
- Building an Associative Memory Vastly Larger Than the BrainScience, 1995
- Molecular Computation of Solutions to Combinatorial ProblemsScience, 1994
- Formal language theory and DNA: An analysis of the generative capacity of specific recombinant behaviorsBulletin of Mathematical Biology, 1987