Complexities for Generalized Models of Self-Assembly

Published on: 2005/01/01

Abstract

In this paper, we study the complexity of self-assembly under models that are natural generalizations of the tile self-assembly model. In particular, we extend Rothemund and Winfree's study of the tile complexity of tile self-assembly [Proceedings of the 32nd Annual ACM Symposium on Theory of Computing, Portland, OR, 2000, pp. 459--468]. They provided a lower bound of \(\Omega(\frac{\log N}{\log\log N})\) on the tile complexity of assembling an \(N\times N\) square for almost all N. Adleman et al. [Proceedings of the 33rd Annual ACM Symposium on Theory of Computing, Heraklion, Greece, 2001, pp. 740--748] 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\times N\) square in a model which allows flexible glue strength between nonequal glues. This result is matched for almost all N 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\times 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^{1/k =='"`UNIQ--h-1--QINU`"'Authors== =='"`UNIQ--h-2--QINU`"'File== [[Category:Papers]] {k})\) for the 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; we show that this problem is NP-hard for three of the generalized models. |authors=Gagan Aggarwal, Qi Cheng, Michael H. Goldwasser, Ming-Yang Kao, Pablo Moisset de Espanes, and Robert T. Schweller |file=CGM siam.pdf }}