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

DOI10.1007/978-3-319-21999-8_5MaRDI QIDQ2948409zbMATH OpenOpenAlexFDO

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)

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

Mathematics Subject Classification ID

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

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.

Recommendations

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

Cites work

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

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)
• Program size and temperature in self-assembly
• 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)