Difference between revisions of "Program Size and Temperature in Self-Assembly"
Jump to navigation
Jump to search
(Created page with "{{PaperTemplate |date=2011/12/08 |abstract=Asymptotic upper and lower bounds for the tile assembly complexity of NxN squares are known. But the precise number? Well, it's related...") |
m |
||
Line 3: | Line 3: | ||
|abstract=Asymptotic upper and lower bounds for the tile assembly complexity of NxN 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. | |abstract=Asymptotic upper and lower bounds for the tile assembly complexity of NxN 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 | + | |file=[http://www.dna.caltech.edu/Papers/minimal_tile_systems_ISAAC2011.pdf Program Size and Temperature in Self-Assembly] |
}} | }} |
Revision as of 12:37, 22 June 2021
Published on: 2011/12/08
Abstract
Asymptotic upper and lower bounds for the tile assembly complexity of NxN 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