types to assemble, at which point the tile system could grow back to the x- axis assemble that pattern, a contradiction. So to establish (for instance) NP- completeness requires also specifying a bounding box as part of the input and requiring that the assembled shape is a subset of the bounding box. Göös and Orponen30 and Lempiäinen, Czeizler, and Orponen35 developed branch-and-bound algorithms for a variant of this problem, but these algorithms require exponential time.

One can also consider the assembly of infinite patterns (as in Figure 2d) as the “computability-theoretic” version of self-assembly. Lathrop et al. 34 showed that not every computable pattern ( subset of Z2) can be self-assembled, since each time step of computation with tiles irreversibly occupies a point in space, and for some patterns, it requires strictly more time to compute whether that point is part of the pattern. However, with regard to one-dimensional patterns, Patitz and Summers42 showed that every computable subset of N can be self-assembled on the x-axis ( crucially using the fact that the assembly occupies a large area outside the x-axis where the actual computation happens). Lathrop et al. 34 showed a weaker result for computably enumerable sets: there is a simple quadratically bounded function f: N → N such that, for every computably enumerable A ⊆ N, f (A) can be self-assembled on the x-axis.

assembly time complexity
Another resource bound to consider
is the time required to build a shape
(as determined by stochastic chemi-
cal kinetics). There is a linear amount
of parallelism available for assem-
bling a shape of size N in fewer than N
steps. This is because the frontier (set
of potential binding sites) of an as-
sembly of size N is potentially as large
as O(N), and in a given unit of time, a
constant fraction of the frontier will
have tiles attach if tile types are suf-
ficiently concentrated. Adleman et al. 2
showed that any shape of diameter D
requires time Ω(D) to assemble from a
deterministic tile system in the a TAM,
later shown by Chen and Doty13 to
hold for nondeterministic systems.
Adleman et al. 2 showed that this lower
bound is tight for the assembly of n ×
n squares, that is, they can be assem-
bled in time O(n), achievable using
the information-theoretically optimal
O(log n / log log n) tile types. Reif43 also
studied local parallelism within the
seeded a TAM, for the purpose of com-
putation rather than shape-building.
Reif showed that for many problems
such as prefix sum and bitonic merge,
it is possible to design a tile system
that solves the problem using the
optimal parallel speedup. Reif used
a generalization of the model known
as step assembly, in which tile types
are added to a test tube in a series of
steps, with each step assumed to run
to completion before washing away
remaining unbound tiles, before add-
ing new tile types.

 

intrinsic universality Doty et al. 24 showed a different notion of universality, with respect to growth rather than computation, constructing a single tile set U that simulates any tile system T, by choosing an appropriate seed assembly to encode T using tiles from U. The simulation is intrinsic in the sense that the self-assembly process carried out by U is exactly that carried out by T, with each tile of T represented by an m × m block of U tiles. Therefore there is a single tile set that can (modulo rescaling) carry out any self-assembly process that can be achieved by any tile system. The challenge is to program all this activity without ever blocking a path that may later be needed for intra-block communication, since no block representing a tile is necessarily aware of the identities of its neighboring blocks, whether they are even present, and if not, whether they will ever arrive.

 

Power of cooperative binding Cooperative binding is used crucially in all non-trivial constructions in the aTAM. It is also the most challenging aspect of the model to enforce experimentally, so it is reasonable to question its necessity in algorithmic self-assembly. Doty, Patitz, and Summers27 investigated the power of temperature 1 self-assembly in the a TAM, in which all positive glue strengths have sufficient energy to bind a tile, which effectively inhibits the use of cooperative binding. They show that a wide class of deterministic tile systems, satisfying a condition known as pumpability, are incapable of universal computation in the sense that they self-assemble only “periodic” ( semi-linear) sets. They conjecture that all deterministic, temperature 1 tile systems are pumpable. Maňuch, Stacho, and Stoll38 obtained similar results studying temperature 1 tile systems that assemble finite assemblies and