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

Aleck Johnsen, Ming Yang Kao, Shinnosuke Seki*

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

2 Citations (Scopus)

Abstract

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

Original languageEnglish
Pages (from-to)496–529
Number of pages34
JournalJOURNAL OF COMBINATORIAL OPTIMIZATION
Volume33
Issue number2
Early online date24 Nov 2015
DOIs
Publication statusPublished - 2017
MoE publication typeA1 Journal article-refereed

Keywords

  • DNA pattern self-assembly
  • Manually-checkable proof
  • Tile complexity

Fingerprint Dive into the research topics of 'A manually-checkable proof for the NP-hardness of 11-color pattern self-assembly tileset synthesis'. Together they form a unique fingerprint.

Cite this