Anzeige
Erschienen in:
2015 | OriginalPaper | Buchkapitel
Optimal Program-Size Complexity for Self-Assembly at Temperature 1 in 3D
verfasst von : David Furcy, Samuel Micka, Scott M. Summers
Erschienen in: DNA Computing and Molecular Programming
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
Working in a three-dimensional variant of Winfree’s abstract Tile Assembly Model, we show that, for all \(N \in \mathbb {N}\), there is a tile set that uniquely self-assembles into an \(N \times N\) square shape at temperature 1 with optimal program-size complexity of \(O(\log N / \log \log 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.