Solution of a 20-Variable 3-SAT Problem on a DNA Computer

Braich, Ravinderjit S. and Chelyapov, Nickolas and Johnson, Cliff and Rothemund, Paul W. K. and Adleman, Leonard (2002) Solution of a 20-Variable 3-SAT Problem on a DNA Computer. Science, 296 (5567). pp. 499-502. ISSN 0036-8075. doi:10.1126/science.1069528. https://resolver.caltech.edu/CaltechAUTHORS:20141118-145557580

Preview

Image (GIF) (Fig. 1) - Supplemental Material
See Usage Policy.
76kB

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20141118-145557580

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.

Item Type:

Article

Related URLs:

URL	URL Type	Description
http://www.sciencemag.org/content/296/5567/499.abstract	Publisher	Article
http://dx.doi.org/10.1126/science.1069528	DOI	Article
http://www.sciencemag.org/content/296/5567/499/suppl/DC1	Related Item	Supplementary Material

ORCID:

Author	ORCID
Rothemund, Paul W. K.	0000-0002-1653-3202

Additional Information:

© 2002 American Association for the Advancement of Science. 3 January 2002; accepted 5 March 2002. Published online 14 March 2002; 10.1126/science.1069528. We gratefully acknowledge the contributions of M. Goodman, A. Soltani, D. Hwang, L. Kari, N. Chelyapov Jr., and the members of the Laboratory for Molecular Science. Supported by grants from NASA/Jet Propulsion Laboratory, the Defense Advanced Research Projects Agency, the Office of Naval Research, and NSF.

Funders:

Funding Agency	Grant Number
NASA/JPL	UNSPECIFIED
Defense Advanced Research Projects Agency (DARPA)	UNSPECIFIED
Office of Naval Research (ONR)	UNSPECIFIED
NSF	UNSPECIFIED

Issue or Number:

5567

DOI:

10.1126/science.1069528

Record Number:

CaltechAUTHORS:20141118-145557580

Persistent URL:

https://resolver.caltech.edu/CaltechAUTHORS:20141118-145557580

Official Citation:

Solution of a 20-Variable 3-SAT Problem on a DNA Computer Ravinderjit S. Braich, Nickolas Chelyapov, Cliff Johnson, Paul W. K. Rothemund, and Leonard Adleman Science 19 April 2002: 296 (5567), 499-502.Published online 14 March 2002 [DOI:10.1126/science.1069528]

Usage Policy:

No commercial reproduction, distribution, display or performance rights in this work are provided.

ID Code:

51922

Collection:

CaltechAUTHORS

Deposited By:

Ruth Sustaita

Deposited On:

18 Nov 2014 23:15

Last Modified:

10 Nov 2021 19:17

Repository Staff Only: item control page