On the computational power of DNA

Authors: D. Boneh, C. Dunworth, R. Lipton, and J. Sgall

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.

In Discrete Applied Mathematics, Special Issue on Computational Molecular Biology, Vol. 71 (1996), pp. 79--94

Full paper: gzipped-PostScript