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 ≥ 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.
展开▼
