Complexities for Generalized Models of Self-Assembly

by Gagan Aggarwal, Michael H. Goldwasser, Ming-Yang Kao and Robert T. Schweller

Abstract: In this paper, we extend Rothemund and Winfree's examination of the tile complexity of tile self-assembly. They provided a lower bound of $\Omega(\frac{\log N}{\log\log N})$ on the tile complexity of assembling an N x N square for almost all N. Adleman et al. gave a construction which achieves this bound. We consider whether the tile complexity for self-assembly can be reduced through several natural generalizations of the model. One of our results is a tile set of size $O(\sqrt{\log N})$ which assembles an N x N square in a model which allows flexible glue strength between non-equal glues. This result is matched by a lower bound dictated by Kolmogorov complexity. For three other generalizations, we show that the $\Omega(\frac{\log N}{\log\log N})$ lower bound applies to N x N squares. At the same time, we demonstrate that there are some other shapes for which these generalizations allow reduced tile sets. Specifically, for thin rectangles with length N and width k, we provide a tighter lower bound of $\Omega(\frac{N^\frac{1}{k}}{k})$ standard model, yet we also give a construction which achieves $O(\frac{\log N}{\log\log N})$ complexity in a model in which the temperature of the tile system is adjusted during assembly. We also investigate the problem of verifying whether a given tile system uniquely assembles into a given shape, and show that this problem is NP-hard.

Complexities for Generalized Models of Self-Assembly
Gagan Aggarwal, Michael H. Goldwasser, Ming-Yang Kao, and Robert T. Schweller
Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), New Orleans, Louisiana, Jan. 2004, pp. 880-889.
Download as: [ pdf, pdf.gz, pdf.Z ]

A complete version later appeared as:
Complexities for Generalized Models of Self-assembly
Gagan Aggarwal, Qi Cheng, Michael H. Goldwasser, Ming-Yang Kao, Pablo Moisset de Espanes, and Robert T. Schweller
SIAM Journal of Computing, 34(6):1493-1515, 2005.
Download as: [ abstract, pdf, pdf.gz ]

Michael Goldwasser