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 journalArticlepeer-review

2 Scopus citations

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 k, k-pats is the subproblem of pats that restricts input patterns to those with at most k colors. We give an efficient [InlineEquation not available: see fulltext.] 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 (US)
Pages (from-to)496-529
Number of pages34
JournalJournal of Combinatorial Optimization
Volume33
Issue number2
DOIs
StatePublished - Feb 1 2017

Keywords

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

ASJC Scopus subject areas

  • Computer Science Applications
  • Discrete Mathematics and Combinatorics
  • Control and Optimization
  • Computational Theory and Mathematics
  • Applied Mathematics

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