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

Corresponding author: Dónall A. Mac Dónaill ( dmcdonll@tcd.ie )

© Dónall A. Mac Dónaill.
This article is freely available under the J.UCS Open Content License.
Citation: Dónaill DAM (1996) On the Scalability of Molecular Computational Solutions to NP Problems. JUCS - Journal of Universal Computer Science 2(2): 87-95. https://doi.org/10.3217/jucs-002-02-0087
Open Access
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
Molecular Computation, DNA, NP-problem