Computer Science – Computational Complexity
Scientific paper
2009-02-14
Computer Science
Computational Complexity
This is a major revision -- thanks to comments from two very helpful anonymous reviewers -- of "A Limit to the Power of Multip
Scientific paper
Majumder, Reif and Sahu have presented a stochastic model of reversible, error-permitting, two-dimensional tile self-assembly, and showed that restricted classes of tile assembly systems achieved equilibrium in (expected) polynomial time. One open question they asked was how much computational power would be added if the model permitted multiple nucleation, i.e., independent groups of tiles growing before attaching to the original seed assembly. This paper provides a partial answer, by proving that if a tile assembly model uses only local binding rules, then it cannot use multiple nucleation on a surface to solve certain "simple" problems in constant time (time independent of the size of the surface). Moreover, this time bound applies to macroscale robotic systems that assemble in a three-dimensional grid, not just to tile assembly systems on a two-dimensional surface. The proof technique defines a new model of distributed computing that simulates tile (and robotic) self-assembly. Keywords: self-assembly, multiple nucleation, locally checkable labeling.
No associations
LandOfFree
A Time Lower Bound for Multiple Nucleation on a Surface does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with A Time Lower Bound for Multiple Nucleation on a Surface, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Time Lower Bound for Multiple Nucleation on a Surface will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-55061