Running time and program size for self-assembled squares

Published on: 2001/07/06

Abstract

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 \(\Theta(n \log n)\) and program size \(\Theta(\log n)\). We present a new construction for assembling \(n\times n\) squares which uses optimal time \(\Theta(n)\) and program size \(\Theta(\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 Adleman, Qi Cheng, Ashish Goel, and Ming-Deh Huang

File

Running time and program size for self-assembled squares.pdf