A manually-checkable proof for the NP-hardness of 11-color pattern self-assembly tileset synthesis
| Autor: | Shinnosuke Seki, Ming-Yang Kao, Aleck Johnsen |
|---|---|
| Rok vydání: | 2015 |
| Předmět: |
Discrete mathematics
Control and Optimization Applied Mathematics 0102 computer and information sciences 02 engineering and technology 021001 nanoscience & nanotechnology 01 natural sciences Computer Science Applications Combinatorics Set (abstract data type) Computational Theory and Mathematics 010201 computation theory & mathematics visual_art Theory of computation visual_art.visual_art_medium Discrete Mathematics and Combinatorics Tile 0210 nano-technology Probabilistically checkable proof Mathematics Integer (computer science) |
| Zdroj: | Journal of Combinatorial Optimization. 33:496-529 |
| ISSN: | 1573-2886 1382-6905 |
| Popis: | Patterned self-assembly tile set synthesis (pats) aims at minimizing the number of distinct DNA tile types used to self-assemble a given rectangular color pattern. For an integer k, k-pats is the subproblem of pats that restricts input patterns to those with at most k colors. We give an efficient [InlineEquation not available: see fulltext.] verifier, and based on that, we establish a manually-checkable proof for the NP-hardness of 11-pats; the best previous manually-checkable proof is for 29-pats. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink