2014/09/04 by Aleck Johnsen, Johnsen, Aleck, Ming-Yang Kao +3
Computer Science · #68Q17 #92B05 #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #cs.DM #msc:68Q17 #msc:92B05
paper · pdf · doi:10.48550/arxiv.1409.1619
arxiv created 2014/09/04 · arxiv updated 2014/09/08
Patterned self-assembly tile set synthesis (PATS) aims at finding a minimum tile set to uniquely self-assemble a given rectangular (color) pattern. For k >= 1, k-PATS is a variant of PATS that restricts input patterns to those with at most k colors. A computer-assisted proof has been recently proposed for 2-PATS by Kari et al. [arXiv:1404.0967 (2014)]. In contrast, the best known manually-checkable proof is for the NP-hardness of 29-PATS by Johnsen, Kao, and Seki [ISAAC 2013, LNCS 8283, pp.~699-710]. We propose a manually-checkable proof for the NP-hardness of 11-PATS.