Parallel Computation Using Active Self-assembly
From MaRDI portal
Abstract: We study the computational complexity of the recently proposed nubot model of molecular-scale self-assembly. The model generalises asynchronous cellular automata to have non-local movement where large assemblies of molecules can be pushed and pulled around, analogous to millions of molecular motors in animal muscle effecting the rapid movement of macroscale arms and legs. We show that the nubot model 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 solvable in polylogarithmic expected time and polynomial workspace using nubots. Along the way, we give fast parallel nubot 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 the nubot model is a highly parallel model of computation in a formal sense. Asynchronous cellular automata are not capable of this parallelism, and our result shows that adding a rigid-body movement primitive to such a model, to get the nubot model, drastically increases parallel processing abilities.
Recommendations
- Parallel computation using active self-assembly
- Computational self-assembly
- Fuel Efficient Computation in Passive Self-Assembly
- Dynamic self-assembly in living systems as computation
- Parallelism and time in hierarchical self-assembly
- Parallelism and time in hierarchical self-assembly
- Active self-assembly of algorithmic shapes and patterns in polylogarithmic time
- Simulation of programmable matter systems using active tile-based self-assembly
Cites work
- A theory of strict P-completeness
- A very hard log-space counting class
- Active self-assembly of algorithmic shapes and patterns in polylogarithmic time
- Algorithms and Computation
- Amplifying lower bounds by means of self-reducibility
- An introduction to tile-based self-assembly
- Asynchronous signal passing for tile self-assembly: fuel efficient computation and efficient assembly of shapes
- Complexities for Generalized Models of Self-Assembly
- Complexity classes for self-assembling flexible tiles
- Computation with finite stochastic chemical reaction networks
- Fast Computation by Population Protocols with a Leader
- Hierarchical self assembly of patterns from the Robinson tilings: DNA tile design in an enhanced tile assembly model
- scientific article; zbMATH DE number 48028 (Why is no real title available?)
- scientific article; zbMATH DE number 610968 (Why is no real title available?)
- scientific article; zbMATH DE number 1161568 (Why is no real title available?)
- scientific article; zbMATH DE number 1869460 (Why is no real title available?)
- scientific article; zbMATH DE number 784042 (Why is no real title available?)
- One tile to rule them all: simulating any tile assembly system with a single universal tile
- One-dimensional staged self-assembly
- Optimal kinodynamic motion planning for 2D reconfiguration of self-reconfigurable robots
- P-completeness of Cellular Automaton Rule 110
- Randomized Self-assembly for Approximate Shapes
- Randomized self-assembly for exact shapes
- Realistic reconfiguration of crystalline (and telecube) robots
- Reconfiguration of Cube-Style Modular Robots Using O(logn) Parallel Moves
- Reducing tile complexity for self-assembly through temperature programming
- Reducing tile complexity for the self-assembly of scaled shapes through temperature programming
- Self-assembly with geometric tiles
- Self-assemblying Classes of Shapes with a Minimum Number of Tiles, and in Optimal Time
- Staged self-assembly: nanomanufacture of arbitrary shapes with \(O(1)\) glues
- The program-size complexity of self-assembled squares (extended abstract)
- The Two-Handed Tile Assembly Model Is Not Intrinsically Universal
- Tile complexity of approximate squares
- Two hands are better than one (up to constant factors): self-assembly in the 2HAM vs. aTAM
Cited in
(11)- Terminating distributed construction of shapes and patterns in a fair solution of automata
- A minimal requirement for self-assembly of lines in polylogarithmic time
- Parallel computation using active self-assembly
- An exponentially growing nubot system without state changes
- Computation = self-assembly + conformational change: Toward new computing paradigms.
- Fast algorithmic self-assembly of simple shapes using random agitation
- Leader election and shape formation with self-organizing programmable matter
- scientific article; zbMATH DE number 1304542 (Why is no real title available?)
- Improved Leader Election for Self-organizing Programmable Matter
- Fuel Efficient Computation in Passive Self-Assembly
- A minimal requirement for self-assembly of lines in polylogarithmic time
This page was built for publication: Parallel Computation Using Active Self-assembly
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5168495)
