2006/02/05 by Kao, Ming-Yang, Schweller, Robert
#Computational Complexity (cs.CC) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.cs/0602010
We consider the tile self-assembly model and how tile complexity can be eliminated by permitting the temperature of the self-assembly system to be adjusted throughout the assembly process. To do this, we propose novel techniques for designing tile sets that permit an arbitrary length m binary number to be encoded into a sequence of O(m) temperature changes such that the tile set uniquely assembles a supertile that precisely encodes the corresponding binary number. As an application, we show how this provides a general tile set of size O(1) that is capable of uniquely assembling essentially any n× n square, where the assembled square is determined by a temperature sequence of length O(log n) that encodes a binary description of n. This yields an important decrease in tile complexity from the required Ω((log n)/(loglog n)) for almost all n when the temperature of the system is fixed. We further show that for almost all n, no tile system can simultaneously achieve both o(log n) temperature complexity and o((log n)/(loglog n)) tile complexity, showing that both versions of an optimal square building scheme have been discovered. This work suggests that temperature change can constitute a natural, dynamic method for providing input to self-assembly systems that is potentially superior to the current technique of designing large tile sets with specific inputs hardwired into the tileset.