On The Computational Power of DNA

Abstract:

We show how DNA based computers can be used to solve the
satisfiability problem for boolean circuits. Furthermore, we show how
DNA computers can solve optimization problems directly without first
solving several decision problems. Our methods also enable
random sampling of satisfying assignments. Finally we suggest a
procedure for evaluating functions in the polynomial hierarchy.

This technical report will be published as

On The Computational Power of DNA. Dan Boneh, Christopher
Dunworth, Richard J. Lipton and Jiri Sgall,
DAM 1996.