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

Aleck Johnsen; Ming Yang Kao; Shinnosuke Seki

doi:10.1007/s10878-015-9975-6

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 journal › Article › Scientific › peer-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 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.

Original language	English
Pages (from-to)	496–529
Number of pages	34
Journal	JOURNAL OF COMBINATORIAL OPTIMIZATION
Volume	33
Issue number	2
Early online date	24 Nov 2015
DOIs	https://doi.org/10.1007/s10878-015-9975-6
Publication status	Published - 2017
MoE publication type	A1 Journal article-refereed

Keywords

DNA pattern self-assembly
Manually-checkable proof
Tile complexity

Access to Document

10.1007/s10878-015-9975-6

Link to publication in Scopus

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

@article{def9ac24050446f1be665bb2c377a800,

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 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 Kao, {Ming Yang} and Shinnosuke Seki",

year = "2017",

doi = "10.1007/s10878-015-9975-6",

language = "English",

volume = "33",

pages = "496–529",

journal = "JOURNAL OF COMBINATORIAL OPTIMIZATION",

issn = "1382-6905",

publisher = "Springer Netherlands",

number = "2",

}

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

Y1 - 2017

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

U2 - 10.1007/s10878-015-9975-6

DO - 10.1007/s10878-015-9975-6

M3 - Article

AN - SCOPUS:84948183978

VL - 33

SP - 496

EP - 529

JO - JOURNAL OF COMBINATORIAL OPTIMIZATION

JF - JOURNAL OF COMBINATORIAL OPTIMIZATION

SN - 1382-6905

IS - 2

ER -