文章基本信息

标题：Two Hands Are Better Than One (up to constant factors): Self-Assembly In The 2HAM vs. aTAM
本地全文：下载
作者：Sarah Cannon ; Erik D. Demaine ; Martin L. Demaine 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2013
卷号：20
页码：172-184
DOI：10.4230/LIPIcs.STACS.2013.172
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：abstract tile assembly model; hierarchical tile assembly model; two-handed tile assembly model; algorithmic self-assembly; DNA computing; biocomputing