Solving NP-complete problems in the tile assembly model
作者： Yuriy Brun
DOI: 10.1016/J.TCS.2007.07.052
关键词:
摘要: Formalized study of self-assembly has led to the definition tile assembly model, a highly distributed parallel model computation that may be implemented using molecules or large computer network such as Internet. Previously, I defined deterministic and nondeterministic in showed how add, multiply factor. Here, extend notion include deciding subsets natural numbers, present system decides SubsetSum, well-known NP-complete problem. The is each executes time linear input. requires only constant number different types: 49. describe mechanisms for finding successful solutions among many assemblies explore bounds on probability succeeding prove can made arbitrarily close one.
core.ac.uk
acm.org
elsevier.com
sci-hub.se 参考文章(40)
Manoj Gopalkrishnan, Dustin Reishus, Leonard Adleman, Nickolas Chelyapov, Yuriy Brun, Bilal Shaw, Building blocks for DNA self-assembly Proceedings of the 1st Foundations of Nanoscience: Self-Assembled Architectures and Devices (FNANO). ,(2004)
Erik Winfree, On the Computational Power of DNA Annealing and Ligation DNA Based Computers. pp. 199- 221 ,(1996)
Yuliy Baryshnikov, Ed Coffman, Petar Momčilović, DNA-Based Computation Times DNA Computing. ,vol. 3384, pp. 14- 23 ,(2005) , 10.1007/11493785_2
Erik Winfree, Paul W. K. Rothemund, The program-size complexity of self-assembled squares ACM. ,(2000)
Yuliy Baryshnikov, Ed Coffman, Nadrian Seeman, Teddy Yimwadsana, Self-correcting Self-assembly: Growth Models and the Hammersley Process DNA Computing. pp. 1- 11 ,(2006) , 10.1007/11753681_1
Ho-Lin Chen, Ashish Goel, Error Free Self-assembly Using Error Prone Tiles DNA Computing. pp. 62- 75 ,(2005) , 10.1007/11493785_6
Ravinderjit S. Braich, Cliff Johnson, Paul W. K. Rothemund, Darryl Hwang, Nickolas Chelyapov, Leonard M. Adleman, Solution of a Satisfiability Problem on a Gel-Based DNA Computer international workshop on dna based computers. pp. 27- 42 ,(2000) , 10.1007/3-540-44992-2_3
Matthew Cook, Paul W. K. Rothemund, Erik Winfree, Self-Assembled Circuit Patterns international workshop on dna-based computers. pp. 91- 107 ,(2003) , 10.1007/978-3-540-24628-2_11
Erik Winfree, Renat Bekbolatov, Proofreading Tile Sets: Error Correction for Algorithmic Self-Assembly international workshop on dna-based computers. pp. 126- 144 ,(2003) , 10.1007/978-3-540-24628-2_13
Erik Winfree, Self-healing Tile Sets Nanotechnology: Science and Computation. pp. 55- 78 ,(2006) , 10.1007/3-540-30296-4_4