Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

Revision #1 to TR10-195 | 27th April 2011 00:16

#### Parallelism and Time in Hierarchical Self-Assembly

Revision #1
Authors: Ho-Lin Chen, David Doty
Accepted on: 27th April 2011 00:16
Keywords:

Abstract:

We study the role that parallelism plays in time complexity of variants of Winfree's abstract Tile Assembly Model (aTAM), a model of molecular algorithmic self-assembly. In the "hierarchical" aTAM, two assemblies, both consisting of multiple tiles, are allowed to aggregate together, whereas in the "seeded" aTAM, tiles attach one at a time to a growing assembly. Adleman, Cheng, Goel, and Huang (\emph{Running Time and Program Size for Self-Assembled Squares}, STOC 2001) showed how to assemble an $n \times n$ square in $O(n)$ time in the seeded aTAM using $O(\frac{\log n}{\log \log n})$ unique tile types, where both of these parameters are optimal. They asked whether the hierarchical aTAM could allow a tile system to use the ability to form large assemblies in parallel before they attach to break the $\Omega(n)$ lower bound for assembly time. We show that there is a tile system with the optimal $O(\frac{\log n}{\log \log n})$ tile types that assembles an $n \times n$ square using $O(\log^2 n)$ parallel "stages", which is close to the optimal $\Omega(\log n)$ stages, forming the final $n \times n$ square from four $n/2 \times n/2$ squares, which are themselves recursively formed from $n/4 \times n/4$ squares, etc. However, despite this nearly maximal parallelism, the system requires superlinear time to assemble the square. We extend the definition of *partial order tile systems* studied by Adleman et al. in a natural way to hierarchical assembly and show that *no* hierarchical partial order tile system can build \emph{any} shape with diameter $N$ in less than time $\Omega(N)$, demonstrating that in this case the hierarchical model affords no speedup whatsoever over the seeded model. We also strengthen the $\Omega(N)$ time lower bound for deterministic seeded systems of Adleman et al. to nondeterministic seeded systems. Finally, we show that for infinitely many $n$, a tile system can assemble an $n \times n'$ rectangle, with $n > n'$, in time $O(n^{4/5} \log n)$, breaking the linear-time lower bound that applies to all seeded systems and partial order hierarchical systems.

Changes to previous version:

The previous version of this paper has been split into two papers, and a new result (sublinear time assembly of a shape) has been added to this paper. The previous other half of this paper is here: http://arxiv.org/abs/1011.3493

### Paper:

TR10-195 | 13th November 2010 06:41

#### Parallelism, Program Size, Time, and Temperature in Self-Assembly

TR10-195
Authors: Ho-Lin Chen, David Doty, Shinnosuke Seki, David Soloveichik
Publication: 11th December 2010 13:09