Volume 9 (2013) Article 1 pp. 1-29
The Power of Nondeterminism in Self-Assembly
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.