title: 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 (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.
authors.affiliation: University of Southern California, Laboratory for Molecular Science, Los Angeles, CA 90089-1340, USA.
authors.forename: Ravinderjit S
authors.initials: RS
authors.lastname: Braich
authors.forename: Nickolas
authors.initials: N
authors.lastname: Chelyapov
authors.forename: Cliff
authors.initials: C
authors.lastname: Johnson
authors.forename: Paul W K
authors.initials: PW
authors.lastname: Rothemund
authors.forename: Leonard
authors.initials: L
authors.lastname: Adleman
mesh_terms: 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
chemical_list: D004277:DNA, Single-Stranded; D015345:Oligonucleotide Probes; D004247:DNA