  We investigate the role of nondeterminism in Winfree's abstract Tile Assembly
Model (aTAM), which was conceived to model artificial molecular self-assembling
systems constructed from DNA. Of particular practical importance is to find
tile systems that minimize resources such as the number of distinct tile types,
each of which corresponds to a set of DNA strands that must be
custom-synthesized in actual molecular implementations of the aTAM. We seek to
identify to what extent the use of nondeterminism in tile systems affects the
resources required by such molecular shape-building algorithms.
  We first show a "molecular computability theoretic" result: there is an
infinite shape S that is uniquely assembled by a tile system but not by any
deterministic tile system. We then show an analogous phenomenon in the finitary
"molecular complexity theoretic" case: there is a finite shape S that is
uniquely assembled by a tile system with c tile types, but every deterministic
tile system that uniquely assembles S has more than c tile types. In fact we
extend the technique to derive a stronger (classical complexity theoretic)
result, showing that the problem of finding the minimum number of tile types
that uniquely assemble a given finite shape is Sigma-P-2-complete. In contrast,
the problem of finding the minimum number of deterministic tile types that
uniquely assemble a shape was shown to be NP-complete by Adleman, Cheng, Goel,
Huang, Kempe, Moisset de Espan\'es, and Rothemund (Combinatorial Optimization
Problems in Self-Assembly, STOC 2002).
  The conclusion is that nondeterminism confers extra power to assemble a shape
from a small tile system, but unless the polynomial hierarchy collapses, it is
computationally more difficult to exploit this power by finding the size of the
smallest tile system, compared to finding the size of the smallest
deterministic tile system.
