On the Scalability of Molecular Computational Solutions to NP Problems

Простая страница элемента
dc.creatorDónaill,Dónall A. Mac
dc.date1996
dc.date.accessioned2024-02-06T12:48:09Z
dc.date.available2024-02-06T12:48:09Z
dc.descriptionA 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
dc.formattext/html
dc.identifierhttps://doi.org/10.3217/jucs-002-02-0087
dc.identifierhttps://lib.jucs.org/article/27220/
dc.identifier.urihttps://openrepository.mephi.ru/handle/123456789/6925
dc.languageen
dc.publisherJournal of Universal Computer Science
dc.relationinfo:eu-repo/semantics/altIdentifier/eissn/0948-6968
dc.relationinfo:eu-repo/semantics/altIdentifier/pissn/0948-695X
dc.rightsinfo:eu-repo/semantics/openAccess
dc.rightsJ.UCS License
dc.sourceJUCS - Journal of Universal Computer Science 2(2): 87-95
dc.subjectMolecular Computation
dc.subjectDNA
dc.subjectNP-problem
dc.titleOn the Scalability of Molecular Computational Solutions to NP Problems
dc.typeResearch Article
Файлы
Коллекции
Публикации в журналах НИЯУ МИФИ