JUCS - Journal of Universal Computer Science 2(2): 87-95, doi: 10.3217/jucs-002-02-0087
On the Scalability of Molecular Computational Solutions to NP Problems
expand article infoDónall A. Mac Dónaill
‡ Department of Chemistry & Centre for Scientific Computation, Trinity College, University of Dublin, Ireland
Open Access
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
Molecular Computation, DNA, NP-problem