Optimal program-size complexity for self-assembly at temperature 1 in 3D

Original · EN

Working in a three-dimensional variant of Winfree's abstract Tile Assembly Model, we show that, for all N ∈ N, there is a tile set that uniquely self-assembles into an N × N square shape at temperature 1 with optimal program-size complexity of O(N / N) (the program-size complexity, also known as tile complexity, of a shape is the minimum number of unique tile types required to uniquely self-assemble it). Moreover, our construction is "just barely" 3D in the sense that it works even when the placement of tiles is restricted to the z = 0 and z = 1 planes. This result affirmatively answers an open question from Cook, Fu, Schweller (SODA 2011). To achieve this result, we develop a general 3D temperature 1 optimal encoding construction, reminiscent of the 2D temperature 2 optimal encoding construction of Soloveichik and Winfree (SICOMP 2007), and perhaps of independent interest.