doi: 10.1126/science.1069528.
Epub 2002 Mar 14.
Solution of a 20-variable 3-SAT problem on a DNA computer
Affiliations
- PMID: 11896237
- DOI: 10.1126/science.1069528
Item in Clipboard
Solution of a 20-variable 3-SAT problem on a DNA computer
Science.
.
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 (2(20)) 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.
Comment in
-
Computing. Successes and challenges.Science. 2002 Apr 19;296(5567):478-9. doi: 10.1126/science.1070978. Science. 2002. PMID: 11964464 No abstract available.
Similar articles
-
DNA computing on surfaces.Nature. 2000 Jan 13;403(6766):175-9. doi: 10.1038/35003155. Nature. 2000. PMID: 10646598
-
DNA computing using single-molecule hybridization detection.Nucleic Acids Res. 2004 Sep 23;32(17):4962-8. doi: 10.1093/nar/gkh817. Print 2004. Nucleic Acids Res. 2004. PMID: 15388798 Free PMC article.
-
A DNA computing readout operation based on structure-specific cleavage.Nat Biotechnol. 2001 Nov;19(11):1053-9. doi: 10.1038/nbt1101-1053. Nat Biotechnol. 2001. PMID: 11689851
-
Single nucleotide polymorphism genotyping using locked nucleic acid (LNA).Expert Rev Mol Diagn. 2003 Jan;3(1):27-38. doi: 10.1586/14737159.3.1.27. Expert Rev Mol Diagn. 2003. PMID: 12528362 Review.
-
The past, present and future of molecular computing.Nat Rev Mol Cell Biol. 2000 Oct;1(1):69-72. doi: 10.1038/35036086. Nat Rev Mol Cell Biol. 2000. PMID: 11413491 Review.
Cited by
-
Thermodynamically based DNA strand design.Nucleic Acids Res. 2005 Sep 6;33(15):4951-64. doi: 10.1093/nar/gki773. Print 2005. Nucleic Acids Res. 2005. PMID: 16145053 Free PMC article.
-
One-Electron Oxidation Potentials and Hole Delocalization in Heterogeneous Single-Stranded DNA.Biochemistry. 2023 Nov 21;62(22):3312-3322. doi: 10.1021/acs.biochem.3c00324. Epub 2023 Nov 3. Biochemistry. 2023. PMID: 37923303 Free PMC article.
-
Production of random DNA oligomers for scalable DNA computing.Biotechnol J. 2009 Jan;4(1):119-28. doi: 10.1002/biot.200800224. Biotechnol J. 2009. PMID: 19156734 Free PMC article.
-
Paradigms for computational nucleic acid design.Nucleic Acids Res. 2004 Feb 27;32(4):1392-403. doi: 10.1093/nar/gkh291. Print 2004. Nucleic Acids Res. 2004. PMID: 14990744 Free PMC article.
-
A Label-Free Fluorescent DNA Machine for Sensitive Cyclic Amplification Detection of ATP.Materials (Basel). 2018 Nov 29;11(12):2408. doi: 10.3390/ma11122408. Materials (Basel). 2018. PMID: 30501020 Free PMC article.
Publication types
MeSH terms
Substances
LinkOut - more resources
Full Text Sources
Other Literature Sources
Research Materials
Miscellaneous
