Binary pattern tile set synthesis is NP-hard

DOI10.1007/978-3-662-47672-7_83zbMATH Open1370.68109arXiv1404.0967OpenAlexW1589309006MaRDI QIDQ527409FDOQ527409

Authors: Lila Kari, Steffen Kopecki, Pierre Meunier, Matthew J. Patitz, Shinnosuke Seki 

Publication date: 11 May 2017

Published in: Algorithmica, Automata, Languages, and Programming (Search for Journal in Brave)

Abstract: In the field of algorithmic self-assembly, a long-standing unproven conjecture has been that of the NP-hardness of binary pattern tile set synthesis (2-PATS). The $k$-PATS problem is that of designing a tile assembly system with the smallest number of tile types which will self-assemble an input pattern of $k$ colors. Of both theoretical and practical significance, $k$-PATS has been studied in a series of papers which have shown $k$-PATS to be NP-hard for $k=60$, $k=29$, and then $k=11$. In this paper, we close the fundamental conjecture that 2-PATS is NP-hard, concluding this line of study. While most of our proof relies on standard mathematical proof techniques, one crucial lemma makes use of a computer-assisted proof, which is a relatively novel but increasingly utilized paradigm for deriving proofs for complex mathematical problems. This tool is especially powerful for attacking combinatorial problems, as exemplified by the proof of the four color theorem by Appel and Haken (simplified later by Robertson, Sanders, Seymour, and Thomas) or the recent important advance on the ErdH{o}s discrepancy problem by Konev and Lisitsa using computer programs. We utilize a massively parallel algorithm and thus turn an otherwise intractable portion of our proof into a program which requires approximately a year of computation time, bringing the use of computer-assisted proofs to a new scale. We fully detail the algorithm employed by our code, and make the code freely available online.

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

Recommendations

• Binary pattern tile set synthesis is NP-hard
• A manually-checkable proof for the NP-hardness of 11-color pattern self-assembly tileset synthesis
• Computing minimum tile sets to self-assemble color patterns
• Solving NP-complete problems in the tile assembly model
• Constant-Size Tileset for Solving an NP-Complete Problem in Nondeterministic Linear Time
• Synthesis of tiled patterns using factor graphs
• Nearly constant tile complexity for any shape in two-handed tile assembly
• Tilings of Binary Spaces
• Hard tiling problems with simple tiles
• scientific article; zbMATH DE number 851645

zbMATH Keywords

computer-assisted proofNP-hardnesspattern assemblyalgorithmic DNA self-assemblymassively-parallelized program

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Intrinsic universality in self-assembly
• One tile to rule them all: simulating any tile assembly system with a single universal tile
• Combinatorial Optimization in Pattern Assembly
• The Two-Handed Tile Assembly Model Is Not Intrinsically Universal
• Computability and complexity in self-assembly
• Intrinsic universality in tile self-assembly requires cooperation
• Self-assembly of decidable sets
• Almost-natural proofs
• Every planar map is four colorable. I: Discharging
• Every planar map is four colorable. II: Reducibility
• Minimum-weight triangulation is NP-hard
• Intrinsic universality and the computational power of self-assembly
• Formal proof - the four color theorem
• Computer solution to the 17-point Erdős-Szekeres problem
• Amplifying lower bounds by means of self-reducibility
• 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
• Cannonballs and honeycombs.
• A SAT attack on the Erdős discrepancy conjecture
• Computing minimum tile sets to self-assemble color patterns
• A manually-checkable proof for the NP-hardness of 11-color pattern self-assembly tileset synthesis
• 3-color bounded patterned self-assembly (extended abstract)
• Binary pattern tile set synthesis is NP-hard
• DNA Computing
• 3-color bounded patterned self-assembly
• Study of the Kepler's conjecture: the problem of the closest packing
• The weak Goldbach conjecture
• Title not available (Why is that?)
• The 24th Mersenne Prime
• Natural proofs

Cited In (7)

• 3-color bounded patterned self-assembly
• The complexity of fixed-height patterned tile self-assembly
• Title not available (Why is that?)
• A manually-checkable proof for the NP-hardness of 11-color pattern self-assembly tileset synthesis
• Binary pattern tile set synthesis is NP-hard
• Programmable single-stranded architectures for computing
• Reflections on tiles (in self-assembly)

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

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