CaltechAUTHORS
  A Caltech Library Service

Parallel Computation Using Active Self-assembly

Chen, Moya and Xin, Doris and Woods, Damien (2013) Parallel Computation Using Active Self-assembly. In: DNA Computing and Molecular Programming. Lecture Notes in Computer Science. No.8141. Springer International Publishing , Berlin, Germany, pp. 16-30. ISBN 978-3-319-01927-7. http://resolver.caltech.edu/CaltechAUTHORS:20140506-085427393

[img]
Preview
PDF - Submitted Version
See Usage Policy.

2024Kb

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20140506-085427393

Abstract

We study the computational complexity of the recently proposed nubots model of molecular-scale self-assembly. The model generalizes asynchronous cellular automaton to have non-local movement where large assemblies of molecules can be moved around, analogous to millions of molecular motors in animal muscle effecting the rapid movement of large arms and legs. We show that nubots is capable of simulating Boolean circuits of polylogarithmic depth and polynomial size, in only polylogarithmic expected time. In computational complexity terms, any problem from the complexity class NC is solved in polylogarithmic expected time on nubots that use a polynomial amount of workspace. Along the way, we give fast parallel algorithms for a number of problems including line growth, sorting, Boolean matrix multiplication and space-bounded Turing machine simulation, all using a constant number of nubot states (monomer types). Circuit depth is a well-studied notion of parallel time, and our result implies that nubots is a highly parallel model of computation in a formal sense. Thus, adding a movement primitive to an asynchronous non-deterministic cellular automation, as in nubots, drastically increases its parallel processing abilities.


Item Type:Book Section
Related URLs:
URLURL TypeDescription
http://link.springer.com/chapter/10.1007%2F978-3-319-01928-4_2PublisherArticle
http://dx.doi.org/10.1007/978-3-319-01928-4_2DOIArticle
http://arxiv.org/abs/1405.0527arXivWorking Paper
Additional Information:© 2013 Springer International Publishing Switzerland. Supported by National Science Foundation grants CCF-1219274, 0832824. We thank Erik Winfree for valuable discussion and suggestions on our results, Paul Rothemund for stimulating conversations on molecular muscle, and Niall Murphy for informative discussions on circuit complexity theory. Damien thanks Beverley Henley for introducing him to developmental biology many moons ago.
Funders:
Funding AgencyGrant Number
NSFCCF-1219274
NSFCCF-0832824
NSFCCF-1162589
Record Number:CaltechAUTHORS:20140506-085427393
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:20140506-085427393
Official Citation: Parallel Computation Using Active Self-assembly Moya Chen, Doris Xin, Damien Woods Pages 16-30
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:45513
Collection:CaltechAUTHORS
Deposited By: Ruth Sustaita
Deposited On:06 May 2014 18:11
Last Modified:06 May 2014 18:11

Repository Staff Only: item control page