Go home now Header Background Image
Submission Procedure
share: |
Follow us
Volume 2 / Issue 2

available in:   HTML (16 kB) PDF (32 kB) PS (194 kB)
Similar Docs BibTeX   Write a comment
Links into Future
DOI:   10.3217/jucs-002-02-0087


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