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 journalArticle

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

Fingerprint

NP-hardness
Self-assembly
Tile
Self assembly
Hardness
Synthesis
Color
DNA
Distinct
Integer

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

Cite this

@article{ef0bf74182834ad2bb7f95ab88f6ae7e,
title = "A manually-checkable proof for the NP-hardness of 11-color pattern self-assembly tileset synthesis",
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.",
keywords = "DNA pattern self-assembly, Manually-checkable proof, Tile complexity",
author = "Aleck Johnsen and Ming-Yang Kao and Shinnosuke Seki",
year = "2017",
month = "2",
day = "1",
doi = "10.1007/s10878-015-9975-6",
language = "English (US)",
volume = "33",
pages = "496--529",
journal = "Journal of Combinatorial Optimization",
issn = "1382-6905",
publisher = "Springer Netherlands",
number = "2",

}

A manually-checkable proof for the NP-hardness of 11-color pattern self-assembly tileset synthesis. / Johnsen, Aleck; Kao, Ming-Yang; Seki, Shinnosuke.

In: Journal of Combinatorial Optimization, Vol. 33, No. 2, 01.02.2017, p. 496-529.

Research output: Contribution to journalArticle

TY - JOUR

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

AU - Johnsen, Aleck

AU - Kao, Ming-Yang

AU - Seki, Shinnosuke

PY - 2017/2/1

Y1 - 2017/2/1

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

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

KW - DNA pattern self-assembly

KW - Manually-checkable proof

KW - Tile complexity

UR - http://www.scopus.com/inward/record.url?scp=84948183978&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84948183978&partnerID=8YFLogxK

U2 - 10.1007/s10878-015-9975-6

DO - 10.1007/s10878-015-9975-6

M3 - Article

VL - 33

SP - 496

EP - 529

JO - Journal of Combinatorial Optimization

JF - Journal of Combinatorial Optimization

SN - 1382-6905

IS - 2

ER -