Research Article

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

See allHide authors and affiliations

Science  19 Apr 2002:
Vol. 296, Issue 5567, pp. 499-502
DOI: 10.1126/science.1069528

You are currently viewing the abstract.

View Full Text


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.

View Full Text