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.