Paper by Erik D. Demaine
- Sarah Cannon, Erik D. Demaine, Martin L. Demaine, Sarah Eisenstat, Matthew J. Patitz, Robert Schweller, Scott M. Summers, and Andrew Winslow, “Two Hands Are Better Than One (up to constant factors): Self-Assembly In The 2HAM vs. aTAM”, in Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013), Kiel, Germany, February 27–March 2, 2013, pages 172–184.
We study the difference between the standard seeded model (aTAM) of tile
self-assembly, and the “seedless” two-handed model of tile
self-assembly (2HAM). Most of our results suggest that the two-handed model
is more powerful. In particular, we show how to simulate any seeded system
with a two-handed system that is essentially just a constant factor larger.
We exhibit finite shapes with a busy-beaver separation in the number of
distinct tiles required by seeded versus two-handed, and exhibit an infinite
shape that can be constructed two-handed but not seeded. Finally, we show
that verifying whether a given system uniquely assembles a desired supertile
is co-NP-complete in the two-handed model, while it was known to be
polynomially solvable in the seeded model.
- The full paper is available as arXiv.org:1201.1650 of the Computing Research Repository (CoRR).
- Copyright held by the authors. Licensed under the Creative Commons Attribution-No Derivative Works 3.0 license.
- The paper is available in PDF (752k).
- See information on file formats.
- [Google Scholar search]
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated January 13, 2020 by