Program Size and Temperature in Self-Assembly
Revision as of 12:37, 22 June 2021 by \('"2\)'"7
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
