On the Scalability of Molecular Computational Solutions to NP Problems

Dónall A. Mac Dónaill (Department of Chemistry & Centre for Scientific Computation, Trinity College, University of Dublin, Ireland)

Abstract: A molecular computational procedure in which manipulation of DNA strands may be harnessed to solve a classical problem in NP - the directed Hamiltonian path problem - was recently proposed [Adleman 1994], [Gifford 1994]. The procedure is in effect a massively parallel chemical analog computer and has a computational capacity corresponding to approximately CPU years on a typical 10 MFLOP workstation. In this paper limitations on the potential scalability of molecular computation are considered. A simple analysis of the time complexity function shows that the potential of molecular systems to increase the size of generally solvable problems in NP is fundamentally limited to . Over the chemically measurable picomolar to molar concentration range the greatest practical increase in problem size is limited to

Keywords: DNA, Molecular Computation, NP-problem