Solution of a 20-variable 3-SAT problem on a DNA computer.
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.
Braich
Ravinderjit S
RS
University of Southern California, Laboratory for Molecular Science, Los Angeles, CA 90089-1340, USA.
Chelyapov
Nickolas
N
Johnson
Cliff
C
Rothemund
Paul W K
PW
Adleman
Leonard
L
D020029:Base Pairing; D001483:Base Sequence; D003201:Computers; D003205:Computing Methodologies; D004247:DNA; D004277:DNA, Single-Stranded; D004591:Electrophoresis, Polyacrylamide Gel; D015723:Gene Library; D009693:Nucleic Acid Hybridization; D015345:Oligonucleotide Probes; D016133:Polymerase Chain Reaction
D004277:DNA, Single-Stranded; D015345:Oligonucleotide Probes; D004247:DNA