2026-08-15T23:21:11Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:3932 2024-03-06T10:34:39Z ddc:004 open_access

Two Hands Are Better Than One (up to constant factors): Self-Assembly In The 2HAM vs. aTAM Cannon, Sarah Demaine, Erik D. Demaine, Martin L. Eisenstat, Sarah Patitz, Matthew J. Schweller, Robert T. Summers, Scott M Winslow, Andrew abstract tile assembly model hierarchical tile assembly model two-handed tile assembly model algorithmic self-assembly DNA computing biocomputing 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sarah Cannon and Erik D. Demaine and Martin L. Demaine and Sarah Eisenstat and Matthew J. Patitz and Robert T. Schweller and Scott M Summers and Andrew Winslow 2013 Is Part Of LIPIcs, Volume 20, 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2013.172 urn:nbn:de:0030-drops-39321 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2013.172 eng https://creativecommons.org/licenses/by-nd/3.0/legalcode