Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published May 2000 | public
Book Section - Chapter

The program-size complexity of self-assembled squares


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.

Additional Information

© 2000 ACM.

Additional details

August 19, 2023
October 23, 2023