Running time and program size for self-assembled squares

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 &THgr;(n log n) and program size &THgr;(log n). We present a new construction for assembling n \times n squares which uses optimal time &THgr;(n) and program size &THgr;(\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.

REFERENCES

• 1: Leonard M. Adleman. Towards a mathematical theory of self-assembly. Technical Report 00-722, Department of Computer Science, University of Southern California, 2000.
• 2: H. Abelson, D. Allen, D. Coore, C. Hanson, G. Homsy, T. Knight, R. Nagpal, E. Rauch, G. Sussman and R. Weiss. Amorphous computing. AI Memo 1665, August 1999.
• 3: Chengde Mao, Thomas H. LaBean, John H. Reif and Nadrian C. Seeman. Logical computation using algorithmic self-assembly of DNA triple-crossover molecules. Nature, 407:493-496, 2000.
• 4: Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
• 5: Paul Rothemund. Using lateral capillary forces to compute by self-assembly. Proceedings of the National Academy of Sciences, 97:984-989, 2000.
• 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. II. Bell Systems Technical Journal, 40:1-42, 1961.
• 8: Erik Winfree, Furong Liu, Lisa A. Wenzler, and Nadrian C. Seeman. Design and self-assembly of two-dimensional DNA crystals. Nature, 394:539-544, 1998.
• 9: Erik Winfree. PhD thesis. Cal Tech, 1998.
• 10: Erik Winfree. Personal communication.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING

General Terms:
Design, Verification