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

DOI10.1007/S10878-015-9975-6MaRDI QIDQ511695zbMATH OpenOpenAlexFDO

Authors Aleck Johnsen, Ming-Yang Kao, Shinnosuke Seki

Publication date 22 February 2017

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1409.1619

zbMATH Keywords

tile complexityDNA pattern self-assemblymanually-checkable proof

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Abstract: Patterned self-assembly tile set synthesis (PATS) aims at finding a minimum tile set to uniquely self-assemble a given rectangular (color) pattern. For k >= 1, k-PATS is a variant of PATS that restricts input patterns to those with at most $k$ colors. A computer-assisted proof has been recently proposed for 2-PATS by Kari et al. [arXiv:1404.0967 (2014)]. In contrast, the best known manually-checkable proof is for the NP-hardness of 29-PATS by Johnsen, Kao, and Seki [ISAAC 2013, LNCS 8283, pp.~699-710]. We propose a manually-checkable proof for the NP-hardness of 11-PATS.

Recommendations

• Synthesizing minimal tile sets for complex patterns in the framework of patterned DNA self-assembly
• Computing minimum tile sets to self-assemble color patterns
• Synthesizing minimal tile sets for complex patterns in the framework of patterned DNA self-assembly
• Combinatorial Optimization in Pattern Assembly

Cites work

• scientific article; zbMATH DE number 1101596 (Why is no real title available?)
• 3-color bounded patterned self-assembly (extended abstract)
• Combinatorial Optimization in Pattern Assembly
• Computing minimum tile sets to self-assemble color patterns
• DNA Computing
• Efficient 3-SAT algorithms in the tile assembly model
• Search methods for tile sets in patterned DNA self-assembly
• Solving NP-complete problems in the tile assembly model
• Solving satisfiability in the tile assembly model with a constant-size tileset
• Synthesizing minimal tile sets for complex patterns in the framework of patterned DNA self-assembly
• The complexity of satisfiability problems

Cited in

(1)

• 3-color bounded patterned self-assembly

This page was built for publication: A manually-checkable proof for the NP-hardness of 11-color pattern self-assembly tileset synthesis

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q511695)