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

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

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)

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

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)