Complexities for generalized models of self-assembly

Gagan Aggarwal*, Q. I. Cheng, Michael H. Goldwasser, Ming-Yang Kao, Pablo Moisset De Espanes, Robert T. Schweller

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

108 Scopus citations

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 Ω(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.

Original languageEnglish (US)
Pages (from-to)1493-1515
Number of pages23
JournalSIAM Journal on Computing
Volume34
Issue number6
DOIs
StatePublished - Dec 1 2005

Keywords

  • Kolmogorov complexity
  • Polyominoes
  • Self-assembly
  • Tile complexity
  • Tilings
  • Wang tiles

ASJC Scopus subject areas

  • Computer Science(all)
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Complexities for generalized models of self-assembly'. Together they form a unique fingerprint.

Cite this