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

2002569 citationsJournal Article

Authors

Paul W. K. Rothemund · California Institute of Technology

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.

Topics & Keywords

DNA and Biological Computing Advanced biosensing and bioanalysis techniques Machine Learning and Algorithms

Publication Details

Published in: Science

Volume 296, Issue 5567, pp. 499-502

DOI: 10.1126/science.1069528

Field-Weighted Citation Impact: 13.01

Command Palette

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

Authors

Abstract

Topics & Keywords

Publication Details