Revised: October 3, 2012

Published: January 21, 2013

**Keywords:**nondeterminism, polynomial hierarchy, completeness, self-assembly

**Categories:**complexity theory, polynomial-time hierarchy, completeness, tiling, self-assembly, nondeterminism

**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.