Computer Science – Computational Complexity
Scientific paper
2006-02-05
Computer Science
Computational Complexity
A preliminary version of this paper appeared in Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA
Scientific paper
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\times 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 $\Omega(\frac{\log n}{\log\log 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(\frac{\log n}{\log\log 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.
Kao Ming-Yang
Schweller Robert
No associations
LandOfFree
Reducing Tile Complexity for Self-Assembly Through Temperature Programming does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Reducing Tile Complexity for Self-Assembly Through Temperature Programming, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Reducing Tile Complexity for Self-Assembly Through Temperature Programming will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-361695