2012/11/21 by Shinnosuke Seki, Seki, Shinnosuke, Yasushi Okuno +1
Biochemistry, Genetics and Molecular Biology · Engineering · #Advanced biosensing and bioanalysis techniques #Computational Complexity (cs.CC) #DNA and Biological Computing #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Modular Robots and Swarm Intelligence
paper · pdf · doi:10.48550/arxiv.1211.4949
openalex publication_date 2012/11/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Behaviors of Winfree's tile assembly systems (TASs) at high temperatures are investigated in combination with integer programming of a specific form called threshold programming. First, we propose a way to build bridges from the Boolean satisfiability problem (SAT) to threshold programming, and further to TAS's behavior, in order to prove the NP-hardness of optimizing temperatures of TASs that behave in a way given as input. These bridges will take us further to two important results on the behavior of TASs at high temperatures. The first says that arbitrarily high temperatures are required to assemble some shape by a TAS of "reasonable" size. The second is that for any temperature at least 4 given as a parameter, it is NP-hard to find the minimum size TAS that self-assembles a given shape and works at the given temperature or below.