Solving NP-complete problems in the tile assembly model
type: Item
instance of: scholarly article
title: Solving NP-complete problems in the tile assembly model
zbMATH Open document ID: 1145.68018
author: Yuriy Brun
published in: Theoretical Computer Science
publication date: 2008-05-19T00:00:00Z
Mathematics Subject Classification ID: 68Q10
Mathematics Subject Classification ID: 68Q05
Mathematics Subject Classification ID: 68Q17
zbMATH DE Number: 5276395
zbMATH Keywords: self-assembly
zbMATH Keywords: NP-complete
zbMATH Keywords: tile assembly model
zbMATH Keywords: crystal-growth
zbMATH Keywords: molecular computation
zbMATH Keywords: natural computation
zbMATH Keywords: distributed computing
zbMATH Keywords: parallel computing
zbMATH Keywords: nondeterministic computation
zbMATH Keywords: subsetsum
MaRDI profile type: Publication
full work available at URL: j.tcs.2007.07.052
OpenAlex ID: W1967232959
cites work: Q4664413
cites work: Combinatorial optimization problems in self-assembly
cites work: Running time and program size for self-assembled squares
cites work: The Undecidability of the Infinite Ribbon Problem: Implications for Computing by Self-Assembly
cites work: Complexities for Generalized Models of Self-Assembly
cites work: DNA Computing
cites work: Self-correcting Self-assembly: Growth Models and the Hammersley Process
cites work: Q4529973
cites work: Arithmetic computation in the tile assembly model: addition and multiplication
cites work: Nondeterministic polynomial time factoring in the tile assembly model
cites work: Reducing tile complexity for self-assembly through temperature programming
cites work: Q4762326
cites work: Undecidability and nonperiodicity for tilings of the plane
cites work: The program-size complexity of self-assembled squares (extended abstract)
cites work: Q3392273
DOI: 10.1016/J.TCS.2007.07.052
description: scientific article; zbMATH DE number 5276395