Open Problems

The following is a partial list of some of the many open problems in self-assembly:

• In his 1998 thesis , Winfree showed that the class of directed aTAM systems at temperature 2 is computationally universal, and in Cook et al. showed that undirected temperature 1 aTAM systems could perform computations with a given amount of certainty. They also showed that in 2 planes directed aTAM temperature 1 systems are computationally universal. Is the class of directed aTAM systems at temperature 1 in the plane computationally universal? In Doty, Patitz, and Summers provide insights into this question.
SOLVED
• Can \(n \times n\) squares efficiently self-assemble at temperature 1 (i.e. can less than \(O(n)\) tile types be used)?
• In , Doty et al. introduced a model known as the fuzzy temperature model and showed that in this model n by n squares could efficiently self-assemble. Can systems in this model also perform general computation?
• In Exact Shapes and Turing Universality at Temperature 1 with a Single Negative Glue, Patitz et al. introduced the ``restricted glue TAM`` (rgTAM), a version of the aTAM in which a single glue whose strength is -1 (i.e. it is repulsive) is allowed, and all other glues must be strength 1. They showed that it is computationally universal. However, is a 2HAM version of the rgTAM also computationally universal?
SOLVED
• In Doty et al. showed that the aTAM is intrinsically universal for itself, but for directed systems the intrinsically universal tile set fundamentally relies on nondeterminism. Is the class of directed aTAM systems intrinsically universal for itself?
SOLVED
• Is the STAM intrinsically universal for itself? Also, in it was shown that the 3D aTAM is IU for a subset of the STAM, but it remains open whether or not adding negative strength glues allows the 3D aTAM to be IU for the full STAM. Additionally related to the STAM, for every Staged Assembly Model system is there an STAM system which can simulate it?
• Is the class of aTAM systems at temperature 1 intrinsically universal for itself?
SOLVED
• In his 1998 thesis , Winfree introduced both the aTAM and its more practical counterpart the kTAM. Currently, the 2HAM does not have a more realistic counterpart. Formulate a "k2HAM" model which takes into account the size of assemblies binding together (the bigger the assemblies the less likely it is they will bind together) and the lack of rigidity when assemblies come together.
• In Self-Assembly of Discrete Self-Similar Fractals, Patitz and Summers proved several results about self-assembling discrete self-similar fractals, but it is still an open questions as to whether or not there exists a discrete self-similar fractal that can be self-assembled in the aTAM. Also, are there discrete self-similar fractals which are not pinch-point fractals that are provably impossible to strictly self-assemble (e.g. the Sierpinski carpet)?
SOLVED
• In Self-Assembly with Geometric Tiles, a construction was shown in which 2D tiles with disconnected geometries which are forced to stay within the plane as they combine, are capable of assembling n by n squares using only \(O(\log(\log(n)))\) tile types. Can a similar construction be shown with connected geometries (and staying in 2D)?
• In Computability and Complexity in Self-Assembly, it was shown that for every computably enumerable language \(L \subset \mathbb{N}\), a pattern representing \(L\) weakly self-assembles along the x-axis, but with the points spread out roughly quadratically. Can those points instead be spread out by only a constant factor? (Or with no space between them as with decidable languages as shown in Self-Assembly of Decidable Sets?)
• In One Tile to Rule Them All: Simulating Any Turing Machine, Tile Assembly System, or Tiling System with a Single Puzzle Piece, Demaine et al. showed that it is possible to turn any aTAM system into a single rotatable (non-square) tile which simulates it. They also showed how to adapt this result to convert any of a variety of plane tiling systems (such as Wang tiles) into a "nearly" plane tiling system with a single tile (but with small gaps between the tiles). An open question is whether or not this can be improved to result in a system which fully tiles the plane. (This has been an open problem in tiling theory for many years.)
• In Two Hands Are Better Than One (up to constant factors), among other results, Cannon et al. proved that in the 3D 2HAM, if you are given a system \(\mathcal{T}\) and an assembly \(\alpha\), it is co-NP complete to determine if \(\alpha\) is the unique terminal assembly of \(\mathcal{T}\). It remains open what the complexity of this problem is in 2D. In the same paper, they showed how any aTAM system can be simulated by a 2HAM system at scale factor 5. It remains open how small this scale factor can actually be.
SOLVED

References