%% Theory of Computing
%% File: v009a001.tex
%% Publication date: January 21, 2013
%% Authors: Nathaniel Bryans, Ehsan Chiniforooshan, David Doty, Lila Kari, and Shinnosuke Seki
%
%
%
%
\documentclass{toc} 
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%

\usepackage[normal]{optional}
\usepackage{cite}


%
%
\tocdetails{%
volume=9, number=1, year=2013, firstpage=1,
%
received={February 25, 2011},
revised={October 3, 2012},
published={January 21, 2013},
doi={10.4086/toc.2013.v009a001}
}
%


%
\runningtitle{The Power of Nondeterminism in Self-Assembly}

%
\tocpdftitle{The Power of Nondeterminism in Self-Assembly}


%
%
%
\runningauthor{Nathaniel Bryans, Ehsan Chiniforooshan, David Doty, Lila Kari, and Shinnosuke Seki}
\copyrightauthor{Nathaniel Bryans, Ehsan Chiniforooshan, David Doty, Lila Kari, and Shinnosuke Seki}
%
%
%
\tocpdfauthor{Nathaniel Bryans, Ehsan Chiniforooshan, David Doty, Lila Kari, Shinnosuke Seki}



%
%


%
\renewcommand{\P}{\mathsf{P}}
\newcommand{\NP}{\mathsf{NP}}
\newcommand{\coNP}{\mathsf{coNP}}
\newcommand{\calT}{\mathcal{T}}
\newcommand{\calP}{\mathcal{P}}
\newcommand{\dom}{{\rm dom} \;}
\newcommand{\res}[1]{\textrm{res}(#1)}
\newcommand{\termasm}[1]{\mathcal{A}_{\Box}[#1]}
\newcommand{\prodasm}[1]{\mathcal{A}[#1]}
\newcommand{\set}[2]{\left\{ #1 \;\middle|\; #2 \right\}}
\newcommand{\setr}[2]{\set{#1}{#2}}
\newcommand{\setl}[2]{\set{#1}{#2}}
\newcommand{\pair}[2]{\left\langle #1 , #2 \right\rangle}
\newcommand{\Th}{^{\mathrm{th}}}
\newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor}
\newcommand{\ceil}[1]{\left\lceil #1 \right\rceil}
\renewcommand{\emptyset}{\varnothing}
\newcommand{\gadget}[1]{\textsl{#1}}


\newcommand{\Ktc}{\mathrm{C}^\mathrm{tc}}
\newcommand{\Kdtc}{\mathrm{C}^\mathrm{dtc}}
\newcommand{\MDTS}{\textsc{MinDirectedTileSet}}
\newcommand{\MTS}{\textsc{MinTileSet}}
\newcommand{\spt}{\mathsf{\Sigma^\mathsf{P}_2}}

\newcommand{\figuresize}{\normalsize}

%

\newcommand{\blank}{\llcorner\negthinspace\lrcorner}

\begin{document}

\begin{frontmatter}
%
\title{The Power of Nondeterminism in Self-Assembly\thanks{An extended abstract of this paper appeared as~\cite{BryChiDotKarSek11} in
 \href{http://dl.acm.org/citation.cfm?id=2133082}{SODA'11}.}}

%
%
%
\author[nathaniel]{Nathaniel Bryans\thanks{This author was supported by the NSERC Undergraduate Student Research Awards (USRA) grant.}}
\author[ehsan]{Ehsan Chiniforooshan\thanks{This author was supported by NSERC Discovery Grant R2824A01 and the Canada Research Chair Award in Biocomputing to Lila Kari.}}
\author[dave]{David Doty\thanks{This author was supported by NSERC Discovery Grant R2824A01 and the Canada Research Chair Award in Biocomputing to Lila Kari, by a Computing Innovation Fellowship under NSF grant 1019343 and NSF grants CCF-1219274 and CCF-1162589 and the Molecular Programming Project under NSF grant 0832824.}}
\author[lila]{Lila Kari\thanks{This author was supported by NSERC Discovery Grant R2824A01 and the Canada Research Chair Award in Biocomputing.}}
\author[shin]{Shinnosuke Seki\thanks{This author was supported by NSERC Discovery Grant R2824A01 and the Canada Research Chair Award in Biocomputing to Lila Kari, by Kyoto University Start-up Grant-in-Aid for Young Scientists (No. 021530), and by HIIT Pump Priming Project 902184/T30606. }}

%
\begin{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 \emph{directed} tile system that self-assembles $S$ (\ie, 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.
\end{abstract}


%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%
%

\tocacm{F.2.2}
\tocams{68Q17}

%
\tockeywords{nondeterminism, polynomial hierarchy, completeness, self-assembly}

\end{frontmatter}




%
%


\section{Introduction}
\label{sec-intro}

Tile self-assembly is an algorithmically rich model of ``programmable crystal growth.''
It is possible to design molecules (square-like ``tiles'') with specific binding sites so that, even subject to the chaotic nature of molecules floating randomly in a well-mixed solution, they are guaranteed to bind so as to form a single target shape.
This is despite the number of different types of tiles possibly being much smaller than the size of the shape and therefore having only ``local information'' to guide their attachment.
The ability to control nanoscale structures and machines to atomic-level precision will rely crucially on sophisticated self-assembling systems that automatically control their own behavior where no top-down externally controlled device could fit.

A practical implementation of self-assembling molecular tiles was proved experimentally feasible in 1982 by Seeman~\cite{Seem82} using DNA complexes formed from artificially synthesized strands.
%
Experimental advances have delivered increasingly reliable assembly of algorithmic DNA tiles with error rates of 10\% per tile in 2004~\cite{RoPaWi04}, 1.4\% in 2007~\cite{FujHarParWinMur07}, 0.13\% in 2009~\cite{BarSchRotWin09}, and 0.05\% in 2010~\cite{Constantine10personal}.
Erik Winfree~\cite{Winf98} introduced the abstract Tile Assembly Model (aTAM)---based on a constructive version of Wang tiling~\cite{Wang61,Wang63}---as a simplified mathematical model of self-assembling DNA tiles.
Winfree demonstrated the computational universality of the aTAM by showing how to simulate an arbitrary cellular automaton with a tile assembly system.
Building on these connections to computability, Rothemund and Winfree~\cite{RotWin00} investigated a self-assembly resource bound known as \emph{tile complexity}, the minimum number of tile types needed to self-assemble a shape.
They showed that for most $n$, the problem of self-assembling an $n \times n$ square has tile complexity $\Omega(\log(n)/\log \log (n))$, and Adleman, Cheng, Goel, and Huang~\cite{AdChGoHu01} exhibited a construction showing that this lower bound is asymptotically tight.
We discuss two different models of self-assembly below (unique versus strict), but both of the previous results hold for either model.
%
Under natural generalizations of the model~\cite{AGKS05, BeckerRR06, KaoSchS08, KS06, DDFIRSS07, Sum09, Dot10, ChaGopRei12, RNaseSODA2010, DemPatSchSum2010RNase, SolWin07, ManStaSto09ISAAC, DemEisIshWin11, FuPatSchShe12}, tile complexity can be reduced for tasks such as square-building and self-assembly of more general shapes.
%
%
%
%
%
%

We now briefly describe the aTAM; a formal definition is given in \expref{Section}{sec-tam-formal}.
A \emph{tile} in the aTAM is a unit square with a kind and strength of ``glue'' on each of its sides.
Tiles are assumed not to rotate so that each side has a well-defined direction: north, south, east, or west.
A \emph{tile assembly system} $\mathcal{T}=(T,\sigma,\tau)$ consists of a finite set $T$ of tile types (with infinitely many tiles of each type in $T$ available), a \emph{seed tile} $\sigma \in T$, from which growth is assumed to nucleate, and a \emph{temperature} $\tau$, assumed to be 2 in this paper.
Self-assembly proceeds from the seed tile $\sigma$, with tiles of types in~$T$ successively attaching themselves to the existing assembly.
Two tiles placed next to each other \emph{interact} if the glues on their abutting sides match, and a tile \emph{binds} to a binding site on an assembly if the total strength on all of its interacting sides is at least $\tau$.
The choice of which binding site to attach is nondeterministic.
It is possible that a single binding site could have more than one tile type able to attach with strength $\tau$, which is also a choice made nondeterministically (the impossibility of this situation occurring precisely characterizes the ``directed'' tile systems, described informally next and defined formally in \expref{Section}{sec-tam-formal}).

Since we use the term ``nondeterministic'' informally in various contexts to indicate any situation in which more than one choice is available, to avoid ambiguity, we introduce new terms to distinguish precisely between the two specific types of determinism we consider in this paper.
%
We say a tile system is \emph{directed} if it is guaranteed to form one unique terminal \emph{assembly} (terminal meaning that no tiles can attach to it), where an assembly is defined not only by which positions are eventually occupied by a tile, but also by which tile type is placed at each position.
%
In this case, we say the tile system \emph{uniquely self-assembles} the shape (since the terminal assembly is unique).
%
We say a tile system \emph{strictly self-assembles} a \emph{shape} (and we say the tile system is \emph{strict}) if all of its terminal assemblies are guaranteed to have that shape.
In the case that there is more than one terminal assembly with the same shape, these various assemblies will have different tile types at the same position (but will be in agreement about which positions have a tile).
A strict tile system may not be directed, despite enforcing another sort of determinism by guaranteeing what shape is to form.
%
\expref{Figure}{fig:nondirected-example} shows an example of a non-directed temperature tile system that strictly self-assembles a $2 \times 2$ square.

\begin{figure}[ht]
\centering
  \includegraphics[width=6in]{nondirected-example}
  \caption{\label{fig:nondirected-example} \figuresize a) Example of a non-directed temperature-2 tile system that strictly self-assembles a $2 \times 2$ square.  The seed tile is labeled as such, and the strength of a glue on a tile type's side is indicated by the number of small black squares.\  b) The two terminal assemblies (both having the same shape) of the tile system.  In this example, removing a single tile type (for instance, the white tile type), makes the tile system directed without affecting its ability to strictly self-assemble a $2 \times 2$ square.}
\end{figure}

A natural analogy may be made between a non-directed tile system that strictly self-assembles some shape and a nondeterministic Turing machine $N$ that always produces the same output on a given input, regardless of the nondeterministic choices made during computation.
There is always a deterministic Turing machine $M$ computing the same function as $N$ and using no more ``resources,'' according to any common resource bound such as time complexity, space complexity, or program length.
%
Therefore we regard such a restricted class of nondeterministic Turing machines as no more ``powerful'' than deterministic Turing machines.
%
Based on this analogy, it might seem that strict self-assembly, while allowing one form of nondeterminism (which tile goes where), so strongly requires another form of determinism (which positions have a tile) that extra power cannot be gained by allowing the tile systems to be non-directed.
%

More precisely, it is natural to conjecture that every infinite shape that is strictly self-assembled by some tile system is also strictly self-assembled by some directed tile system.
In the finitary case, \emph{every} finite shape is self-assembled by a directed tile system (possibly using as many tile types as there are points in the shape), so to make the idea non-trivial we might conjecture that the tile complexity of a finite shape is independent of whether we consider all tile systems or only those that are directed.
%
Such conjectures are appealing because the algorithmic design and verification of tile systems~\cite{SolWin07} as well as lower bounds and impossibility proofs~\cite{jLSAT1,ManStaSto10,AGKS05} %
often rely on reasoning about directed tile systems, which are ``better behaved'' in many senses than arbitrary tile systems, even those that strictly self-assemble a shape.
%
It would be helpful to begin such arguments with the phrase, ``Assume without loss of generality that the tile system is directed.''

However, these conjectures are false.


\subsection{Main results of this paper}
We show that for infinitely many $c\in\N$ there is a finite shape $S$ that is strictly self-assembled by a tile system with $c$ tile types, but (unlike the example in \expref{Figure}{fig:nondirected-example}) every directed tile system that strictly self-assembles $S$ has more than $c$ tile types.
In fact, to strictly self-assemble the shape in a directed tile system requires more than $\approx \frac{3}{2} c$ tile types.
Schweller~\cite{SchwellerPersonalCommunicationPNSA} has improved this by exhibiting a family of shapes with super-linear gap between their directed and non-directed tile complexities.
The issue is discussed in more detail in \expref{Section}{sec-conclusion}.
%
The techniques are used in the proof of our main theorem, which shows that (the decision version of) the problem of finding the minimum number of tile types that strictly self-assemble a given finite shape is complete for the complexity class $\spt=\NP^\NP$. %
In contrast, the problem of finding the minimum size \emph{directed} tile system that strictly self-assembles a shape was shown to be $\NP$-complete by Adleman, Cheng, Goel, Huang, Kempe, Moisset de Espan\'{e}s, and Rothemund~\cite{ACGHKMR02}.
(This result is discussed and compared to our own in more detail below.)
That is, not only is the answer to the question ``What is the tile complexity of shape $S$?'' different from the answer to ``What is the directed tile complexity of shape $S$?'', but the former question is fundamentally more difficult to answer than the latter, barring an unlikely collapse of complexity classes.

We then show an analogous phenomenon in the infinitary case: there is an infinite shape $S$ that is strictly self-assembled by a tile system but not by any directed tile system.
Therefore, in a ``molecular computability theoretic'' sense, nondirectedness allows certain shapes to be algorithmically self-assembled that are totally ``unassemblable'' (to borrow Adleman's term analogous to ``uncomputable''~\cite{Adle99}) under the constraint of directedness.



Based on these results, we conclude that nondeterminism in tile type placement confers extra power to self-assemble a shape from a small tile system, but unless the polynomial hierarchy collapses, it is computationally more difficult\footnote{``More difficult'' in the sense of nondeterministic time complexity, although it is conceivable that both problems have the same deterministic time complexity.} to exploit this power by finding the size of the smallest tile system, compared to finding the size of the smallest directed tile system.


\subsection{Comparison with related work}
%
%
%

As indicated above, Adleman, Cheng, Goel, Huang, Kempe, Moisset de Espan\'{e}s, and Rothemund~\cite{ACGHKMR02} consider the optimization problem, given a finite shape $S$, what is the size of the smallest tile system that uniquely self-assembles $S$ (\ie, smallest directed tile system that strictly self-assembles $S$)?
We consider the optimization problem, given a finite shape $S$, what is the size of the smallest tile system that strictly self-assembles $S$?
In other words, our optimization problem considers strictly more tile systems, by allowing those that self-assemble more than one terminal assembly, so long as all of those assemblies have the same shape, whereas in~\cite{ACGHKMR02} the optimization problem considers only directed tile systems, those that self-assemble a unique terminal assembly.
Therefore, for any given shape $S$, the answer to our optimization problem will be less than or equal to the answer to the optimization problem of~\cite{ACGHKMR02}.

A related result was shown by Aggarwal, Cheng, Goldwasser, Kao, Moisset de Espanes, and Schweller~\cite{AGKS05}, who studied a different problem using the same model of shape assembly that we use (strict self-assembly).
Theirs is a verification problem: given a finite shape $S$ \emph{and} a tile system $\calT$, does $\calT$ strictly self-assemble $S$?
They showed this problem to be $\coNP$-complete.
This is in contrast to the equivalent verification problem for unique assembly (\ie, strict self-assembly by a directed tile system, the model considered in~\cite{ACGHKMR02}), which was shown in~\cite{ACGHKMR02} to be solvable in polynomial time.

\begin{table}[ht]
\centering
\begin{tabular}{|l|l|l|}
\hline
& Strict self-assembly & Unique self-assembly \\ \hline
Verification & $\coNP$-complete~\cite{AGKS05} & $\P$~\cite{ACGHKMR02} \\ \hline
Optimization & $\spt$-complete [this paper] & $\NP$-complete~\cite{ACGHKMR02} \\ \hline
\end{tabular}
\caption{Four combinatorial problems in self-assembly of shapes, based on two binary choices: 1) \emph{verification} that a given tile system self-assembles a given shape versus \emph{optimization} of the number of tile types required to self-assemble a given shape, and 2) \emph{strict} self-assembly (many terminal assemblies allowed but they must all have the same shape) versus \emph{unique} self-assembly (only one terminal assembly allowed).}
\label{tab:problems-and-self-assembly-models}
\end{table}

These four results are outlined in \expref{Table}{tab:problems-and-self-assembly-models}.
It is instructive to observe why the containments in $\NP$ and $\spt$ of the bottom row of \expref{Table}{tab:problems-and-self-assembly-models} hold.
In the directed case, one can nondeterministically guess a tile system $\calT$ and then use the polynomial-time algorithm of the upper-right entry of \expref{Table}{tab:problems-and-self-assembly-models} to check whether $\calT$ is uniquely self-assembles $S$.
In the non-directed case, we can also nondeterministically guess a tile system $\calT=(T,\sigma,\tau)$.
The polynomial-time algorithm for unique self-assembly verification does not work for strict self-assembly; indeed, that problem is $\coNP$-complete as indicated in the upper-left entry of the table.
Therefore the optimization problem for strict self-assembly is not obviously contained in $\NP$.
To prove containment in $\spt$, it suffices to use a universal polynomially-bounded quantifier to check all possible sequences of tile additions to the seed of $\calT$ to verify that all terminal assemblies that result have the shape $S$.
Since $|T| \leq |S|$ if $\calT$ is a minimal tile system for $S$, the length in bits of the candidate tile addition sequences is bounded by a polynomial in $|S|$.



%
%
%
%
%
%
%
%
%













\section{Abstract Tile Assembly Model}
\label{sec-tam-formal}

\newcommand{\fullgridgraph}{G^\mathrm{f}}
\newcommand{\bindinggraph}{G^\mathrm{b}}

This section gives a terse definition of the abstract Tile Assembly Model (aTAM,~\cite{Winf98}). This is not a tutorial; for readers unfamiliar with the aTAM, Rothemund and Winfree~\cite{RotWin00} give an excellent introduction to the model. %
Doty~\cite{DotCACM} provides a high-level overview of the field, reviewing several aTAM results.


%
Fix an alphabet $\Sigma$. $\Sigma^*$ is the set of finite strings over $\Sigma$. Given a discrete object $O$, $\langle O \rangle$ denotes a standard encoding of $O$ as an element of $\Sigma^*$. $\Z$, $\Z^+$, and $\N$ denote the set of integers, positive integers, and nonnegative integers, respectively. For a set $A$, $\calP(A)$ denotes the power set of $A$. Given $A \subseteq \Z^2$, the \emph{full grid graph} of $A$ is the undirected graph $\fullgridgraph_A=(V,E)$, where $V=A$, and for all $u,v\in V$, $\{u,v\} \in E \iff \| u-v\|_2 = 1$; \ie, iff $u$ and $v$ are adjacent on the integer Cartesian plane. A \emph{shape} is a set $S \subseteq \Z^2$ such that $\fullgridgraph_S$ is connected. A shape $\Upsilon$ is a \emph{tree} if $\fullgridgraph_\Upsilon$ is acyclic.



A \emph{tile type} is a tuple $t \in (\Sigma^* \times \N)^4$; \ie, a unit square with four sides listed in some standardized order, each side having a \emph{glue} $g \in \Sigma^* \times \N$ consisting of a finite string \emph{label} and nonnegative integer \emph{strength}.
We assume a finite set $T$ of tile types, but an infinite number of copies of each tile type, each copy referred to as a \emph{tile}. An \emph{assembly}
is a nonempty connected arrangement of tiles on the integer lattice $\Z^2$, \ie, a partial function $\alpha:\Z^2 \dashrightarrow T$ such that $\fullgridgraph_{\dom \alpha}$ is connected and $\dom \alpha \neq \emptyset$. The \emph{shape} $S_\alpha \subseteq \Z^2$ of $\alpha$ is $\dom \alpha$.
Two adjacent tiles in an assembly \emph{interact} if the glues on their abutting sides are equal (in both label and strength) and have positive strength.
Each assembly $\alpha$ induces a \emph{binding graph} $\bindinggraph_\alpha$, a grid graph whose vertices are positions occupied by tiles, with an edge between two vertices if the tiles at those vertices interact.\footnote{For $\fullgridgraph_{S_\alpha}=(V_{S_\alpha},E_{S_\alpha})$ and $\bindinggraph_\alpha=(V_\alpha,E_\alpha)$, $\bindinggraph_\alpha$ is a spanning subgraph of $\fullgridgraph_{S_\alpha}$: $V_\alpha = V_{S_\alpha}$ and $E_\alpha \subseteq E_{S_\alpha}$.}
Given $\tau\in\Z^+$, $\alpha$ is \emph{$\tau$-stable} if every cut of $\bindinggraph_\alpha$ has weight at least $\tau$, where the weight of an edge is the strength of the glue it represents.
That is, $\alpha$ is $\tau$-stable if at least energy $\tau$ is required to separate $\alpha$ into two parts. When $\tau$ is clear from context, we say $\alpha$ is \emph{stable}.
Given two assemblies $\alpha,\beta:\Z^2 \dashrightarrow T$, we say $\alpha$ is a \emph{subassembly} of $\beta$, and we write $\alpha \sqsubseteq \beta$, if $S_\alpha \subseteq S_\beta$ and, for all points $p \in S_\alpha$, $\alpha(p) = \beta(p)$.

A \emph{tile assembly system} (TAS) is a triple $\calT = (T,\sigma,\tau)$, where $T$ is a finite set of tile types, $\sigma:\Z^2 \dashrightarrow T$ is the finite, $\tau$-stable \emph{seed assembly}, and $\tau\in\Z^+$ is the \emph{temperature}.
Given two $\tau$-stable assemblies $\alpha,\beta:\Z^2 \dashrightarrow T$, we write $\alpha \to_1^{\calT} \beta$ if $\alpha \sqsubseteq \beta$ and $|S_\beta \setminus S_\alpha| = 1$. In this case we say $\alpha$ \emph{$\calT$-produces $\beta$ in one step}.\footnote{Intuitively $\alpha \to_1^\calT \beta$ means that $\alpha$ can grow into $\beta$ by the addition of a single tile; the fact that we require both $\alpha$ and $\beta$ to be $\tau$-stable implies in particular that the new tile is able to bind to $\alpha$ with strength at least $\tau$. It is easy to check that had we instead required only $\alpha$ to be $\tau$-stable, and required that the cut of $\beta$ separating $\alpha$ from the new tile has strength at least $\tau$, then this implies that $\beta$ is also $\tau$-stable.}
If $\alpha \to_1^{\calT} \beta$, $ S_\beta \setminus S_\alpha=\{p\}$, and $t=\beta(p)$, we write $\beta = \alpha + (p \mapsto t)$.
The \emph{$\calT$-frontier} of $\alpha$ is the set 
\[
\partial^\calT \alpha = \bigcup_{\alpha \to_1^\calT \beta} S_\beta
\setminus S_\alpha\,,
\]
the set of empty locations at which a tile could stably attach to $\alpha$.
%

A sequence of $k\in\Z^+ \cup \{\infty\}$ assemblies $\alpha_0,\alpha_1,\ldots$ is a \emph{$\calT$-assembly sequence} if, for all $1 \leq i < k$, $\alpha_{i-1} \to_1^\calT \alpha_{i}$.
We write $\alpha \to^\calT \beta$, and we say $\alpha$ \emph{$\calT$-produces} $\beta$ (in 0 or more steps) if there is a $\calT$-assembly sequence $\alpha_0,\alpha_1,\ldots$ of length $k = |S_\beta \setminus S_\alpha| + 1$ such that
1) $\alpha = \alpha_0$,
2) $S_\beta = \bigcup_{0 \leq i < k} S_{\alpha_i}$, and
3) for all $0 \leq i < k$, $\alpha_{i} \sqsubseteq \beta$.
If $k$ is finite then it is routine to verify that $\beta = \alpha_{k-1}$.\footnote{If we had defined the relation $\to^\calT$ based on only finite assembly sequences, then $\to^\calT$ would be simply the reflexive, transitive closure $(\to_1^\calT)^*$ of $\to_1^\calT$. But this would mean that no infinite assembly could be produced from a finite assembly, even though there is a well-defined, unique ``limit assembly'' of every infinite assembly sequence.} We say $\alpha$ is \emph{$\calT$-producible} if $\sigma \to^\calT \alpha$, and we write $\prodasm{\calT}$ to denote the set of $\calT$-producible assemblies. The relation $\to^\calT$ is a partial order on $\prodasm{\calT}$~\cite{Roth01,jSSADST}.
%
A $\calT$-assembly sequence $\alpha_0,\alpha_1,\ldots$ is \emph{fair} if, for all $i$ and all $p\in\partial^\calT\alpha_i$, there exists $j$ such that $\alpha_j(p)$ is defined; \ie, no frontier location is ``starved.''

%
An assembly $\alpha$ is \emph{$\calT$-terminal} if $\alpha$ is $\tau$-stable and $\partial^\calT \alpha=\emptyset$.
We write $\termasm{\calT} \subseteq \prodasm{\calT}$ to denote the set of $\calT$-producible, $\calT$-terminal assemblies.
A TAS $\calT$ is \emph{directed (a.\,k.\,a., deterministic, confluent)} if the poset $(\prodasm{\calT}, \to^\calT)$ is directed; \ie, if for each $\alpha,\beta \in \prodasm{\calT}$, there exists $\gamma\in\prodasm{\calT}$ such that $\alpha \to^\calT \gamma$ and $\beta \to^\calT \gamma$.\footnote{The following two convenient characterizations of ``directed'' are routine to verify.
%
$\calT$ is directed if and only if $|\termasm{\calT}| = 1$. $\calT$ is \emph{not} directed if and only if there exist $\alpha,\beta\in\prodasm{\calT}$ and $p \in S_\alpha \cap S_\beta$ such that $\alpha(p) \neq \beta(p)$.} %
%
%
We say that a TAS $\calT$ \emph{strictly self-assembles} a shape $S \subseteq \Z^2$ if, for all $\alpha \in \termasm{\calT}$, $S_\alpha = S$; \ie, if every terminal assembly produced by $\calT$ has shape $S$.
If $\calT$ strictly self-assembles some shape $S$, we say that $\calT$ is \emph{strict}.
Note that the implication ``$\calT$ is directed $\implies$ $\calT$ is strict'' holds, but the converse does not hold.
If $\calT$ strictly self-assembles $S$ and $\calT$ is directed, then we say that $\calT$ \emph{uniquely self-assembles} $S$.

In this paper we will always use \emph{singly-seeded temperature-2} TAS's, those with $|S_\sigma|=1$ and $\tau=2$; hence we will use the term \emph{seed tile} for $\sigma$ as well, and for the remainder of this paper we use the term TAS to mean singly-seeded temperature-2 TAS\@.
When $\calT$ is clear from context, we may omit $\calT$ from the notation above and instead write
$\to_1$,
$\to$,
$\partial \alpha$,
\emph{frontier},
\emph{assembly sequence},
\emph{produces},
\emph{producible}, and
\emph{terminal}.
Since the behavior of a TAS $\calT=(T,\sigma,2)$ is unchanged if every glue with strength greater than 2 is changed to have strength exactly 2, we assume henceforth that all glue strengths are 0, 1, or 2, and use the terms \emph{null glue}, \emph{single glue}, and \emph{double glue}, respectively, to refer to these three cases.\footnote{We use \emph{null bond}, \emph{single bond}, and \emph{double bond} similarly to refer to the \emph{interaction} of two tiles.}
We also assume without loss of generality that every single glue or double glue occurring in some tile type in some direction also occurs in some tile type in the opposite direction, \ie, there are no ``effectively null'' single or double glues.\footnote{Thus the existence of a tile with a double glue facing empty space implies that the empty space is part of the frontier. Many of our arguments use the contrapositive that if a shape $S$ is strictly self-assembled by a tile system and a side of a tile faces a point $p \not\in S$, then the tile cannot have a double glue on that side.}









\section{Assembly of finite shapes}
\label{sec-finite-shapes}


In this section we study the power of nondeterminism in assembling finite shapes.
We first show that the tile complexity of some shapes can be reduced using nondeterminism.
The ideas in this construction will be useful in proving the main theorem of this section, which shows that the minimum tile set problem is $\spt$-complete.

Recall that all of the TAS's we study are assumed singly-seeded.
%
    Let $S \subseteq \Z^2$ be a shape.
    The \emph{(temperature-2) tile complexity} of $S$ is 
\[
\Ktc(S) =
    \min \setl{|T|}{\text{$\calT=(T,\sigma,2)$ is a TAS and $\calT$ strictly self-assembles $S$}}\,,
\]
with the convention $\min \emptyset = \infty$.
%
%
%
    The \emph{(temperature-2) directed tile complexity} of $S$ is 
\[
\Kdtc(S) = \min \setl{|T|}{\text{$\calT=(T,\sigma,2)$ is a directed TAS
    and $\calT$ strictly self-assembles $S$} }\,.
\]
%

Using the terminology of the introduction, $\Ktc(S)$ is the minimum number of tile types required to strictly self-assemble $S$, and $\Kdtc(S)$ is the minimum number of tile types required to unique self-assemble $S$.

The temperature parameter $\tau=2$ means that we distinguish two energy levels of bonds, ``strong'' (strength 2, which can bind on their own) and ``weak'' (strength 1, which require two cooperating bonds to bind).
Higher temperatures mean more discrete energy levels available, which potentially leads to more precise control over tile placement. %
It is worth mentioning that the temperature potentially affects the tile complexity of a shape.
Seki and Okuno~\cite{SekiOkuno2012} considered, for an arbitrary
constant $\tau\in\Z^+$, the \emph{directed temperature-at-most-$\tau$
  tile complexity} of $S$, denoted by 
\[
\Kdtc_\tau(S) = \min
\setl{|T|}{\text{$\calT=(T,\sigma,\tau')$ is a directed TAS, $\tau'
    \leq \tau$, and $\calT$ strictly self-assembles $S$} }\,.
\]
%
They proved that for any temperature $\tau \ge 2$, there is a finite shape $S$ with $\Kdtc_\tau(S) < \Kdtc_{\tau-1}(S)$. %
In practice, only temperature-2 self-assembly has been experimentally implemented~\cite{RoPaWi04, FujHarParWinMur07, BarSchRotWin09}.
Therefore, in this paper we focus on temperature-2 TASs.
Our main theorems hold even if we use an arbitrary positive constant temperature $\tau > 2$ in place of 2.
%

We are interested in the problems, given a finite shape, what is its tile complexity, and what is its directed tile complexity? We define two decision problems that are equivalent to these optimization problems. Let $\mathcal{FS} \subset \calP(\Z^2)$ denote the set of all finite shapes. The \emph{minimum tile set} problem is
\[
  \MTS = \setr{ \pair{S}{c} }{\text{$S \in \mathcal{FS}$, $c \in \Z^+$, and $\Ktc(S) \leq c$}},
\]
and the \emph{minimum directed tile set} problem is
\[
  \MDTS = \setr{ \pair{S}{c} }{\text{$S \in \mathcal{FS}$, $c \in
      \Z^+$,  and $\Kdtc(S) \leq c$}}\,.
\]
Adleman, Cheng, Goel, Huang, Kempe, Moisset de Espan\'{e}s, and Rothemund~\cite{ACGHKMR02} showed that the problem $\MDTS$ is $\NP$-complete. In \expref{Section}{sec-finite-shapes-complete} we show that $\MTS$ is $\spt$-complete, where $\spt=\NP^\NP$. See~\cite{arora2009computational} for a discussion of these complexity classes.








%

%
%
%
%
%











\subsection{A finite shape for which nondeterminism reduces tile complexity}
Although the main result of \expref{Section}{sec-finite-shapes}, \expref{Theorem}{thm-sigma-2-complete}, together with the (widely-believed) assumption that $\NP \neq \spt$ and the fact proven in~\cite{ACGHKMR02} that $\MDTS \in \NP$, implies \expref{Theorem}{thm-finite-shape} of this subsection, we prove \expref{Theorem}{thm-finite-shape} explicitly in order to illustrate some of the reasoning used in the proof of \expref{Theorem}{thm-sigma-2-complete}.

\newcommand{\lemCycleTreeSplit}{%
Given a shape $S$ (possibly a subshape of a larger shape we wish to self-assemble), we say some tile types \emph{hard-code} $S$ to mean that there are $|S|$ unique tile types, each one specific to a position in $S$, using double glues between tile types of all adjacent positions in $S$.

Given a shape $S$ with a subshape $S' \subset S$, we say $S'$ is an \emph{isolated} subshape of $S$ if there is a point $p \in S'$ such that every path from a point in $S'$ to a point in $S \setminus S'$ includes $p$. In this case, we say $p$ is the \emph{root} of the subshape.
If $S'$ is a tree, we say it is an \emph{isolated subtree} of $S$.
We say that an isolated subshape $S'$ of $S$ is \textit{singly-connected} if there is precisely one point in $S \setminus S'$ adjacent to the root of $S'$.}
\opt{normal}{\lemCycleTreeSplit}

\newcommand{\figFiniteShape}{%
\begin{figure}[ht]
\centering
  \includegraphics{finite-shape-example}
  \caption{\label{fig:finite-shape-example} \figuresize A finite shape $S$ for which $\Ktc(S) < \Kdtc(S)$.  Nondeterminism is forced to occur at the two-color top-middle position of the loop $L$, since any minimal tile set must reuse the tile types from subtrees $A$ and $B$ to create $L$.  }
\end{figure}}

\begin{theorem} \label{thm-finite-shape}
  There is a finite shape $S \subset \Z^2$ such that $\Ktc(S) < \Kdtc(S)$.
\end{theorem}


\opt{submission}{\figFiniteShape
The shape is shown in \expref{Figure}{fig:finite-shape-example}. A formal proof of \expref{Theorem}{thm-finite-shape} is contained in \expref{Section}{sec-appendix}. Intuitively, the tile complexity is about $2h$ since the tile types for the two ``pillars'' on the right can be reused to create the two more closely packed pillars on the left. Since the right half of the shape is a tree, all tile types in that region must be unique and therefore already contribute $2h$ to the tile complexity of the whole shape.  In fact, any attempt to use fewer than $3h$ tile types necessarily introduces competition between tile types by forcing us to reuse tile types from the right two pillars to assemble the left two pillars.}

\newcommand{\proofThmFiniteShape}{%
  As such a shape $S$, we propose the shape illustrated in \expref{Figure}{fig:finite-shape-example}.
  The shape $S$ consists of two copies of a subshape $S'$, which is in a labeling box in the figure, and a bridge that connects  one of the 6 bottom positions of the grey scaffolds of a copy of $S'$ with the corresponding position of the other copy.
  The shape $S'$ contains a subshape called the loop $L$ that consists of $L_0, L_1, \ldots, L_h$, $L_0', L_1', \ldots, L_h'$, the tile between $L_h$ and $L_h'$, and the tile between $L_0$ and $L_0'$.
  The height $h$ is left as a variable parameter; increasing $h$ increases the gap between $\Ktc(S)$ and $\Kdtc(S)$.

\opt{normal}{\figFiniteShape}

  First we establish that $\Ktc(S) \leq 2h+30$ (actually with equality, but we only require and hence prove an upper bound).
  A TAS $\mathcal{T}$ that strictly self-assembles $S$ is designed in the following manner.
  Its seed is placed somewhere on the connecting bridge of $S$, and the bridge is hardcoded using 13 tile types.
  The hardcoding allows $\mathcal{T}$ to put tiles of the same type at the leftmost and rightmost positions of the bridge, to the north of which the two copies of $S'$ can assemble by reusing other ($2h+16$) tile types.
  By having $\mathcal{T}$ reuse $h$ tile types for $A_0, \ldots, A_h$ and for $L_0, \ldots, L_h$ and other $h$ tile types for $B_0, \ldots, B_h$ and for $L_0', \ldots, L_h'$, $\mathcal{T}$ can assemble a copy of $S'$ using $2h+16$ tile types.
  Note that this TAS is not directed because the top-middle position of the loop could receive either a tile from $A$ or a tile from $B$.
  Furthermore, these must be different tile types, because the top-right tile type in $A$ must have a double glue on its west but cannot have a double glue on any other side, whereas the top-left tile type of $B$ must have a double glue on its east but not on any other side.

  We now show that this nondeterminism is necessary to achieve the minimum tile complexity by showing that $\Kdtc(S) \geq 3h$.
  Let $\mathcal{T}'$ be a directed TAS that strictly self-assembles $S$, that is, it admits the unique terminal assembly $\alpha$ with $S_\alpha = S$.
  Its seed is placed either on one of the two copies of $S'$ or on the connecting bridge, and this means that the other copy of $S'$ grows from the position where the bridge is connected.
  We will see that the subprocess to assemble the seed-free copy of $S'$ costs $3h$ tile types, which implies $\Kdtc(S) \geq 3h$.

  Let $S_T$ be the tree which consists of the subtrees $A, B$ and the three tiles connecting them.
  In order to assemble the $S_T$ of the seed-free copy of $S'$, $\mathcal{T}'$ needs $2h+7$ tile types due to Theorem~4.3 in~\cite{ACGHKMR02}.
  Now we will prove that the loop $L$ of the copy costs $\mathcal{T}'$ $h$ tile types more.
  Depending on how this loop is assembled, we have two cases to be examined.
  First we consider the case when the loop is assembled so as for every pair of adjacent tiles on it to be bound via double glue.
  Then, it is possible for $\mathcal{T}'$ to assemble the left pillar upward as $L_1 \to L_2 \to \cdots \to L_h$.
  Being doubly-bonded with its right neighbor, the tile that $\mathcal{T}'$ puts on the top-middle position of the loop $L$ should be different from the one on the end of the subtree $A$.
  This means that the left pillar cannot reuse the tiles on $A$.
  If the left pillar reused any tile type on $B$ instead, then a tile would stick out to the left of the left pillar.

  The other case is when some of adjacent tiles on the loop $L$ are not bound via double glue.
  Note that at most 2 such weak bonds can appear on the loop, and furthermore, they must be incident on a single tile.
  Thus, we assume without loss of generality that such a weak bond does not occur on the left pillar.
  If $L_h'$ and the tile on the top-middle of $L$ are bonded by double glue, then all tiles on the positions $L_0, L_1, \ldots, L_h$ as well as the top-middle and $L_h'$ are bounded by double glue and, hence, the process of assembling $\alpha$ can proceed upward from $L_0$ to $L_h'$.
  This process should not reuse any tile type on the subtree $A$ in order to prevent the tile type $\alpha(L_h')$ from filling the gap between the subtrees $A$ and $B$.
  Clearly, it cannot borrow any tile type from the subtree $B$, either.
  If the bond is weak, the right pillar must grow upward.
  Hence, this pillar cannot reuse any tile type on the subtree $B$ because otherwise $\mathcal{T}'$ would produce another terminal assembly in which the tile on the top-middle position of $L$ is bonded with its right neighbor by double glue.
  As mentioned above, it is almost trivial that the right pillar cannot reuse any tile type on the subtree $A$.
}

\opt{normal}{\begin{proof} \proofThmFiniteShape \end{proof}}

\subsection{The Minimum Tile Set problem is \texorpdfstring{$\spt$-complete}{Sigma-2-P-Complete}}
\label{sec-finite-shapes-complete}

\newcommand{\eac}{\exists\forall\textsc{CNF-Unsat}}
\newcommand{\aec}{\forall\exists\textsc{CNF-Sat}}

\newcommand{\negate}[1]{\neg #1}

The following is the main theorem of this paper.

\begin{theorem} \label{thm-sigma-2-complete}
  $\MTS$ is $\spt$-complete.
\end{theorem}

\begin{figure}[ht]
\centering
  \includegraphics[width=6in]{reduction-final}
  \caption{\label{fig:reduction-final} \figuresize The shape $S$ of the reduction $\langle \varphi
  \rangle \mapsto \pair{S}{c}$ showing $\eac$ is polynomial-time many-one reducible to $\MTS$.  In this example, the quantified negated
  CNF formula $\varphi=\exists x \forall y \negate{\phi(x,y)}$ has clauses $C_1,C_2$ and $C_3$,
  $\exists$-variables $x_1,x_2$, and $x_3$, and $\forall$-variables $y_1$ and $y_2$. The ``matrix''
  of gadgets at the top left has a row of gadgets for each clause and a column of gadgets for each
  variable. The matrix sits atop a group of ``pillars'' that, when tiled by actual tiles, will
  represent a variable assignment to $\phi$ (along with one taller left-boundary pillar to help
  initiate cooperative binding of gadgets to assemble the matrix). The tree $\Upsilon$ is $S$
  without the matrix and pillars beneath it. In the zoom-in, the two yellow lines above the yellow X represent strength-1 glues that cooperate to place the gray gadget once (enough of) the black gadgets to its west and south are in place.  The yellow X shows ``backward growth'' of the gray gadget that is blocked before it can grow down far enough to form a new copy of the bottom row of $S$.}
\end{figure}

\begin{proof}
  To show that $\MTS \in \spt$, define the verification language
  \[
  \MTS_V = \setr{\langle S,c,\calT,\vec{\alpha} \rangle}{%
    \begin{minipage}{75mm}
      $S \in \mathcal{FS}$, $c\in\Z^+$, $\calT=(T,\sigma,2)$ is a TAS
      with $|T| \leq c$,
      $\vec{\alpha}=(\sigma,\alpha_2,\alpha_3,\ldots,\alpha_{k})$ is a
      $\calT$-assembly sequence with $S_{\alpha_k}=S$, and $\alpha_k$ is
        $\calT$-terminal
    \end{minipage}  }\,.
  \]
Clearly $\MTS_V \in \P$.  $\MTS \in \spt$ because $\pair{S}{c} \in \MTS$ if and only if there exists $\calT=(T,\sigma,2)$ with $|T| \leq c$ such that for all $\calT$-assembly sequences $\vec{\alpha}=(\sigma,\alpha_2,\ldots,\alpha_k)$ of length $k=|S|$, $\langle S,c,\calT,\vec{\alpha} \rangle \in \MTS_V$, with $\left| \langle \calT \rangle \right|$ and $|\langle \vec{\alpha} \rangle|$ bounded by $O(|\pair{S}{c}|^2)$.

To show that $\MTS$ is $\spt$-hard, we show that $\eac$ is polynomial-time many-one reducible to $\MTS$, where $\eac$ is the $\spt$-complete language~\cite{SchUma02a,Stockmeyer1976,Wrathall1976}
\[
\eac =
\setr{\langle \varphi \rangle}{
  \begin{minipage}{95mm}
    $\varphi$ is a true quantified Boolean formula $\varphi=\exists x
    \forall y \negate{\phi(x,y)}$, where $\phi$ is an unquantified CNF
    formula with $n+m$ input bits $x=x_1,\ldots,x_n$ and $y=y_1,\ldots,y_m$
  \end{minipage}}\,.
\]
We follow a similar strategy to the reduction of $\textsc{3Sat}$ to $\MDTS$ shown in~\cite{ACGHKMR02}.
The reduction $\langle \varphi \rangle \mapsto \pair{S}{c}$ works as follows.
First, we compute a tree $\Upsilon \in \mathcal{FS}$ that ``represents'' $\varphi$ with subtree gadgets that encode possible variable assignments and their effect on clauses.
  We then process $\Upsilon$ with the polynomial-time algorithm described in~\cite{ACGHKMR02} that computes the minimum number of tile types needed to strictly self-assemble a tree.
  Let $\calT=(T,\sigma,2)$ be this minimal TAS that strictly self-assembles $\Upsilon$, and let $c=|T|$.
  We then compute a shape $S\in\mathcal{FS}$ such that $\Upsilon \subset S$ with the property that, if $\varphi$ is true, then the tile types in $T$ can be modified, solely through changing some null glues to be single or double glues, producing a TAS $\calT'=(T',\sigma,2)$ with $|T'|=|T|=c$ such that $\calT'$ strictly self-assembles $S$, and if $\varphi$ is false, then no TAS with at most $c$ tile types can strictly self-assemble $S$. The shape $S$ is shown in \expref{Figure}{fig:reduction-final}.
  %
  In \expref{Figure}{fig:reduction-final}, the height of pillars is set to a number bigger than
  $20\ell$, where $\ell$ is the number of variables in $\varphi$.\footnote{Actually, it is enough to
  set the height of pillars to any number bigger than the width of the clause-variable matrix.}

\begin{figure}[ht]
\begin{center}
  \includegraphics[scale=1.6]{gadgets}
  \caption{\label{fig:info-gadgets} \figuresize Six main varieties of ``information-bearing'' tree gadgets used in the reduction. The position $(i,j)$ where the gadget is intended to go in the matrix is encoded in binary. Gadgets intended for the top row are missing the top ``T/F'' bumps, and gadgets intended for the right column are different on the right depending on whether the clause is satisfied or not, as shown in \expref{Figure}{fig:reduction-final}.}
\end{center}
\end{figure}

  \paragraph{Informal description of how the shape $S$ relates to the formula $\varphi$}
  Informally, the shape $S$ encodes the formula $\varphi$ as follows.
  Each of the gadgets shown in \expref{Figure}{fig:info-gadgets} corresponds to a specific variable-clause pair.
  The ``matrix'' in \expref{Figure}{fig:reduction-final} is self-assembled by these gadgets, whose purpose is to evaluate the formula clause-by-clause by its own self-assembly.
  Each row in the matrix of the shape $S$ corresponds to a clause, and each column to a variable.
  In \expref{Figure}{fig:reduction-final}, there are three rows and five columns in the matrix, so a total of fifteen gadgets are used in the matrix.
  We imagine the matrix assembling one row at a time (although multiple rows could grow in parallel, but for one row to complete, the row below it must complete).
  The type of gadget at position $(i,j)$ used depends on whether a previous variable (one with index $< i$) satisfied the $j$th clause, and if not, whether the truth assignment to the $i$th variable now satisfies the $j$th clause.
  For the formula to be satisfied, all clauses must be satisfied, so every gadget in the rightmost column (corresponding to the last variable) must be of type ``satisfied,'' and if so, the black part of the shape to the right of the matrix (appearing like a three-rung ladder in \expref{Figure}{fig:reduction-final}) will \emph{not} form.
  The presence of at least one gadget in the rightmost column of type ``unsatisfied'' will form the ladder.
  In other words, the $S$ will be strictly self-assembled if and only if the variable assignment chosen (how this is done is described below) does not satisfy $\phi$.

  The way that variables are assigned to do this evaluation of the formula is as follows.
  The choice of assignments to the $\exists$-variables is done by design of the tile set, by choosing appropriate glues to make one of each of the two types of red ``pillars'' from the right side of $S$ grow on the left side of $S$ to start the assembly of the matrix.
  The choice of assignments to $\forall$-variables is not controlled by the design of the tile set.
  Rather, to grow the matrix (from a minimal number of tile types), one is forced to choose glues so as to allow both types of green pillars to assemble under the matrix, two for each column corresponding to a $\forall$-variable.
  Therefore the two green pillars (one representing True and the other False) nondeterministically compete to assign a value to that variable.
  This is the primary way nondeterminism is used in assembling the shape: all possible assignments to the $\forall$-variables are possible to choose, and if and only if all of them fail to satisfy the formula is the shape $S$ assembled properly (each possible assignment to the $\forall$-variables corresponds to a different terminal assembly, but they all have the shape $S$ if they all make $\phi$ evaluate to False).
  It is this ability to ``try out'' different assignments to the $\forall$-variables, which lead to different assemblies, so long as they all form the same shape, that confers the extra power on non-directed assembly of the shape.
  The ability manifests in adding an extra $\forall$ quantifier to the Boolean formula, which makes it a $\spt$-formula.

  \paragraph{Formal description of reduction}
  We now describe the reduction more formally.

  Suppose that $\phi$ has $k$ clauses $C_1,\ldots,C_k$ and $\ell=n+m$ input variables $v_1,\ldots,v_\ell$, where $v_1,\ldots,v_n = x_1,\ldots,x_n$ are the $\exists$-variables of $\varphi$ and $v_{n+1}\ldots,v_\ell = y_1,\ldots,y_m$ are the $\forall$-variables of $\varphi$.
  A clause $C$ is \emph{satisfied} by variable $v$ if $C$ contains literal $v$ and $v$ is true, or if $C$ contains literal $\negate{v}$ and $v$ is false.
  For each $1 \leq i \leq k$ and $1 \leq j \leq \ell$, define the
  following six gadgets:
  \begin{description}
    \item[\gadget{SST}$_{i j}$:] $C_i$ is satisfied by $v_p$ for some $1 \leq p < j$, and $v_j$ is true.
    \item[\gadget{SSF}$_{i j}$:] $C_i$ is satisfied by $v_p$ for some $1 \leq p < j$, and $v_j$ is false.
    \item[\gadget{UUT}$_{i j}$:] $C_i$ is unsatisfied by $v_p$ for every $1 \leq p \leq j$, and $v_j$ is true.
    \item[\gadget{UUF}$_{i j}$:] $C_i$ is unsatisfied by $v_p$ for every $1 \leq p \leq j$, and $v_j$ is false.
    \item[\gadget{UST}$_{i j}$:] $C_i$ is unsatisfied by $v_p$ for every $1 \leq p < j$, $C_i$ is satisfied by $v_j$, and $v_j$ is true.
    \item[\gadget{USF}$_{i j}$:] $C_i$ is unsatisfied by $v_p$ for every $1 \leq p < j$, $C_i$ is satisfied by $v_j$, and $v_j$ is false.
  \end{description}
  Each of these six main varieties of ``information-bearing'' gadgets is shown in \expref{Figure}{fig:info-gadgets}.
  Each gadget is designed to minimize the amount of ``potential unwanted cooperative strength-1 binding'' when they are placed next to each other in the ``matrix'' of gadgets in the upper left of \expref{Figure}{fig:reduction-final}.\footnote{Strength-1 glues can only have an effect on growth of gadgets in the matrix when they are on tiles on the gray positions $r$, $s$, and $t$ in \expref{Figure}{fig:info-gadgets}, if the tile types used to assemble those gadgets in the matrix are the same as those used to assemble the gadgets in $\Upsilon$. This is useful in proving the converse direction of the reduction by showing that if a tile assembly system with $\leq c$ tile types strictly self-assembles $S$, then $\varphi$ must be true.}
  Each gadget encodes the integers $i$ and $j$, as well as encoding the information about the clause $C_i$ and variable $v_j$ as described above.
  Some of the ``boundary case'' gadgets are shaped slightly differently than those in \expref{Figure}{fig:info-gadgets}.
  If $i=k$ (a ``top gadget''), the top of the gadget will not encode information about the truth value of the variable $v_i$.
  If $j=\ell$ (a ``right gadget''), the right side of the gadget will still encode whether the clause is satisfied, but the gadget will have a different shape than for $1 \leq j < \ell$. These special boundary shapes are shown in \expref{Figure}{fig:reduction-final}.

  Not all six varieties of gadgets are created for each $(i,j)$; the only gadgets created are those that are logically consistent with some variable assignment to $\phi$.
  The matrix and pillars portion of $S$ (\ie, $S \setminus \Upsilon$) depends only on the number of $\exists$-variables, the number of $\forall$-variables, and the number of clauses.
  The remainder of the information about $\varphi$ is encoded in the following choices about which gadgets to create in $\Upsilon$.
  In the case of $j=1$, the gadgets $\gadget{SST}_{i 1}$ and $\gadget{SSF}_{i 1}$ are not created.
  For any clause $C_i$ in which the literal $v_j$ (resp.\ $\negate{v_j}$) does not appear, the gadget $\gadget{UST}_{i j}$ (resp.\ $\gadget{USF}_{i j}$) is not created.
  Similarly, for any clause $C_i$ in which \emph{no} literal $v_p$ (resp.\ $\negate{v_p}$) appears for any $1 \leq p < j$, the gadget $\gadget{SST}_{i j}$ (resp.\ $\gadget{SSF}_{i j}$) is not created.
  Finally, for any clause $C_i$ in which the literal $v_j$ (resp.\ $\negate{v_j}$) \emph{does} appear, the gadget $\gadget{UUT}_{i j}$ (resp.\ $\gadget{UUF}_{i j}$) is not created.

%
%
%
%
%
%

  %

  The tree $\Upsilon$ is $S$ without the ``matrix'' on the top left and the ``pillars'' beneath it that connect it to the bottom row.
  Let $c=\Ktc(\Upsilon)$.
  We assume that the seed is placed on the rightmost position of the bottom row, for both the shapes $\Upsilon$ and $S$.
  \opt{normal}{At the end of the proof we show how to modify the shapes to enforce this restriction.}
  \opt{submission}{In \expref{Section}{sec-appendix} we show how to modify the shapes to enforce this restriction.}
  The steps needed to complete the proof are divided into several lemmas.
  \opt{normal}{These lemmas are proven after the current proof.}
  Lemmas~\ref{lem-varphi-true-implies-C-small} and~\ref{lem:C-small-implies-varphi-true} \opt{submission}{(proven in \expref{Section}{sec-appendix})} establish each direction of the claim that $\varphi$ is true $\iff \Ktc(S) \leq c$.
  %
  Intuitively, since $\Upsilon$ is a ``tree-like'' subshape of $S$ (despite the leftmost tiles intersecting cycles in $S$), any tile system that strictly self-assembles $S$ must place tiles in the bottom row that do not appear anywhere else in $\Upsilon$.
  $\varphi$ is true $\implies \Ktc(S) \leq c$ because we can modify the null glues of tiles in the left half of the bottom row of $\Upsilon$ to be double glues matching those tile types from the pillars on the right to grow the pillars on the left.
  In the case of the $\exists$-variables $x$ we choose an assignment by our choice of double glues.
  In the case of $\forall$-variables $y$ we have no choice; we must allow both the ``false'' and ``true'' pillars to grow and nondeterministically compete to assign a bit to each $y_i$.
  We can then modify null glues in the gadgets and pillars to be single glues that propagate information about the neighbors of a gadget to allow a new gadget encoding the proper information to be placed in the matrix.
  Therefore the assembly of the matrix ``evaluates $\phi(x,y)$'' and if it is false, strictly self-assembles $S$.
  The reverse direction is more tedious to establish.
  Again, since $\Upsilon$ is a ``tree-like'' subshape of $S$, any TAS strictly self-assembling $S$ already uses $c$ tile types just to assemble the $\Upsilon$ portion of $S$ (derived from \expref{Lemma}{lem:shape-to-tree}).
  Therefore to assemble all of $S$ using $c$ tile types requires reusing these same tile types.
  Our gadget design, together with the properties of minimal tile sets for trees, allow us to conclude that the only way to tile the matrix is ``using the gadgets in the way they were intended,'' which means the rightmost vertical bar of the matrix cannot form unless at least one clause is not satisfied; \ie, $\varphi$ is true.
  %

  To handle the placement of the seed, we use the same trick as in the proof of \expref{Theorem}{thm-finite-shape}, making two copies of the shape connected by a bridge to enforce that at least one copy does not contain the seed.
  Define $a \in S$ to be the rightmost point on the bottom row of $S$.
  Make two copies of $S$, place one directly above the other but without touching, and connect the copies by a width-1 ``bridge'' of length $h$ that connects to each copy of $a$ on $a$'s right side.
  Denote this new shape by $S'$.
  It is routine to show using techniques similar to those in the proof of \expref{Theorem}{thm-finite-shape} that any minimal TAS for $S'$ uses $\Ktc(S) + h$ tile types, places the seed in the bridge, uses $h$ tile types to grow the bridge and uses the tile types of a TAS $\calT$ that is minimal (subject to the restriction that $\calT$ places the seed at $a$) for $S$, to assemble each copy of $S$.
  Let $c'=c+h$.
  Our reduction outputs $\pair{S'}{c'}$, rather than $\pair{S}{c}$.
  By the arguments above concerning $S$, we have that $\varphi$ is true $\iff \Ktc(S') \leq c'$, whence $\eac$ is polynomial-time many-one reducible to $\MTS$.
\end{proof}

In the following lemmas, $\varphi$ denotes an arbitrary (true or false) quantified Boolean formula of the form $\varphi=\exists x \forall y \negate{\phi(x,y)}$, where $\phi$ is an unquantified CNF formula with $n+m$ input bits $x=x_1,\ldots,x_n$ and $y=y_1,\ldots,y_m$. $\Upsilon,S \in \mathcal{FS}(\Z^2)$ refer to the tree and shape constructed from $\varphi$ as in the proof of \expref{Theorem}{thm-sigma-2-complete}, and $c=\Ktc(\Upsilon)$.


\newcommand{\calTU}{\calT_{\Upsilon}}
\newcommand{\calTS}{\calT_{S}}

  \begin{lemma}\label{lem-varphi-true-implies-C-small}
    If $\varphi$ is true, then $\Ktc(S) \leq c$.
  \end{lemma}
  \begin{proof}
    Let $\calTU=(T,\sigma,2)$ be a minimal TAS that strictly self-assembles $\Upsilon$ with seed placed at position $a$, the rightmost point of the bottom row of $\Upsilon$, and let $\alpha \in \termasm{\calTU}$
    be the unique terminal producible assembly of $\calTU$, such that $S_\alpha = \Upsilon$.
    %
    Theorem 4.3 of~\cite{ACGHKMR02} shows that if $\calTU$ is a minimal TAS for $\Upsilon$, then $\calTU$ puts the same tile type in two positions
    $p_1,p_2\in\Upsilon$ if and only if the subtrees of $\Upsilon$ rooted at $p_1$
    and $p_2$ (with the seed location considered the root of $\Upsilon$) are isomorphic and ``identically entered'' (meaning both of them have their parent in the same direction).
    %
    This theorem is stated for directed TAS's but it is easy to show that any minimal TAS for a tree must be directed.
    %
    Given $\alpha$ and $t \in T$, define $t$ to be \emph{singular in $\alpha$} if it appears exactly once in $\alpha$.
    %
    Thus, all the positions at the bottom row of $\Upsilon$ will receive tile types that are singular in $\alpha$.

    Since $\varphi$ is true, there is an assignment $f$ to variables $x_1, x_2, \ldots, x_n$ such that
    any assignment to $y_1, y_2, \ldots, y_m$ makes $\phi(x, y)$ false.
    %
    Since all the tile types in the bottom row are unique, we can change the north glues of the
    tiles at the base of the clause-variable matrix, without ruining the rest of the shape.
    %
    We change the north glues so that the blue pillar grows as the leftmost pillar and for each
    variable $x_i$ we grow the red true/false pillar depending on $f(x_i)$ being true or false.
    %
    For the positions corresponding to $y$ variables, we change the north glues so that both true
    and false green pillars can grow.

    We will also change a number of null glues into single glues in the following way:
    the set of labels with strength one will be \texttt{T}, \texttt{F}, $\texttt{S}_{i,j}$, and
    $\texttt{U}_{i,j}$, where $1\leq i\leq k$ and $1\leq j\leq\ell$.
    %
    For each gadget $G$, let $p$ be the position of its branch point in $\Upsilon$, as shown in \expref{Figure}{fig:info-gadgets}.
    %
    Then, we change the null glue of the south side of $\alpha(s)$ to a single glue with
    label \texttt{T} if $G$ is of type \gadget{SST}, \gadget{UUT}, or \gadget{UST}; otherwise, we change the south glue to a single
    glue with label \texttt{F}.
    %
    Also, we change the north glue of $\alpha(s)$ to a single glue with label
    $\texttt{S}_{i,j}$ if $G$ is a gadget for the $i$th clause and $j$th variable and is of type \gadget{SST}
    or \gadget{SSF}; otherwise, if $G$ is of type \gadget{UUT}, \gadget{UUF}, \gadget{UST}, or \gadget{USF}, the north glue of $\alpha(s)$ will be
    a single glue with label $\texttt{U}_{i, j}$.
    %
    Note that, the tile type $\alpha(s)$ is singular in $\alpha$, due to the fact that
    its rooted subtree contains the encoding about the gadget type, clause number, and variable
    number, and hence, is not isomorphic to any other subtree.

    The north glue of the tile type $\alpha(r)$ will be changed to a strength one glue with label \texttt{T} if $G$ is of type \gadget{SST}, \gadget{UUT}, or \gadget{UST};
    otherwise, its label will be \texttt{F}.
    %
    The south glue of the tile type $\alpha(t)$ will be changed to a strength one glue with
    label $\texttt{S}_{i, j+1}$ if $G$ is for the $i$th clause and $j$th variable and is of type \gadget{SST},
    \gadget{SSF}, \gadget{UST}, or \gadget{USF}; otherwise, its label will be $\texttt{U}_{i, j+1}$.

    Applying the above-mentioned changes will give us a TAS $\calTS$ with the same tile complexity
    as $\calTU$.
    %
    In $\calTS$, a gadget can grow at the cell of the
    matrix corresponding to clause $i$ and variable $j$ using cooperation of single glues of the
    bottom and left gadget if and only if its notches match the notches of the bottom and left
    gadget.
    %
    And, the notches of gadgets are designed in a way that they can be put together to assemble $S$
    if and only if the truth assignment to $x$ and $y$ variables (presented as pillar notches at the first
    row of the matrix) make $\phi(x, y)$ false.
    %
    Intuitively, the gadgets grow in the matrix so as to ``evaluate $\phi(x,y)$'' on inputs $x$ and $y$ encoded in the pillars, with the pillars encoding $y$ nondeterministically choosing values for each of the $y_i$.
    %
    If we choose the proper assignment $f$ to $x$ such that, for all assignments to $y$ (corresponding to different terminal assemblies), $\phi(x,y)$ is false (such an assignment $f$ exists since $\varphi = \exists x \forall y \negate{\phi(x,y)}$ is true), then all of these assemblies will have at least one unsatisfied right gadget in the rightmost column of the matrix, and the assembly will have shape $S$.
    %
    Therefore $\calTS$ strictly self-assembles $S$.
  \end{proof}


  %
  %
  {}From here until the end of the section, assume that $\calTS=(T_S,\sigma,2)$ is a TAS that strictly self-assembles $S$ with the seed placed at the rightmost position on the bottom row.
  %
  Also, $B$ represents the subshape of $S$ that does not have the black matrix on
  the left, but has the pillars beneath it, and $I \subset \Z^2$ denotes the set of $k \times \ell$ positions (where $k$ is the number of clauses in $\phi$ and $\ell$
  is the number of variables) marked by
  small circles in \expref{Figure}{fig:reduction-final}.
  %
  A set $I'\subseteq I$ is called a \emph{staircase} if the following implication holds:
  \[
  \left[ (x_1,y_1)\in I', (x_2, y_2)\in I, x_2\leq x_1, \text{ and
    } y_2\leq y_1 \right] \implies (x_2, y_2)\in I'\,.
  \]
  Let $G^*=\bigcap_{G \in \mathcal{G}} G$, where each element of $\cal G$ is a set of tile positions of a
  gadget created in the proof of \expref{Theorem}{thm-sigma-2-complete}
  (\expref{Figure}{fig:info-gadgets}) translated so that the branch tile is at the origin (so, $\cal G$ has
  at most $k\times\ell\times 6$ elements).

  \begin{lemma}\label{lem:shape-to-tree}
    If $|T_S| \leq c = \Ktc(\Upsilon)$, then there is a TAS $\calTU=(T_\Upsilon,\sigma,2)$ that can be obtained from $\calTS=(T_S,\sigma,2)$ by only changing a number of
    double glues to null glues (in particular implying that $|T_\Upsilon|=|T_S|$), such that $\calTU$ strictly self-assembles $\Upsilon$.
  \end{lemma}
  \begin{proof}
    Let $\alpha\in\termasm{\calTS}$.
    Let the subassembly of $\alpha$ consisting of the gray row underneath the matrix, between the leftmost and rightmost pillars in \expref{Figure}{fig:reduction-final}, be denoted by $R$.
    It suffices to show that all tile types in $R$ appear precisely once in $\alpha \upharpoonright \Upsilon$ ($\alpha$ restricted to $\Upsilon$), and further that they are all bound together by double glues.
    This will establish that, by adjusting double glues on the north of tiles beneath the pillars to be null glues, all of $\Upsilon$ can grow from the tiles without growing any of the pillars or matrix of $S \setminus \Upsilon$, and without affecting the assembly of the rest of $\alpha \upharpoonright \Upsilon$.
    Since we only change double glues to null glues, it is not possible to introduce new double glues adjacent to empty space that were not already present, so nothing will grow outside of $\Upsilon$.


    First we show that every adjacent pair of tiles in $R$ is bound by a double glue.
    For the sake of contradiction, let $p_1\in\Upsilon$ and $p_2\in\Upsilon$ be the closest positions to the seed that are adjacent to each other but $\alpha(p_1)$ and $\alpha(p_2)$ do not have double glue between them.
    %
    Then, they are on the bottom row below the clause-variable matrix in $S$.
    %
    Thus, there must be a pillar growing down from the clause-variable matrix; consider the pillar
    that grows down in $\alpha$ earlier than the others.
    %
    This pillar cannot reuse any tile type that is used in positions to the right of $p_1$ in
    $\Upsilon$; otherwise, an undesirable part of $\Upsilon$ can grow to the left
    of the downward pillar.
    %
    Therefore, the number of tile types in $\calTS$ is at least $\Ktc(\Upsilon) -
    x + y$, where $x$ is the horizontal width of the clause-variable matrix and $y$ is the height of the pillars.
    %
    This is a contradiction to the assumption that $\calTS$ uses at most $\Ktc(\Upsilon)$
    tile types, since we set $y>x$ in our construction.
    %
    Thus every adjacent pair of tiles in $R$ is bound by a double glue.

    We now argue that each tile type in $R$ appears exactly once in $\alpha \upharpoonright \Upsilon$.
    Since the portion of $\Upsilon$ outside of $R$ is acyclic (and since we just showed tiles within $R$ are double-bonded to each other), then all of $\alpha \upharpoonright \Upsilon$ must be entirely double-bonded.
    Since $\Upsilon$ is a tree shape, there is no possibility of the presence of one tile in $\Upsilon$ ``blocking'' the growth of another in $\Upsilon$, since this would introduce a cycle in the shape being assembled and it would not be a tree.
    Therefore, for any two positions $p_1$ and $p_2$ in $\Upsilon$ such that $\alpha(p_1)=\alpha(p_2)$, any subtree of $\Upsilon$ rooted at $p_1$ (with respect to the seed location being the root of the whole tree) must also appear as a subtree of $p_2$.
    But every subtree within $\Upsilon$ of every position $p_1$ in $R$ (each such subtree being simply the portion of $R$ to the left of $p_1$, plus the gray row to the left of that, plus the single ``notch'' position just above the leftmost position on the row) does not appear anywhere else in $\Upsilon$.
    This can be verified by inspection of \expref{Figure}{fig:reduction-final}.
    Therefore the tile types in $R$ do not appear anywhere else in $\alpha \upharpoonright \Upsilon$.
  \end{proof}










The following lemma states the ``inductive step'' of the proof of \expref{Lemma}{lem:C-small-implies-varphi-true}.
%
Namely, if gadgets of a minimal tile system for $S$ grow to fill in part of the matrix ``in the way we intend,'' then the only way to extend this growth to fill in an additional gadget is also ``in the way we intend.''

In the following lemma, ``right branch'' and ``top branch'' refer to the two subtrees of a gadget rooted at the branch as shown in \expref{Figure}{fig:info-gadgets}.


\begin{lemma}\label{lem:matrix-steps}
    Suppose $\calTS$ has at most $c = \Ktc(\Upsilon)$ tile types. Let $\alpha\in\prodasm{\calTS}$ be a producible assembly such that
    \begin{enumerate}
      \item $B\subseteq S_\alpha\subseteq S$. (where $B$ is the subshape of $S$ that does not have the black matrix on
  the left, but has the pillars beneath it),
      \item $S_\alpha\cap I$ is a staircase of cardinality $m < |I|$,
      \item all tile types in $\alpha(S_\alpha\cap I)$ are branch tiles of gadgets,
      \item the right and top branches rooted at tiles in $S_\alpha
        \cap I$ are present in $\alpha$, and
      \item if there exists $p\in I$ such that $p \not\in S_\alpha$, then $S_\alpha \cap (p + G^*) = \emptyset$.
    \end{enumerate}
    %
    Then there exists an assembly $\beta \in \prodasm{\calTS}$ such that $\alpha\rightarrow\beta$ and requirements (1)-(5) are satisfied with ``$\alpha$'' replaced by ``$\beta$'' and ``$m$'' replaced by ``$m+1$.''
  \end{lemma}
  \begin{proof}
    $\alpha$ cannot be a terminal assembly, since $\calTS$ strictly self-assembles $S\neq S_{\alpha}$.

    Since double glues cannot be added to gadget tile types without ruining the tree shape portion
    of $S$, $\alpha$ must grow by cooperation of single glues.
    %
    This cooperation can happen only at $F-(4,3)$, where
    \[F=\set{p\in I\setminus S_\alpha}{\text{$(S_\alpha\cap
        I)\cup\{p\}$ is a staircase}}\,.\]
    In other words, $F-(4,3)$ is the set of points marked $s$ in \expref{Figure}{fig:info-gadgets}, which are adjacent to points marked $r$ and $t$ in neighboring gadgets.
    Let $\beta'$ be a minimal assembly producible from $\alpha$ such that $S_{\beta'}\cap F$ is not empty.
    %
    Let $\{p\} = S_{\beta'}\cap F$.
    %
    All paths from $S_\alpha$ to $p$ in $\beta'$ must pass through $s=p-(4,3)$, due to the
    minimality of $\beta'$.
    %
    Even if the tile type that goes in $s$ is not taken from any gadgets, the tile type that
    eventually goes to $s + (1, 1)$ must be chosen from a gadget, since it should be able to grown
    the zig-zag shape only by double glues, and the zig-zag shape is used only in one of the
    gadgets.
    %
    Thus, $\beta'(p)$ is a branch tile type.

    Since $p\in S_{\beta'}\cap I$ and $p\not\in S_\alpha\cap I$, $S_{\beta'}\cap I$ has cardinality at
    least $m+1$.
    Let $\beta$ be the minimal assembly producible from $\beta'$ in which the right and top branches of $p$ are tiled.
    %
    $\beta(p)$ and $\beta(q)$ for all $q$ in the branches of $p$ must be tile types from the correct gadget to ensure consistency with the notches of neighboring gadgets and consistency with the (row,column) identifier notches at the top of the right branch.
    %
    %
    %
    %

    Due to the minimality of $\beta$, it satisfies condition 5.
  \end{proof}















  \begin{lemma} \label{lem:C-small-implies-varphi-true}
    If $\calTS$ has at most $c$ tile types, then $\varphi$ is true.
  \end{lemma}
  \begin{proof}
    First we show that $B$ is $\calTS$-producible.
    %
    According to \expref{Lemma}{lem:shape-to-tree}, by changing a number of double glues in $\calTS$
    to null glues, we can obtain a TAS $\calTU$ that strictly self-assembles $\Upsilon$.
    %
    So, $\Upsilon$ is $\calTS$-producible.
    %
    Moreover, as can be checked in the proof of \expref{Lemma}{lem:shape-to-tree},
    the null glues in $\calTU$ that are double glues in $\calTS$ are the north
    glues of the tile types that appear at the base of pillars beneath the gadget matrix.
    %
    Also, all the pillars must grow from the bottom row to the matrix, and not downward, because
    growing a pillar downward requires adding a double glue to a tile type in the matrix area, which
    will also ruin $\Upsilon$.
    %
    Thus, $B$, which is $\Upsilon$ together with the pillars beneath the matrix, is
    $\calTS$-producible.
    %
    This establishes the base case.

    Let $f(x_i)$ be true if the red true pillar is used to grow the pillar corresponding to $x_i$
    and be false if the red false pillar is used.
    %
    Using \expref{Lemma}{lem:matrix-steps} for the inductive case, we conclude that there is an assembly $\alpha$
    such that $B\cup I\subseteq S_\alpha$ and valid gadgets are/can be used to fill the matrix part
    of $\alpha$.
    %
    By our construction of gadgets, this implies that the truth assignment $f$ to $x$ makes $\phi(x,y)$
    false for every value of $y$.
    %
    Thus $\varphi$ is true.
  \end{proof}














%
%
%
%
%


\section{Assembly of infinite shapes}
\label{sec-infinite-shapes}

In this section we study the power of nondeterminism in assembling infinite shapes. The following theorem, an infinitary analog of \expref{Theorem}{thm-finite-shape}, is the main result of \expref{Section}{sec-infinite-shapes}.
%

\begin{theorem} \label{thm-infinite-shape}
  There is a shape $S \subset \Z^2$ such that some TAS strictly self-assembles $S$, but no directed TAS strictly self-assembles $S$.
\end{theorem}

\begin{figure}[ht]
\begin{center}
  \includegraphics[width=6in]{infinite-shape-example}
  \caption{\label{fig:infinite-shape-example} \figuresize A portion of an infinite shape $S$ that strictly self-assembles, but not by any directed TAS\@.  The $n\Th$ ray simulates a Turing machine $M$ on input $n$, and a vertical line is present under that ray if and only if $M$ accepts $n$. $Y$ and $N$ are points at these positions representing ``yes'' and ``no'' instances of $L(M)$, respectively, and elements of $Y$ are the points where nondeterminism is forced to occur in any TAS that strictly self-assembles $S$.}
\end{center}
\end{figure}


\begin{proof}
  Let $L \subset \N$ be a language that is computably enumerable but not decidable, and let $M$ be a Turing machine such that $L = L(M) = \setr{n\in\N}{\text{$M$ accepts $n$}}$.
  Let $S$ be the shape that is strictly self-assembled by the TAS described below, when $M$ is encoded into the TAS as described.

  A portion of the shape $S$ is shown in \expref{Figure}{fig:infinite-shape-example}.
  The TAS that strictly self-assembles $S$ is based on the main construction of Lathrop, Lutz, Patitz, and Summers~\cite{jCCSA}.
  In that paper, the authors show that for each Turing machine $M$, an encoding of the language $L(M)\subseteq\N$ accepted by $M$ ``weakly self-assembles'' on the $x$-axis.
  More precisely, for a ``reasonably simple'' function $f:\N\to\N$, a special tile type is placed at position $(f(n),0)$ if and only if $n\in L(M)$.
  The $n\Th$ ``ray'' in \expref{Figure}{fig:infinite-shape-example} begins growth just before $(f(n),0)$, and grows independently of the other rays, controlling an adjacent simulation of $M(n)$ in parallel with all the other rays.
  The slope of each ray is just a bit smaller than the previous, with the slope approaching 2 as $n\to\infty$.
  The simulation executes one transition of $M$ on input $n$ every $\approx 2^n$ rows of the ray.
  Since $M$ can use no more than $k$ tape cells after $k$ transitions, this slowed simulation ensures that each ray has enough space to allow a potentially unbounded simulation of $M$ on each $n$, without ``crashing'' into the next adjacent ray, even in the worst case that $M$ moves its tape head right on every transition.

\pagebreak[4]
  What is needed from this construction for our purpose is:
  \begin{enumerate}
    \item $f$ is computable.\footnote{\cite{jCCSA} defines the roughly quadratic function $$f(n) = \binom{n+1}{2} + (n+1) \floor{\log n} + 6n - 2^{1+\floor{\log n}} + 2\,.$$
        Our version of this function will grow just a bit faster, to make room for a vertical line to form between two adjacent rays without ``touching'' the rest of the shape except at the endpoints of the line, but retains computability.}
    \item The simulation of $M(n)$, carried out adjacent to the $n\Th$ ray, sends a ``signal'' crawling down the right side of the simulation if and only if $M$ accepts $n$, placing a special tile just above the ``planter'' (the group of tiles growing below each of the rays).
  \end{enumerate}
  We modify the signal so that, rather than growing all the way to the planter, for input $n$, the signal grows to distance $n$ north of the planter and then grows a width-1 vertical line $n$ positions down to the planter, using the same tile type with equal north and south double glues to ``crash'' into the planter.
  To ensure that the downward-growing vertical lines do not obstruct the operation of the planter, the planter is modified so that it is guaranteed to grow horizontally a sufficient number of tiles before laying out the input for the $M$, so as to guarantee that there is something present for a ``controlled crash.''
  The space for the downward-growing line of length $n$ to drop after the input is accepted is created by having the Turing machine simulations begin not immediately above the planter, but at height $n$ on input $n$.
  This is why the $n\Th$ ray grows straight up for $n$ rows before beginning its sloped growth.
  Under \emph{every} simulation, a ``notch'' tile is placed above the planter using a double glue, which is horizontally lined up with where the vertical line will grow if $M$ accepts.
  The actions of the ray, planter and Turing machine simulation are otherwise similar to the mechanisms used in~\cite{jCCSA}.
  We note that this particular TAS is not directed since the ``notch'' tiles compete nondeterministically with the vertical line tiles at positions where $M$ accepts.

  It remains to show that no directed TAS strictly self-assembles $S$.
  Intuitively, we show that at points of the form $(f(n),0)$, any directed TAS must place tiles that ``know'' whether there will eventually be a vertical line above the point, implying the ability to decide $L$ since vertical lines appear above exactly those positions $(f(n),0)$ such that $n \in L$.
  Assume for the sake of contradiction that there is a directed TAS $\calT=(T,\sigma,2)$ that strictly self-assembles $S$, and let $\alpha\in\termasm{\calT}$ be its uniquely producible, terminal assembly.
  Since the heights of the vertical ``bases'' of each ray below the sloped portion are strictly increasing, there is some $n_0\in\N$ such that, for all $n > n_0$, the distance from $(f(n),1)$ to the ray above it is at least $|T|+1$.
  Let $Y = \setl{(f(n),0)}{\text{$n \in L$ and $n > n_0$}}$ be the bottommost points of the vertical lines adjacent to rays corresponding to (sufficiently large) ``yes'' instances of $L$, and let $N = \setl{(f(n),0)}{n \not\in L \text{ and } n > n_0}$ represent the positions of the ``notches'' corresponding to (sufficiently large) ``no'' instances.
  $Y$ and $N$ are shown in \expref{Figure}{fig:infinite-shape-example}.
  Let $T_Y = \alpha(Y)$ and $T_N = \alpha(N)$ be the set of tile types that appear at ``yes'' and ``no'' instance points, respectively.
  Since $S$ has empty space immediately north of positions in $N$, no tile type in $T_N$ has a north double glue.


  We claim that $T_Y\cap T_N = \emptyset$.
  For the sake of contradiction, suppose otherwise,  let $t \in T_Y \cap T_N$, and let $p \in Y$ be a point where $\alpha(p)=t$.
  Since $t\in T_N$, $t$ has no north double glue, so the vertical line above $p$ must grow downward using north and south double glues.
  Let $q=p+(0,1)$ be the point just above $p$.
  By our choice of $n_0$, the vertical line must repeat a tile type before reaching the point $q$, so all tile types in the repetition period have a north and a south double glue, including the tile type $t'=\alpha(q)$.
  Let $t''$ be the tile type appearing beneath $t'$ after the previous occurrence of $t'$ in the vertical line.
  Since $t''$ has a north double glue, $t'' \not\in T_N$, so $t'' \neq t$.
  Because $t$ binds to the rest of $\alpha$ only through its south double glue, there can be no precedence relationship enforcing that $p$ must contain a tile before $q$ (or any other point) receives a tile.
  In other words, there exists a producible assembly $\beta\in\prodasm{\calT}$ such that $\beta(q)=t'$ and $\beta(p)$ is undefined. This implies that $t''$ can bind to $\beta$ at position $p$ to create $\beta' = \beta + (p \mapsto t'')$, contradicting the directedness of $\calT$ since $\beta',\alpha\in \prodasm{\calT}$ but $\beta'(p) = t'' \neq t = \alpha(p)$.
  This verifies the claim that $T_Y \cap T_N = \emptyset$.

  For all $n\in\N$, let $p_n = (f(n),0)$. Since $T_Y \cap T_N = \emptyset$, for all $n > n_0$, 
\[
n \in L \iff p_n \in Y \iff \alpha(p_n) \in T_Y\,,\quad\text{and}\quad n \not\in L \iff p_n \in N \iff \alpha(p_n) \in T_N\,.
\]
  Using this fact, we describe an algorithm to decide $L$, contradicting its undecidability and completing the proof.
  On input $n\in\N$, if $n \leq n_0$, use a constant lookup table to decide $n$.
  Otherwise, compute $p_n = (f(n),0)$.
  Simulate the assembly of $\calT$ with a fair assembly sequence, maintaining a first-in, first-out queue of frontier locations to enforce fairness, until a tile is placed at position $p_n$.
  Since this assembly sequence is fair, the simulation will eventually place a tile type $\alpha(p_n)$ at $p_n$, and $\alpha(p_n)$'s membership in $T_Y$ or $T_N$ will indicate whether to accept or reject $n$.
\end{proof}

We have implemented the tile assembly system that strictly self-assembles $S$:
\begin{center}
\url{http://www.dna.caltech.edu/~ddoty/pnsa/}
\end{center}
It can be simulated using Matthew Patitz's ISU TAS simulator~\cite{PatitzTAS} available here:
\begin{center}
\url{http://www.cs.iastate.edu/~lnsa/software.html}
\end{center}
The purpose of the implementation is not to quantitatively analyze the construction, since we make no quantitative claims about either the shape being assembled or the TAS that strictly self-assembles the shape.  Furthermore, the bulk of the intellectual effort in the proof of \expref{Theorem}{thm-infinite-shape} is proving the negative result that no directed TAS strictly self-assembles the shape, which is something that cannot be established through a simulation.  We provide the simulation primarily to help the interested reader understand the details of the construction and help to convince oneself that the shape really can be strictly self-assembled and to directly observe how the TAS accomplishes this task.


\section{Conclusion}
\label{sec-conclusion}

We have investigated the power of nondeterminism for the strict self-assembly of shapes in the abstract Tile Assembly Model. We showed that for both the infinite and finite cases, even when the shape is required to be strictly self-assembled, nondeterminism can help to assemble the shape, by making strict self-assembly possible in the infinite case, and reducing tile complexity in the finite case. Furthermore, the problem of finding the minimum tile set to strictly self-assemble a shape is strictly harder (in the sense of nondeterministic time complexity) than that of finding the minimum directed tile set that does so, unless $\NP = \spt$.

\newcommand{\openProblems}{
There are some interesting questions that remain open:

\begin{enumerate}

  \item \label{open-question-1} What is the fastest growing function $f:\N\to\N$ for which one could prove a statement of the form ``\emph{For infinitely many $n\in\N$, there is a finite shape $S \subset \Z^2$ such that $\Ktc(S) \leq n$ and $\Kdtc(S) \geq f(n)$}''? The proof of \expref{Theorem}{thm-finite-shape} of the present paper establishes this statement for $f(n) =1.4999 n$.   Can $f(n)$ be made, for example, $n^2$ or $2^n$?  What is an upper bound for $f$ above which such a statement is false? Note that \expref{Theorem}{thm-infinite-shape} establishes such a statement for \emph{all} functions $f:\N\to\N$ if the shape is allowed to be infinite.  However, when designing complex tile systems, a common challenge is to direct a group of tiles to stop growing,\footnote{For example, $\Ktc(S) \approx \Kdtc(S) = O(\log n / \log \log n)$ for $S$ an $n \times k$ rectangle with $n \geq k \geq \log n / \log \log n$, but $\Ktc(S)$ and $\Kdtc(S)$ increase steadily towards $n$ as $k$ decreases from $\log n / \log \log n$ to 1; ``counting'' to the length of the rectangle and then stopping becomes more difficult as the rectangle's width decreases.} so it would be interesting to identify a family of \emph{finite} shapes with a fast-growing gap between the two tile complexity measures. This would imply that sometimes it \emph{really} helps to employ nondeterminism.

  \item We have showed that the optimization problem of finding precisely the smallest number of tile types to strictly self-assemble a shape is $\spt$-hard. Can it be shown that for some $\alpha>1$, the solution is $\spt$-hard to approximate within multiplicative factor $\alpha$? This may be related to \expref{Question}{open-question-1}.

  \item Is there an $\alpha > 1$ such that it is $\NP$-hard to find an $\alpha$-approximate solution to the minimum directed tile set problem?

  \item Shape-building is one common goal of self-assembly; pattern-painting is another. In particular, it is possible to assemble some patterns, such as disconnected sets, if we change the definition of what is interpreted as the assembled object. We say that a TAS $\calT = (T,\sigma,2)$ \emph{weakly self-assembles} a set $S \subseteq \Z^2$ if there is a subset $B \subseteq T$ (the tile types that are ``painted black'') such that, for all $\alpha\in\termasm{\calT}$, $\alpha^{-1}(B)=S$. In other words, the set of positions with a black tile is guaranteed to be $S$. In the case $B=T$, this definition is equivalent to strict self-assembly, but for $B \subsetneq T$ the shape is allowed to grow outside the desired pattern using tile types from $T \setminus B$ to allow ``extra computation room'' for painting the pattern using tile types from $B$. Such a definition is appropriate for modeling practical goals such as self-assembled circuit layouts~\cite{OrigamiLithographyNatureNano2009, CarbonNanotubesNatureNano2010, park2004electronic, park2006finite, LiuParReiLab04, YanParFinReiLab03} or placement of guides for walking molecular robots~\cite{DNARobotNature2010}; see~\cite{jSSADST,jCCSA} for more discussion of the theoretical issues of weak self-assembly.
      It remains open to prove or disprove analogs of Theorems~\ref{thm-infinite-shape} and~\ref{thm-finite-shape}, with ``weakly'' substituted for ``strictly.'' In other words, is it possible to uniquely paint an infinite (resp.\ finite) pattern with a tile system, but every tile system that does so (resp.\ that does so with no extra tile types) is not directed?


  \item It remains open to prove or disprove analogs of Theorems~\ref{thm-infinite-shape} and~\ref{thm-finite-shape}, with ``weakly'' substituted for ``strictly'' \emph{and} with ``strict'' substituted for ``directed.'' In other words, is it possible to uniquely paint an infinite (resp.\ finite) pattern with a tile system, but every tile system that does so (resp.\ that does so with no extra tile types) must self-assemble more than one shape on which this pattern is painted?

  \newcommand{\MWTS}{\textsc{MinWeakTileSet}}
  \newcommand{\MDWTS}{\textsc{MinDirectedWeakTileSet}}

  \item What is the status of the optimization problem of determining the minimum number of tile types to weakly self-assemble a finite pattern?  Let $\mathcal{F}(\Z^2)\subset \mathcal{P}(\Z^2)$ denote the set of all finite subsets of $\Z^2$.  Define
      $$
      \MWTS = \setr{\pair{S}{c}}{%
      \begin{minipage}{75mm}
      $S \in \mathcal{F}(\Z^2)$, $c\in\Z^+$, and $(\exists
      \calT=(T,\sigma,2)) \;|T|\leq c$, and $\calT$ weakly
      self-assembles $S$
    \end{minipage}}\,.
      $$
      In contrast to the case for strict self-assembly, it can be shown that $\MWTS$ is undecidable.  This follows from a ``Berry's paradox'' argument, similar to the one used to show that Kolmogorov complexity is uncomputable, together with the fact that arbitrary algorithms may be simulated in a tile assembly system.  Briefly, assuming this quantity is computable, define a Turing machine $M$ that on input $c\in\Z^+$ enumerates finite sets of points lying entirely on the positive $x$-axis until a set $S(c)$ is found whose ``weak self-assembly tile complexity'' exceeds $c$.  Then for each $c\in\Z^+$ define a tile system $\calT$ that simulates $M(c)$ in the second quadrant, using its output to place black tiles precisely on points in $S(c)$.  Since $\calT$ requires only $\log c + O(1)$ tile types, for sufficiently large $c$ this contradicts the tile complexity of $S(c)$.
      It is not difficult to show that $\MWTS \in \mathsf{\Pi}^0_2$.
      Is it complete for $\mathsf{\Pi}^0_2$?

  \item $\MDWTS$ is defined similarly to $\MWTS$ but also requiring $\calT$ to be directed.
      It is not difficult to show that $\MDWTS \in \mathsf{\Delta}^0_2$.
      Can be be shown that $\MDWTS \not\in \mathsf{\Sigma}^0_1 \cup \mathsf{\Pi}^0_1$?

  \newcommand{\MBWTS}{\textsc{MinBddWeakTileSet}}
  \newcommand{\MBDWTS}{\textsc{MinBddDirectedWeakTileSet}}

  \item The previous two problems have ``bounded'' variants:
      $$
      \MBWTS = \setr{\langle S,c,0^n \rangle}{
      \begin{minipage}{80mm}
        $S \in \mathcal{F}(\Z^2)$, $c\in\Z^+$, and $(\exists
        \calT=(T,\sigma,2))\; |T|\leq c$\linebreak and $\calT$ weakly self-assembles $S$
        and $(\forall \alpha\in\termasm{\calT})$\; $S_\alpha \subseteq \{0,\ldots,n-1\}^2$
      \end{minipage}}\,,
      $$
      and define $\MBDWTS$ similarly for the directed case.
      It is easy to show that $\MBWTS \in \spt$ and $\MBDWTS\in\NP$ using the same techniques used for strict self-assembly.
      Can it be shown that they are complete for these classes?
      This seems more difficult than the case of strict self-assembly, since the ``bounding box'' is now constrained to be a square, so that it is no longer possible to use the technique of forcing certain subshapes to be trees (whose tilings by minimal tile sets are well-characterized).


  \item In~\cite{ACGHKMR02} the authors show that for the special cases of tree and square shapes, the minimum directed tile set problem is in $\P$.  For trees, it is straightforward to verify that the minimum tile set is always directed, so the answer is the same whether or not we restrict attention to directed tile sets.  What is the complexity of the minimum tile set problem restricted to squares?  The polynomial-time algorithm given in~\cite{ACGHKMR02} crucially depends on the existence of a polynomial-time algorithm for the \emph{directed shape verification} problem of determining whether a given tile system strictly self-assembles a given shape and is directed. Removing the directed constraint on this shape verification problem, even when restricted to the case of squares, makes the problem $\coNP$-complete~\cite{GareyJohnson79,LewisPapadimitriou98,AGKS05}. Perhaps this means that the minimum tile set problem restricted to squares is hard as well.
      On the other hand, since this problem is sparse,\footnote{More precisely, if one takes a bit of care in encoding the problem, then it can be assumed sparse.
      %
      Assume that each square $S$ has its lower left-corner at the origin and is encoded by a list of its points in binary using precisely $\floor{\log |S|} + 1$ bits for each point, and the bound $c$ on the number of tile types is also encoded in binary using precisely $\floor{\log |S|} + 1$ bits.
      Then a sparse set that is $\equiv_\mathrm{m}^\mathsf{P}$-equivalent to the minimum tile set problem for squares is \[\setr{\pair{S}{c} \in \MTS}{S \text{ is an } n \times n \text{ square with lower-left corner $(0,0)$, and } 1 \leq c \leq n^2}\,.\] In fact we can even require $c \leq O(\log n / \log \log n)$ by a result of~\cite{AdChGoHu01}, but the trivial upper bound of $n^2$ suffices to obtain sparseness.}
      %
      Fortune's Theorem~\cite{Fortune79} implies that it cannot be  $\coNP$-hard (nor $\NP$-hard by Mahaney's Theorem~\cite{Mahaney82}) unless $\P = \NP$.

  %



\end{enumerate}

}

\opt{submission}{See \expref{Section}{subsec-open-problems} for related open problems.}

\opt{normal}{\openProblems}



\paragraph{Acknowledgement}
The authors are grateful to anonymous referees for their detailed and useful comments.


\bibliographystyle{tocplain}   %
%
%
%
%
\bibliography{v009a001}


%
%
%
%
\begin{tocauthors}
\begin{tocinfo}[nathaniel]
 Nathaniel Bryans\\
 Software Development Engineer in Test\\
 Microsoft, Inc.\\
 Redmond, Washington, USA\\
 nathbry\tocat{}microsoft\tocdot{}com%
\end{tocinfo}
\begin{tocinfo}[ehsan]
  Ehsan Chiniforooshan\\
  Software Engineer\\
  Google, Inc.\\
  Waterloo, Ontario, Canada\\
  chiniforooshan\tocat{}alumni\tocdot{}uwaterloo\tocdot{}ca%
\end{tocinfo}
\begin{tocinfo}[dave]
  David Doty\\
  Computing Innovation Fellow and Postdoctoral Scholar\\ 
  Computing and Mathematical Sciences\\
  California Institute of Technology \\
  Pasadena, California, USA\\
  ddoty\tocat{}caltech\tocdot{}edu\\
  \url{http://www.dna.caltech.edu/~ddoty/}
\end{tocinfo}
\begin{tocinfo}[lila]
  Lila Kari\\
  Professor, Computer Science\\
  University of Western Ontario \\
  London, Ontario, Canada\\
  lila\tocat{}csd\tocdot{}uwo\tocdot{}ca\\
  \url{http://www.csd.uwo.ca/~lila/}
\end{tocinfo}
\begin{tocinfo}[shin]
  Shinnosuke Seki\\
  Postdoctoral Scholar\\
  Information and Computer Science\\
  Aalto University\\
  Helsinki, Finland\\
  shinnosuke\tocdot{}seki\tocat{}aalto\tocdot{}fi\\
  \url{http://users.ics.aalto.fi/sseki/}
\end{tocinfo}
\end{tocauthors}

%
%
%
%
%
%
%
%
%
%
%
%
%

\begin{tocaboutauthors}

\begin{tocabout}[nathaniel]
\textsc{Nathaniel Bryans} received his B.\,Sc.\ in Bioinformatics at \href{http://www.uwo.ca}{The
University of Western Ontario} in 2012. He currently works at \href{http://www.microsoft.com}{Microsoft} as a Software Development Engineer in Test. In his free time, he enjoys hiking, skiing, and improving his minesweeper score.
\end{tocabout}

\begin{tocabout}[ehsan]
\textsc{Ehsan Chiniforooshan} received his M.\,Sc.\ from \href{http://www.sharif.ir/web/en/}{Sharif University of Technology}, advised by Rouzbeh Tusserkani, and his \phd\ from the \href{http://www.uwaterloo.ca/}{University of Waterloo} under the supervision of \href{http://www.cs.uwaterloo.ca/~nishi/}{Naomi Nishimura}. He has worked on problems in \href{http://arxiv.org/abs/1112.0376}{Combinatorics}, \href{http://onlinelibrary.wiley.com/doi/10.1002/jgt.20291/abstract}{Graph Theory}, \href{http://www.springerlink.com/content/al6klrulp4dvfnpb/}{Data Structures}, and \href{http://www.siam.org/proceedings/soda/2011/SODA11_046_bryans.pdf}{Self-Assembly}, is currently a Software Engineer at Google, Kitchener-Waterloo, and likes to bike and play table tennis and \href{http://www.pandanet-igs.com/}{Go}.
\end{tocabout}

\begin{tocabout}[dave]
\textsc{David Doty} received his \phd\ in \href{http://www.cs.iastate.edu}{Computer Science} at \href{http://www.iastate.edu}{Iowa State University}
in 2009; his advisors were \href{http://www.cs.iastate.edu/~lutz/}{Jack Lutz} and \href{http://www.cs.iastate.edu/~jil/}{Jim Lathrop}.
His thesis focused on applying the theory of computation to problems in molecular self-assembly. He lives in Pasadena, CA, where he works at \href{http://www.caltech.edu/}{Caltech} and continues to prove theorems related to molecular computation and conduct physical experiments implementing molecular computation.  When he is not proving theorems (and sometimes when he is), he can be found roaming the \href{http://en.wikipedia.org/wiki/San_Gabriel_Mountains}{San Gabriel mountains}, with or without a \href{http://www.mtbaldyskilifts.com/}{snowboard}, and sometimes \href{http://www.santamonica.com/visitors/what-to-do/beach/}{surfing}, \href{http://www.cooksillustrated.com/}{cooking}, or \href{http://settebello.net/}{eating}.
\end{tocabout}

\begin{tocabout}[lila]
\textsc{Lila Kari} is Professor in the \href{http://www.csd.uwo.ca}{Department of Computer Science} at \href{http://www.uwo.ca}{The
University of Western Ontario}, London, Ontario, Canada. She received her
M.\,Sc.\ in 1987 from the \href{http://www.unibuc.ro/e/}{Univesity of Bucharest}, Romania, and her \phd\ in
1991 from the \href{http://www.utu.fi/en/}{University of Turku}, Finland.  Her current research focuses %
on theoretical aspects of bioinformation and biocomputation, including
models of cellular computation, nanocomputation by DNA self-assembly, and Watson-Crick complementarity in formal languages.
\end{tocabout}

\begin{tocabout}[shin]
\textsc{Shinnosuke Seki} received his \phd\ in 2010 from the \href{http://www.csd.uwo.ca}{University of Western Ontario} under \href{http://www.csd.uwo.ca/lila}{Lila Kari}. His research interests include algorithmic self-assembly and algorithmic drug design. He also has a deep interest in history, especially ancient Roman history. He is now working at the \href{http://ics.aalto.fi/en/}{Department of Information and Computer Science}, \href{http://www.aalto.fi/en/}{Aalto University}.
\end{tocabout}

\end{tocaboutauthors}

\end{document}
