2013/12/02 by Pierre-Étienne Meunier, Meunier, Pierre-Étienne · 1 citation
Biochemistry, Genetics and Molecular Biology · Engineering · #Advanced biosensing and bioanalysis techniques #Biosensors and Analytical Detection #Computational Complexity (cs.CC) #Computational Geometry (cs.CG) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Modular Robots and Swarm Intelligence
paper · pdf · doi:10.48550/arxiv.1312.1299
openalex publication_date 2013/12/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We prove that the number of tile types required to build squares of size n x n, in Winfree's abstract Tile Assembly Model, when restricted to using only non-cooperative tile bindings, is at least 2n-1, which is also the best known upper bound. Non-cooperative self-assembly, also known as temperature 1, is where tiles bind to each other if they match on one or more sides, whereas in cooperative binding, some tiles can bind only if they match on multiple sides. Our proof introduces a new programming technique for temperature 1, that disproves the very intuitive and commonly held belief that, in the same model, assembling paths between two points A and B cannot be done with less tile types than the Manhattan distance between them. Then, we prove a necessary condition for these "efficient paths" to be assembled, and show that this necessary condition cannot hold in completely filled squares. This result proves the oldest conjecture in algorithmic self-assembly, published by Rothemund and Winfree in STOC 2000, in the case where growth starts from a corner of the square. As a corollary, we establish n as a lower bound on the tile complexity of the general case. The problem of determining the minimal number of tile types to self-assemble a shape is known to be Sigmap2-complete.