Binary pattern tile set synthesis is NP-hard
From MaRDI portal
DOI10.1007/s00453-016-0154-7zbMath1370.68109arXiv1404.0967MaRDI QIDQ527409
Lila Kari, Shinnosuke Seki, Steffen Kopecki, Pierre-Étienne Meunier, Matthew J. Patitz
Publication date: 11 May 2017
Published in: Algorithmica, Automata, Languages, and Programming (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1404.0967
NP-hardness; computer-assisted proof; pattern assembly; algorithmic DNA self-assembly; massively-parallelized program
68Q80: Cellular automata (computational aspects)
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
05B45: Combinatorial aspects of tessellation and tiling problems