Program Size and Temperature in Self-Assembly

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

File

Program Size and Temperature in Self-Assembly.pdf