Impossibility and Efficiency Comparisions Between aTAM and 2HAM

From self-assembly wiki
Revision as of 14:01, 27 May 2014 by \('"2\)'"7
(\(1) \)2 | \(3 (\)4) | \(5 (\)6)
Jump to navigation Jump to search

Given that the 2HAM can simulate the aTAM (and that the converse is not true), it seems that the 2HAM is more powerful. Thus, it may be somewhat surprising that in [1] it was shown that there is a simple class of shapes (so-called loops) which can be assembled with slightly greater tile type efficiency in the aTAM at temperature 1 than in the 2HAM at temperature 1. (However, this separation disappears at temperature 2.) Nonetheless, in [1] it was also shown that there are shapes called staircases which can self-assemble in the 2HAM using roughly n tile types, while the aTAM requires a number exponential in n (and this can in fact be extended to the busy beaver function, BB(n)). In terms of impossibility, it was shown that there is a class of infinite shapes which self-assembles in the aTAM but not the 2HAM, and also a class of shapes which can self-assemble (in a weaker sense) in the 2HAM but not in the aTAM.

References

  1. 1.0 1.1 Sarah Cannon, Erik D. Demaine, Martin L. Demaine, Sarah Eisenstat, Matthew J. Patitz, Robert Schweller, Scott M. Summers, Andrew Winslow - Two Hands Are Better Than One (up to constant factors)
    Technical Report, Computing Research Repository (1201.1650),2012
    http://arxiv.org/abs/1201.1650
    Bibtex
    Author : Sarah Cannon, Erik D. Demaine, Martin L. Demaine, Sarah Eisenstat, Matthew J. Patitz, Robert Schweller, Scott M. Summers, Andrew Winslow
    Title : Two Hands Are Better Than One (up to constant factors)
    In : Technical Report, Computing Research Repository -
    Address :
    Date : 2012