Published April 19, 2002
| Supplemental Material
Journal Article
Open
Solution of a 20-Variable 3-SAT Problem on a DNA Computer
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.
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.Attached Files
Supplemental Material - 1069528S1_med.gif
Files
1069528S1_med.gif
Files
(76.3 kB)
| Name | Size | Download all |
|---|---|---|
|
md5:1715ed044ea1deb880a31302ec4e409e
|
76.3 kB | Preview Download |
Additional details
- Eprint ID
- 51922
- Resolver ID
- CaltechAUTHORS:20141118-145557580
- NASA/JPL
- Defense Advanced Research Projects Agency (DARPA)
- Office of Naval Research (ONR)
- NSF
- Created
-
2014-11-18Created from EPrint's datestamp field
- Updated
-
2021-11-10Created from EPrint's last_modified field