Program Size and Temperature in Self-Assembly

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

File

Program Size and Temperature in Self-Assembly.pdf