A manually-checkable proof for the NP-hardness of 11-color pattern self-assembly tileset synthesis

摘要

Patterned self-assembly tile set synthesis (pats) aims at minimizing the number of distinct DNA tile types used to self-assemble a given rectangular color pattern. For an integer k, k-pats is the subproblem of pats that restricts input patterns to those with at most k colors. We give an efficient verifier, and based on that, we establish a manually-checkable proof for the NP-hardness of 11-pats; the best previous manually-checkable proof is for 29-pats.