Another model relaxes the assumption of constant temperature over time: temperature programming, in which the temperature is raised and lowered over many stages, with each stage assumed to reach a terminal state before changing the temperature for the next stage. Aggarwal et al. 5 proved that with one temperature change, a thin rectangle—an n × k rectangle where k < log n log log n – log log log n —can be assembled from O( log n log log n) tile types, compared to a provable lower bound of Ω( n1/k k ) in the standard aTAM. Kao and Schweller31 showed that O( 1) tile types suffice to assemble any n × n square using O(log n) temperature changes. Summers53 showed that O( 1) tile types suffices to assemble any shape (scaled up) using temperature programming, using two constructions. In the first, the number of temperature changes is O(|S|), and the scaling factor is O( 1). In the second, the number of temperature changes is O(K(S)) (the Kolmogorov complexity of S), and the scaling factor is proportional to the running time of the shortest program for S.

Randomized self-assembly uses the
inherent nondeterminism in the a TAM
in which multiple tile types compete to
bind to a single binding site, and tile
type concentrations determine the
probability of a tile type attaching to
a binding site when it competes with
others sharing the same input glues.
Chandran, Gopalkrishnan, and Reif12
showed that the tile complexity of a 1
× n line is Θ(log n) in the randomized
model, that is, Θ(log n) tile types are
sufficient and necessary to assemble a
line of expected length n (compared to
n tile types that are provably necessary
in the deterministic aTAM). In fact,
their tile system is equimolar: all tile
types have equal concentrations. Beck-
er, Rapaport, and Rémila9 introduced
the model of concentration program-
ming, in which concentrations of tile
types are used to program input to the
system. Kao and Schweller32 showed
that for each δ,ε > 0, there is a single tile
system T so that, for every n ∈ Z+, there
is a setting of concentrations that cause
T to assemble an n′ × n′ square, where
( 1 – ε) n ≤ n′ ≤ ( 1 + ε)n with probability at
least 1 − δ. That is, the square is probably
approximately assembled. Doty23 im-
proved this result, showing that for each
δ > 0, a single tile system can be used to
assemble an exactly n × n square for any
n ∈ Z+ with probability at least 1 − δ us-
ing concentration programming.

computational complexity

Rather than manually analyzing each new shape or class of shapes to determine its tile complexity, it would be beneficial to develop an algorithm that automates the task: given a finite shape S, it outputs the smallest tile system that uniquely assembles S. Unfortunately, an efficient algorithm is unlikely to exist: Adleman et al. 3 showed that the problem is NP-complete. Here, “uniquely assembles S” means, assembles one unique terminal assembly, whose shape is S. One could object that a tile system deterministi-cally assembles S if it produces many terminal assemblies that all have the shape S. Under this definition, Bryans et al. 10 showed that the problem, in a sense, is even harder: NPNP-complete, that is, NP-complete for algorithms that have access to a constant-time subroutine for an NP-complete problem such as SAT.

In addition to optimization prob-
lems, there are important verification
problems of interest in tile assembly.
One easy problem is this: given a tile
system T and a (possibly nontermi-
nal) assembly α, can T produce α One
can simply add tiles to the seed that
are consistent with α and have suf-
ficient binding strength until either
α is complete, or until no more tiles
can be added; the answer is “yes” in
the former case and “no” in the latter.
A more challenging question: Is α the
unique terminal assembly produced
by T A tile system could produce α
through an exponential number of
different pathways (orders of tile ad-
dition), so it would naïvely seem to
require that we check all of them to
ensure none of them create a different
terminal assembly. However, Adleman
et al. 3 showed this problem is solvable
in quadratic time. On the other hand,
in the hierarchical aTAM (in which
two large assemblies are allowed to
attach), the problem of determining
whether α is uniquely assembled is
coNP-complete. 11 This is discouraging,
since such decision problems are a
formalization of the practically impor-
tant task of “write a simulator for the
hierarchical a TAM.”
Shape building is one goal of self-
assembly; another is pattern painting.
Briefly, we paint some tile types black
(for example, by attaching a strepta-
vidin marker molecule) and say the
pattern assembled is the set of posi-
tions in the final assembly with a black
tile. Such a definition is appropriate
for modeling practical goals such as
self-assembled circuit layouts, such as
those studied by Cook, Winfree, and
Rothemund. 19 Although the proof tech-
niques for these verification problems
generalize easily to pattern assembly,
it remains open to prove or disprove
pattern assembly analogues of the op-
timization results noted here. The opti-
mization problems are uncomputable
if the tile system is allowed to grow ar-
bitrarily far outside the pattern, using
the same argument that shows Kol-
mogorov complexity is uncomputable.
If the minimum tile system to assem-
ble a given finite pattern could be com-
puted, then this computation could be
simulated in the second quadrant by a
tile system of size O( 1) + log n search-
ing for the first pattern on the positive
x-axis that requires more than n tile