Chen, Moya and Xin, Doris and Woods, Damien (2015) Parallel computation using active self-assembly. Natural Computing, 14 (2). pp. 225-250. ISSN 1572-9796

Preview

Download (1MB) | Preview

Abstract

We study the computational complexity of the recently proposed nubots model of molecular-scale self-assembly. The model generalises asynchronous cellular automata 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 macroscale 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, we show that 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. Asynchronous cellular automata are not capable of such parallelism, and our result shows that adding a movement primitive to such a model, to get the nubots model, drastically increases parallel processing abilities.

Item Type:	Article
Keywords:	Molecular robotics; Self-assembly; Computational complexity;
Academic Unit:	Faculty of Science and Engineering > Computer Science Faculty of Science and Engineering > Research Institutes > Hamilton Institute
Item ID:	12406
Identification Number:	https://doi.org/10.1007/s11047-014-9432-y
Depositing User:	Damien Woods
Date Deposited:	10 Feb 2020 18:09
Journal or Publication Title:	Natural Computing
Publisher:	Springer
Refereed:	Yes
URI:	Publisher
Use Licence:	This item is available under a Creative Commons Attribution Non Commercial Share Alike Licence (CC BY-NC-SA). Details of this licence are available here

Repository Staff Only(login required)

Item control page

Downloads

Origin of downloads