Research Article

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

+ See all 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

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.

View Full Text