Combinatorial optimization in pattern assembly (extended abstract). (English) Zbl 1381.68101

Seki, Shinnosuke

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].

MSC:

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