Quick links

On The Computational Power of DNA

Report ID:
September 1995
Download Formats:


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.
Follow us: Facebook Twitter Linkedin