On The Computational Power of DNA

Report ID: TR-499-95

---

Author: Sgall, Jiri / Boneh, Dan / Lipton, Richard J. / Dunworth, Christopher

---

Date: 1995-10-00

---

Pages: 14

---

Download Formats: |Postscript|

---

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.