Theory of Computing ------------------- Title : The Power of Nondeterminism in Self-Assembly Authors : Nathaniel Bryans, Ehsan Chiniforooshan, David Doty, Lila Kari, and Shinnosuke Seki Volume : 9 Number : 1 Pages : 1-29 URL : https://theoryofcomputing.org/articles/v009a001 Abstract -------- 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 $\Sigma_2^P$-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.