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

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