zbMATH — the first resource for mathematics

Combinatorial optimization in pattern assembly (extended abstract). (English) Zbl 1381.68101
Mauri, Giancarlo (ed.) et al., Unconventional computation and natural computation. 12th international conference, UCNC 2013, Milan, Italy, July 1–5, 2013. Proceedings. Berlin: Springer (ISBN 978-3-642-39073-9/pbk). Lecture Notes in Computer Science 7956, 220-231 (2013).
Summary: Pattern self-assembly tile set synthesis (PATS) is an NP-hard combinatorial problem to minimize a rectilinear tile assembly system (RTAS) that uniquely self-assembles a given rectangular pattern. For \(c \geq 1\), \(c\)-PATS is a subproblem of PATS which takes only the patterns with at most \(c\) colors as input. We propose a polynomial-time reduction of 3SAT to 60-PATS in order to prove that 60-PATS is NP-hard.
For the entire collection see [Zbl 1264.68006].

68Q25 Analysis of algorithms and problem complexity
68Q05 Models of computation (Turing machines, etc.) (MSC2010)
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
90C27 Combinatorial optimization
Full Text: DOI