On the computational power of DNA
Authors: D. Boneh, C. Dunworth, R. Lipton, and J. Sgall
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.
Reference:
In Discrete Applied Mathematics, Special Issue on Computational
Molecular Biology, Vol. 71 (1996), pp. 79--94
Full paper: gzipped-PostScript