Revised: October 3, 2012
Published: January 21, 2013
Abstract: [Plain Text Version]
We investigate the role of nondeterminism in Winfree's abstract Tile Assembly Model (aTAM), in particular how its use in tile systems affects the resource requirements. We show that for infinitely many $c\in\N$, there is a finite shape $S$ that is self-assembled by a tile system (meaning that all of the various terminal assemblies produced by the tile system have shape $S$) with $c$ tile types, but every directed tile system that self-assembles $S$ (i. e., has only one terminal assembly, whose shape is $S$) needs more than $c$ tile types. We extend the technique to prove our main theorem, that the problem of finding the minimum number of tile types that self-assemble a given finite shape is $\spt$-complete. We then show an analogous “computability theoretic” result: there is an infinite shape $S$ that is self-assembled by a tile system but not by any directed tile system.
An extended abstract of this paper appeared in SODA'11.