Difference between revisions of "Building finite shapes in the aTAM"
Jhendricks (talk | contribs) (Created page with "__TOC__ ==Building finite shapes== In order to build any given finite shape, it is trivial to define a tile assembly system which will self-assemble it: simply create a unique ...") |
m (moved Building finite shapes to Building finite shapes in the aTAM) |
||
| (10 intermediate revisions by 2 users not shown) | |||
| Line 4: | Line 4: | ||
In order to build any given finite shape, it is trivial to define a tile assembly system which will self-assemble it: simply create a unique tile type for every point in the shape so that the glue between each tile and each neighbor is unique to that pair in that location. Obviously, however, this is the worst possible construction in terms of tile type complexity. Soloveichik and Wifree, in <ref name=SolWin07/>, showed that as long as the shape can be scaled up (meaning that every point in the original shape is replaced by a square block of tiles of some fixed dimension) the tile type complexity for a finite shape $S$ is bounded above and below by the Kolmogorov complexity of the shape. The Kolmogorov complexity of $S$, denoted $K(S)$, is the length in bits of the shortest program which, when run by a universal Turing machine, outputs exactly the points of $S$ and then halts. They showed that the tile complexity of $S$ is $\Theta\left(\frac{K(S)}{\log K(S)}\right)$ by showing that the lower bound holds because otherwise it would contradict the Kolmogorov complexity of the shape, and for the upper bound they provided a construction in which a Turing machine is simulated inside of each scaled up block to read a compressed definition of $S$ and determine which neighboring locations should have blocks filled in and then passing the program into those blocks and simulating the Turing machine within them, etc. Therefore, the scaling factor $c$ is proportional to the running time of the Turing machine (and thus can be very large), and the tile complexity arises from the compressed definition of $S$. | In order to build any given finite shape, it is trivial to define a tile assembly system which will self-assemble it: simply create a unique tile type for every point in the shape so that the glue between each tile and each neighbor is unique to that pair in that location. Obviously, however, this is the worst possible construction in terms of tile type complexity. Soloveichik and Wifree, in <ref name=SolWin07/>, showed that as long as the shape can be scaled up (meaning that every point in the original shape is replaced by a square block of tiles of some fixed dimension) the tile type complexity for a finite shape $S$ is bounded above and below by the Kolmogorov complexity of the shape. The Kolmogorov complexity of $S$, denoted $K(S)$, is the length in bits of the shortest program which, when run by a universal Turing machine, outputs exactly the points of $S$ and then halts. They showed that the tile complexity of $S$ is $\Theta\left(\frac{K(S)}{\log K(S)}\right)$ by showing that the lower bound holds because otherwise it would contradict the Kolmogorov complexity of the shape, and for the upper bound they provided a construction in which a Turing machine is simulated inside of each scaled up block to read a compressed definition of $S$ and determine which neighboring locations should have blocks filled in and then passing the program into those blocks and simulating the Turing machine within them, etc. Therefore, the scaling factor $c$ is proportional to the running time of the Turing machine (and thus can be very large), and the tile complexity arises from the compressed definition of $S$. | ||
| + | |||
| + | Another interesting aspect to the tile complexity of finite shapes was demonstrated by Bryans, Chiniforooshan, Doty, Kari, and Seki in <ref name=BryChiDotKarSek10/> where they showed that there exist finite shapes which can self-assemble more tile type efficiently by nondeterministic systems than by deterministic, or directed, systems. Both types of systems always create the exact same shape, but where a directed system does so by ensuring that no matter which assembly sequence is followed, a given location always receives a tile of the same type, a nondeterministic system may allow tiles of differing types to occupy a particular position based on the assembly sequence followed. They also showed that the problem of determining the minimum number of tile types which are required to uniquely assemble a given finite shape, if the system isn't constrained to being directed, is complete for the complexity class $\Sigma^P_2 = NP^{NP}$, while it was shown by Adleman, Cheng, Goel, Huang, Kempe, Moisset de Espanés, and Rothemund in <ref name=ACGHKMR02/> to be NP-complete for directed systems. These results suggest that such nondeterminism adds power and complexity to the aTAM. | ||
==References== | ==References== | ||
<references> | <references> | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
<ref name =SolWin07><bibtex> | <ref name =SolWin07><bibtex> | ||
| Line 84: | Line 26: | ||
</bibtex></ref> | </bibtex></ref> | ||
| + | <ref name =BryChiDotKarSek10><bibtex> | ||
| + | @inproceedings{BryChiDotKarSek10, | ||
| + | author = {Nathaniel Bryans, Ehsan Chiniforooshan, David Doty, Lila Kari, and Shinnosuke Seki}, | ||
| + | title = {The power of nondeterminism in self-assembly}, | ||
| + | booktitle = {SODA '11: Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms}, | ||
| + | year = {2011}, | ||
| + | pages = {590--602}, | ||
| + | } | ||
| + | </bibtex></ref> | ||
| + | |||
| + | <ref name =ACGHKMR02><bibtex> | ||
| + | @inproceedings{ACGHKMR02, | ||
| + | author = {eonard M. Adleman, Qi~Cheng, Ashish Goel, Ming-Deh A. Huang, David Kempe, Pablo~Moisset de Espanés, and Paul W. K. Rothemund, | ||
| + | title = {Combinatorial optimization problems in self-assembly}, | ||
| + | booktitle = {Proceedings of the Thirty-Fourth Annual ACM Symposium on Theory of Computing}, | ||
| + | year = {2002}, | ||
| + | pages = {23--32}, | ||
| + | } | ||
| + | </bibtex></ref> | ||
</references> | </references> | ||
| + | |||
| + | [[Category:Results in the aTAM]] | ||
| + | [[Category:Self-assembly]] | ||
Latest revision as of 14:57, 27 May 2014
Contents
Building finite shapes
In order to build any given finite shape, it is trivial to define a tile assembly system which will self-assemble it: simply create a unique tile type for every point in the shape so that the glue between each tile and each neighbor is unique to that pair in that location. Obviously, however, this is the worst possible construction in terms of tile type complexity. Soloveichik and Wifree, in [1], showed that as long as the shape can be scaled up (meaning that every point in the original shape is replaced by a square block of tiles of some fixed dimension) the tile type complexity for a finite shape \(S\) is bounded above and below by the Kolmogorov complexity of the shape. The Kolmogorov complexity of \(S\), denoted \(K(S)\), is the length in bits of the shortest program which, when run by a universal Turing machine, outputs exactly the points of \(S\) and then halts. They showed that the tile complexity of \(S\) is \(\Theta\left(\frac{K(S)}{\log K(S)}\right)\) by showing that the lower bound holds because otherwise it would contradict the Kolmogorov complexity of the shape, and for the upper bound they provided a construction in which a Turing machine is simulated inside of each scaled up block to read a compressed definition of \(S\) and determine which neighboring locations should have blocks filled in and then passing the program into those blocks and simulating the Turing machine within them, etc. Therefore, the scaling factor \(c\) is proportional to the running time of the Turing machine (and thus can be very large), and the tile complexity arises from the compressed definition of \(S\).
Another interesting aspect to the tile complexity of finite shapes was demonstrated by Bryans, Chiniforooshan, Doty, Kari, and Seki in [2] where they showed that there exist finite shapes which can self-assemble more tile type efficiently by nondeterministic systems than by deterministic, or directed, systems. Both types of systems always create the exact same shape, but where a directed system does so by ensuring that no matter which assembly sequence is followed, a given location always receives a tile of the same type, a nondeterministic system may allow tiles of differing types to occupy a particular position based on the assembly sequence followed. They also showed that the problem of determining the minimum number of tile types which are required to uniquely assemble a given finite shape, if the system isn't constrained to being directed, is complete for the complexity class \(\Sigma^P_2 = NP^{NP}\), while it was shown by Adleman, Cheng, Goel, Huang, Kempe, Moisset de Espanés, and Rothemund in [3] to be NP-complete for directed systems. These results suggest that such nondeterminism adds power and complexity to the aTAM.
References
- ↑
David Soloveichik, Erik Winfree - Complexity of Self-Assembled Shapes
- SIAM Journal on Computing 36(6):1544-1569,2007
- BibtexAuthor : David Soloveichik, Erik Winfree
Title : Complexity of Self-Assembled Shapes
In : SIAM Journal on Computing -
Address :
Date : 2007
- ↑
Nathaniel Bryans, Ehsan Chiniforooshan, David Doty, Lila Kari,, Shinnosuke Seki - The power of nondeterminism in self-assembly
- SODA '11: Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms pp. 590--602,2011
- BibtexAuthor : Nathaniel Bryans, Ehsan Chiniforooshan, David Doty, Lila Kari,, Shinnosuke Seki
Title : The power of nondeterminism in self-assembly
In : SODA '11: Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms -
Address :
Date : 2011
- ↑
eonard M. Adleman, Qi~Cheng, Ashish Goel, Ming-Deh A. Huang, David Kempe, Pablo~Moisset de Espanés,, Paul W. K. Rothemund,
title = {Combinatorial optimization problems in self-assembly},
booktitle = {Proceedings of the Thirty-Fourth Annual ACM Symposium on Theory of Computing},
year = {2002},
pages = {23--32}, -
