The program-size complexity of self-assembled squares

Abstract

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 details