Topic: The Program-Size Complexity of Self-Assembled Squares

Authors: Rothemund and Winfree 2000.

Abstract:

We study a formal model of crystalline self-assembly, called the Tile 
Assembly Model, in which a tile may be added to a growing object when the 
total interaction strength with its neighbors exceeds a threshold. This 
model has been shown to be turing universal, so self-assembled objects can 
be studied from complexity point of view. Here we define the program size 
complexity of a NxN square to be the minimum no. of distinct tiles 
required to assemble the square. We study this complexity and find a 
dramatic decrease in complexity from N^2 to O(log N) as the threshold 
increases from 1 to 2. Further we see that the size of the largest square 
uniquely produced by a set of n tiles grows faster than any computable 
function.