Complexities for generalized models of self-assembly

ABSTRACT

In this paper, we extend Rothemund and Winfree's examination of the tile complexity of tile self-assembly [6]. 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. [1] 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 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.

REFERENCES

• 1: Leonard Adleman , Qi Cheng , Ashish Goel , Ming-Deh Huang, Running time and program size for self-assembled squares, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.740-748, July 2001, Hersonissos, Greece [doi>10.1145/380752.380881]
• 2: Len Adleman , Qi Cheng , Ashish Goel , Ming-Deh Huang , David Kempe , Pablo Moisset de Espanés , Paul Wilhelm Karl Rothemund, Combinatorial optimization problems in self-assembly, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509913]
• 3: Q. Cheng and P. M. de Espanes. Resolving two open problems in the self-assembly of squares. Technical Report 793, University of Southern California, June 2003.
• 4: M. Lagoudakis and T. LaBean. 2D DNA Self-assembly for Satisfiability. In Proceedings of the 5th DIMACS Workshop on DNA Based Computers held at MIT, Cambridge, 1999.
• 5: Ming Li , Paul Vitányi, An introduction to Kolmogorov complexity and its applications (2nd ed.), Springer-Verlag New York, Inc., Secaucus, NJ, 1997
• 6: Paul W. K. Rothemund , Erik Winfree, The program-size complexity of self-assembled squares (extended abstract), Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.459-468, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335358]
• 7: H. Wang. Proving theorems by pattern recognition. Bell Systems Technical Journal, 40:1--42, 1961.
• 8: Erik Winfree , John J. Hopfield, Algorithmic self-assembly of dna, 1998