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

Aleck Johnsen, Ming Yang Kao, Shinnosuke Seki*

*Tämän työn vastaava kirjoittaja

Tutkimustuotos: LehtiartikkeliArticleScientificvertaisarvioitu

2 Sitaatiot (Scopus)

Abstrakti

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.

AlkuperäiskieliEnglanti
Sivut496–529
Sivumäärä34
JulkaisuJOURNAL OF COMBINATORIAL OPTIMIZATION
Vuosikerta33
Numero2
Varhainen verkossa julkaisun päivämäärä24 marrask. 2015
DOI - pysyväislinkit
TilaJulkaistu - 2017
OKM-julkaisutyyppiA1 Julkaistu artikkeli, soviteltu

Sormenjälki

Sukella tutkimusaiheisiin 'A manually-checkable proof for the NP-hardness of 11-color pattern self-assembly tileset synthesis'. Ne muodostavat yhdessä ainutlaatuisen sormenjäljen.

Siteeraa tätä