Binary pattern tile set synthesis is NP-hard

DOI10.1007/s00453-016-0154-7zbMath1370.68109arXiv1404.0967OpenAlexW1589309006MaRDI QIDQ527409

Steffen Kopecki, Lila Kari, Matthew J. Patitz, Shinnosuke Seki, Pierre-Étienne Meunier

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

zbMATH Keywords

NP-hardnesscomputer-assisted proofpattern assemblyalgorithmic DNA self-assemblymassively-parallelized program

Mathematics Subject Classification ID

Cellular automata (computational aspects) (68Q80) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Combinatorial aspects of tessellation and tiling problems (05B45)

Related Items (6)

A manually-checkable proof for the NP-hardness of 11-color pattern self-assembly tileset synthesis ⋮ Binary pattern tile set synthesis is NP-hard ⋮ 3-color bounded patterned self-assembly ⋮ Unnamed Item ⋮ Reflections on tiles (in self-assembly) ⋮ The Complexity of Fixed-Height Patterned Tile Self-assembly

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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
• A manually-checkable proof for the NP-hardness of 11-color pattern self-assembly tileset synthesis
• Binary pattern tile set synthesis is NP-hard
• Computability and complexity in self-assembly
• Self-assembly of decidable sets
• Almost-natural proofs
• Every planar map is four colorable. I: Discharging
• Every planar map is four colorable. II: Reducibility
• 3-color bounded patterned self-assembly
• Study of the Kepler's conjecture: the problem of the closest packing
• Computing Minimum Tile Sets to Self-Assemble Color Patterns
• Intrinsic Universality in Self-Assembly
• A SAT Attack on the Erdős Discrepancy Conjecture
• Computer solution to the 17-point Erdős-Szekeres problem
• Minimum-weight triangulation is NP-hard
• Amplifying lower bounds by means of self-reducibility
• One Tile to Rule Them All: Simulating Any Tile Assembly System with a Single Universal Tile
• 3-Color Bounded Patterned Self-assembly
• Combinatorial Optimization in Pattern Assembly
• The Two-Handed Tile Assembly Model Is Not Intrinsically Universal
• Intrinsic universality in tile self-assembly requires cooperation
• The 24th Mersenne Prime
• DNA Computing
• Natural proofs

This page was built for publication: Binary pattern tile set synthesis is NP-hard