Volume 9 (2013) Article 1 pp. 1-29
The Power of Nondeterminism in Self-Assembly
Received: February 25, 2011
Revised: October 3, 2012
Published: January 21, 2013
Keywords: nondeterminism, polynomial hierarchy, completeness, self-assembly
ACM Classification: F.2.2
AMS Classification: 68Q17

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.