Complexities for Generalized Models of Self-Assembly

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

*Corresponding author for this work

Research output: Contribution to conferencePaper

33 Scopus citations

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 Ω(log N/ log log N) on the tile complexity of assembling an N×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(√log N) which assembles an N×N square in a model which allows flexible glue strength between non-equal glues (This was independently discovered in [3]). This result is matched 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 logN) 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.

Original languageEnglish (US)
Pages873-882
Number of pages10
StatePublished - Apr 15 2004
EventProceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms - New Orleans, LA., United States
Duration: Jan 11 2004Jan 13 2004

Other

OtherProceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms
CountryUnited States
CityNew Orleans, LA.
Period1/11/041/13/04

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Complexities for Generalized Models of Self-Assembly'. Together they form a unique fingerprint.

  • Cite this

    Aggarwal, G., Goldwasser, M. H., Kao, M-Y., & Schweller, R. T. (2004). Complexities for Generalized Models of Self-Assembly. 873-882. Paper presented at Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, New Orleans, LA., United States.