The program-size complexity of self-assembled squares (extended abstract) 论文

摘要

Molecular self-assembly gives rise to a great diversityofcomplex 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 atilemay be added to the growing object when the total interaction strength with its neighbors exceeds a parameter T. This model has been shown to be Turinguniversal. Thus, self-assembled objects can be studied from the point of view of computational complexity. Here, we dene the program size complexity ofanNN 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 nd a dramatic decrease in complexity, from N 2 tiles to O(log N) tiles,asT is increased from 1 (where bonding is noncooperative) to 2 (allowing cooperative bonding). Further, we nd that the size of the largest square uniquely produced by a set of n tiles grows faster than any computable function. 1.