Solving NP-complete problems in the tile assembly model

DOI10.1016/J.TCS.2007.07.052zbMath1145.68018OpenAlexW1967232959MaRDI QIDQ924678

Yuriy Brun

Publication date: 19 May 2008

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2007.07.052

zbMATH Keywords

parallel computingNP-completedistributed computingself-assemblytile assembly modelnondeterministic computationnatural computationmolecular computationcrystal-growthsubsetsum

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (7)

Efficient 3-SAT algorithms in the tile assembly model ⋮ \(\mathsf{NP}\)-completeness of the game Kingdomino\(^\text{TM}\) ⋮ Strategies to scan pictures with automata based on Wang tiles ⋮ A manually-checkable proof for the NP-hardness of 11-color pattern self-assembly tileset synthesis ⋮ Improving Efficiency of 3-SAT-Solving Tile Systems ⋮ Path finding in the tile assembly model ⋮ An introduction to tile-based self-assembly and a survey of recent results

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Arithmetic computation in the tile assembly model: addition and multiplication
• Nondeterministic polynomial time factoring in the tile assembly model
• Undecidability and nonperiodicity for tilings of the plane
• The program-size complexity of self-assembled squares (extended abstract)
• Combinatorial optimization problems in self-assembly
• Reducing tile complexity for self-assembly through temperature programming
• Self-correcting Self-assembly: Growth Models and the Hammersley Process
• The Undecidability of the Infinite Ribbon Problem: Implications for Computing by Self-Assembly
• Running time and program size for self-assembled squares
• Complexities for Generalized Models of Self-Assembly
• DNA Computing
• DNA Computing
• DNA Computing
• DNA Computing
• DNA Computing
• DNA Computing

This page was built for publication: Solving NP-complete problems in the tile assembly model