Running time and program size for self-assembled squares

Recently Rothemund and Winfree [6] have considered the program size complexity of constructing squares by self-assembly. Here, we consider the time complexity of such constructions using a natural generalization of the Tile Assembly Model defined in [6]. In the generalized model, the Rothemund-Winfree construction of n \times n squares requires time Θ( n log n ) and program size Θ(log n ). We present a new construction for assembling n \times n squares which uses optimal time Θ( n ) and program size Θ(\frac{log n }{log log n }). This program size is also optimal since it matches the bound dictated by Kolmogorov complexity. Our improved time is achieved by demonstrating a set of tiles for parallel self-assembly of binary counters. Our improved program size is achieved by demonstrating that self-assembling systems can compute changes in the base representation of numbers. Self-assembly is emerging as a useful paradigm for computation. In addition the development of a computational theory of self-assembly promises to provide a new conduit by which results and methods of theoretical computer science might be applied to problems of interest in biology and the physical sciences.

Authors

• Leonard M. Adleman
• Qi Cheng 0001
• Ashish Goel
• Ming-Deh A. Huang

Keywords

No keywords are indexed for this paper.