  Winfree's abstract Tile Assembly Model (aTAM) is a model of molecular
self-assembly of DNA complexes known as tiles, which float freely in solution
and attach one at a time to a growing "seed" assembly based on specific binding
sites on their four sides. We show that there is a polynomial-time algorithm
that, given an n x n square, finds the minimal tile system (i.e., the system
with the smallest number of distinct tile types) that uniquely self-assembles
the square, answering an open question of Adleman, Cheng, Goel, Huang, Kempe,
Moisset de Espanes, and Rothemund ("Combinatorial Optimization Problems in
Self-Assembly", STOC 2002). Our investigation leading to this algorithm reveals
other positive and negative results about the relationship between the size of
a tile system and its "temperature" (the binding strength threshold required
for a tile to attach).
