A Caltech Library Service

The program-size complexity of self-assembled squares

Rothemund, Paul W. K. and Winfree, Erik (2000) The program-size complexity of self-assembled squares. In: STOC '00 Proceedings of the thirty-second annual ACM symposium on Theory of computing. ACM , New York, NY, pp. 459-468. ISBN 1-58113-184-4.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


Molecular self-assembly gives rise to a great diversity of complex forms, from crystals and DNA helices to microtubules and holoenzymes. We study a formal model of pseudocrystalline self-assembly, called the Tile Assembly Model, in which a tile may be added to the growing object when the total interaction strength with its neighbors exceeds a parameter Τ. This model has been shown to be Turing-universal. Thus, self-assembled objects can be studied from the point of view of computational complexity. Here, we define the program size complexity of an NxN square to be the minimum number of distinct tiles required to self-assemble the square and no other objects. We study this complexity under the Tile Assembly Model and find a dramatic decrease in complexity, from N^2 tiles to O(log N) tiles, as Τ is increased from 1 (where bonding is noncooperative) to 2 (allowing cooperative bonding). Further, we find that the size of the largest square uniquely produced by a set of n tiles grows faster than any computable function.

Item Type:Book Section
Related URLs:
URLURL TypeDescription
Rothemund, Paul W. K.0000-0002-1653-3202
Winfree, Erik0000-0002-5899-7523
Additional Information:© 2000 ACM.
Record Number:CaltechAUTHORS:20161213-162052032
Persistent URL:
Official Citation:Paul W. K. Rothemund and Erik Winfree. 2000. The program-size complexity of self-assembled squares (extended abstract). In Proceedings of the thirty-second annual ACM symposium on Theory of computing (STOC '00). ACM, New York, NY, USA, 459-468. DOI=
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:72795
Deposited By: Kristin Buxton
Deposited On:14 Dec 2016 00:36
Last Modified:14 Dec 2016 00:36

Repository Staff Only: item control page