Reducing Tile Complexity for the Self-assembly of Scaled Shapes Through Temperature Programming

摘要

This paper concerns the self-assembly of scaled-up versions of arbitrary finite shapes. We work in the multiple temperature model that was introduced by Ag-garwal, Cheng, Goldwasser, Kao, and Schweller (Complexities for Generalized Models of Self-Assembly, SIAM J. Comput. 2005). The multiple temperature model is a natural generalization of Winfree's abstract tile assembly model, where the temperature of a tile system is allowed to be shifted up and down as self-assembly proceeds. We first exhibit two constant-size tile sets in which scaled-up versions of arbitrary shapes self-assemble. Our first tile set has the property that each scaled shape self-assembles via an asymptotically "Kolmogorov-optimum" temperature sequence but the scaling factor grows with the size of the shape being assembled. In contrast, our second tile set assembles each scaled shape via a temperature sequence whose length is proportional to the number of points in the shape but the scaling factor is a constant independent of the shape being assembled. We then show that there is no constant-size tile set that can uniquely assemble an arbitrary (non-scaled, connected) shape in the multiple temperature model, i.e., the scaling is necessary for self-assembly. This answers an open question of Kao and Schweller (Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2006), pp. 571-580, 2006), who asked whether such a tile set exists.