A manually-checkable proof for the NP-hardness of 11-color pattern self-assembly tileset synthesis
From MaRDI portal
Publication:511695
DOI10.1007/S10878-015-9975-6zbMATH Open1361.90050arXiv1409.1619OpenAlexW1484881446MaRDI QIDQ511695FDOQ511695
Shinnosuke Seki, Aleck Johnsen, Ming-Yang Kao
Publication date: 22 February 2017
Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)
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 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.
Full work available at URL: https://arxiv.org/abs/1409.1619
Cites Work
- Title not available (Why is that?)
- Combinatorial Optimization in Pattern Assembly
- Solving NP-complete problems in the tile assembly model
- The complexity of satisfiability problems
- Synthesizing minimal tile sets for complex patterns in the framework of patterned DNA self-assembly
- Search methods for tile sets in patterned DNA self-assembly
- Efficient 3-SAT algorithms in the tile assembly model
- Computing Minimum Tile Sets to Self-Assemble Color Patterns
- Solving satisfiability in the tile assembly model with a constant-size tileset
- 3-Color Bounded Patterned Self-assembly
- Binary pattern tile set synthesis is NP-hard
- DNA Computing
Cited In (3)
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)
