Difference between revisions of "Program Size and Temperature in Self-Assembly"
Jump to navigation
Jump to search
m |
m |
||
| Line 1: | Line 1: | ||
{{PaperTemplate | {{PaperTemplate | ||
|date=2011/12/08 | |date=2011/12/08 | ||
| − | |abstract=Asymptotic upper and lower bounds for the tile assembly complexity of | + | |abstract=Asymptotic upper and lower bounds for the tile assembly complexity of $N x N$ squares are known. But the precise number? Well, it's related to the Kolmogorov complexity of the number $N$, and that's uncomputable. However, the relation is not tight, and a polynomial time algorithm to find the smallest tile program is known for "temperature" $T = 2$. Here, the authors generalize that result for all temperatures. |
|authors=Ho-Lin Chen, David Doty, and Shinnosuke Seki | |authors=Ho-Lin Chen, David Doty, and Shinnosuke Seki | ||
|file=[http://www.dna.caltech.edu/Papers/minimal_tile_systems_ISAAC2011.pdf Program Size and Temperature in Self-Assembly.pdf] | |file=[http://www.dna.caltech.edu/Papers/minimal_tile_systems_ISAAC2011.pdf Program Size and Temperature in Self-Assembly.pdf] | ||
}} | }} | ||
Latest revision as of 13:37, 22 June 2021
Published on: 2011/12/08
Abstract
Asymptotic upper and lower bounds for the tile assembly complexity of \(N x N\) squares are known. But the precise number? Well, it's related to the Kolmogorov complexity of the number \(N\), and that's uncomputable. However, the relation is not tight, and a polynomial time algorithm to find the smallest tile program is known for "temperature" \(T = 2\). Here, the authors generalize that result for all temperatures.
Authors
Ho-Lin Chen, David Doty, and Shinnosuke Seki
