TY - JOUR

T1 - Complexities for generalized models of self-assembly

AU - Aggarwal, Gagan

AU - Cheng, Q. I.

AU - Goldwasser, Michael H.

AU - Kao, Ming-Yang

AU - De Espanes, Pablo Moisset

AU - Schweller, Robert T.

PY - 2005/12/1

Y1 - 2005/12/1

N2 - 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 Ω(log N/log log N) on the tile complexity of assembling an N × 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(√log N) which assembles an N × 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 Ω(log N/log log N) lower bound applies to N × 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 Ω(N 1/k/k) for the standard model, yet we also give a construction which achieves O(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.

AB - 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 Ω(log N/log log N) on the tile complexity of assembling an N × 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(√log N) which assembles an N × 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 Ω(log N/log log N) lower bound applies to N × 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 Ω(N 1/k/k) for the standard model, yet we also give a construction which achieves O(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.

KW - Kolmogorov complexity

KW - Polyominoes

KW - Self-assembly

KW - Tile complexity

KW - Tilings

KW - Wang tiles

UR - http://www.scopus.com/inward/record.url?scp=29344465994&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=29344465994&partnerID=8YFLogxK

U2 - 10.1137/S0097539704445202

DO - 10.1137/S0097539704445202

M3 - Article

AN - SCOPUS:29344465994

VL - 34

SP - 1493

EP - 1515

JO - SIAM Journal on Computing

JF - SIAM Journal on Computing

SN - 0097-5397

IS - 6

ER -