Volume 9 (2013) Article 1 pp. 1-29

The Power of Nondeterminism in Self-Assembly

by Nathaniel Bryans, Ehsan Chiniforooshan, David Doty, Lila Kari, and Shinnosuke Seki

Received: February 25, 2011
Revised: October 3, 2012
Published: January 21, 2013

$\newcommand{\N}{{\mathbb N}} \newcommand{\spt}{\mathsf{\Sigma^\mathsf{P}_2}}$

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.

DOI: 10.4086/toc.2013.v009a001

© 2013 Nathaniel Bryans, Ehsan Chiniforooshan, David Doty, Lila Kari, and Shinnosuke Seki
Licensed under a Creative Commons Attribution License (CC-BY)