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

DOI10.1007/978-3-319-21999-8_5zbMATH Open1364.68195arXiv1411.1122OpenAlexW1760628847MaRDI QIDQ2948409FDOQ2948409

Authors: David Furcy, Samuel Micka, Scott M. Summers 

Publication date: 30 September 2015

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Abstract: Working in a three-dimensional variant of Winfree's abstract Tile Assembly Model, we show that, for all $NinmathbbN$, there is a tile set that uniquely self-assembles into an $NimesN$ square shape at temperature 1 with optimal program-size complexity of $O(logN/loglogN)$ (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.

Full work available at URL: https://arxiv.org/abs/1411.1122

Recommendations

• Optimal program-size complexity for self-assembled squares at temperature 1 in 3D
• Optimal self-assembly of finite shapes at temperature 1 in 3D
• Optimal self-assembly of finite shapes at temperature 1 in 3D
• Program size and temperature in self-assembly
• Program size and temperature in self-assembly

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10)

Cites Work

• The program-size complexity of self-assembled squares (extended abstract)
• Running time and program size for self-assembled squares
• Temperature 1 self-assembly: deterministic assembly in 3D and probabilistic assembly in 2D
• Complexity of Self‐Assembled Shapes
• Limitations of self-assembly at temperature 1
• An introduction to Kolmogorov complexity and its applications

Cited In (10)

• Program size and temperature in self-assembly
• Optimal staged self-assembly of general shapes
• On the effects of hierarchical self-assembly for reducing program-size complexity
• Temperature 1 self-assembly: deterministic assembly in 3D and probabilistic assembly in 2D
• Reducing tile complexity for self-assembly through temperature programming
• New bounds on the tile complexity of thin rectangles at temperature-1
• The program-size complexity of self-assembled squares (extended abstract)
• Optimal self-assembly of finite shapes at temperature 1 in 3D
• Self-assembly of and optimal encoding within thin rectangles at temperature-1 in 3D
• Optimal program-size complexity for self-assembled squares at temperature 1 in 3D

This page was built for publication: Optimal program-size complexity for self-assembly at temperature 1 in 3D

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2948409)