2013/01/16 by Shinnosuke Seki, Seki, Shinnosuke
Biochemistry, Genetics and Molecular Biology · Computer Science · Engineering · Mathematics · #Advanced biosensing and bioanalysis techniques #Algorithm #Boolean satisfiability problem #Colored #Combinatorial optimization #Combinatorics #Computational Complexity (cs.CC) #Computer science #Constant (computer programming) #DNA and Biological Computing #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Materials science #Mathematical optimization #Mathematics #Modular Robots and Swarm Intelligence #Parameterized complexity #Satisfiability #Set (abstract data type) #Simple (philosophy) #Tile #cs.CC #cs.DS
paper · pdf · doi:10.48550/arxiv.1301.3771
arxiv created 2013/01/16 · openalex publication_date 2013/01/16 · arxiv updated 2013/01/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Pattern self-assembly tile set synthesis (PATS) is a combinatorial optimization problem which aim at minimizing a rectilinear tile assembly system (RTAS) that uniquely self-assembles a given rectangular pattern, and is known to be NP-hard. PATS gets practically meaningful when it is parameterized by a constant c such that any given pattern is guaranteed to contain at most c colors (c-PATS). We first investigate simple patterns and properties of minimum RTASs for them. Then based on them, we design a 59-colored pattern to which 3SAT is reduced, and prove that 59-PATS is NP-hard.