Optimal Staged Self-assembly of Linear Assemblies

摘要

We analyze the complexity of building linear assemblies, sets of linear assemblies, and O(1)-scale general shapes in the staged tile assembly model. For systems with at most b bins and t tile types, we prove that the minimum number of stages to uniquely assemble a 1 × n line is Θ(log_t n + log_b n/t + 1). Generalizing to O(1) × n lines, we prove the minimum number of stages is O((log n-tb-t lot t)/b~2+(log log b)/(log t)) and Ω((log n-tb-t log t)/b~2). Next, we consider assembling sets of lines and general shapes using t = O(1) tile types. We prove that the minimum number of stages needed to assemble a set of k lines of size at most O(1) × n is O((k log n)/b~2+(k(log n)~(1/2))/b+log log n) and Ω((k log n)/b~2). In the case that b = O(k~(1/2)), the minimum number of stages is Θ(log n). The upper bound in this special case is then used to assemble "hefty" shapes of at least logarithmic edge-length-to-edge-count ratio at O(1)-scale using O(k~(1/2)) bins and optimal O(log n) stages.