Complexity of graph self-assembly in accretive systems and self-destructible systems
type: Item
instance of: scholarly article
title: Complexity of graph self-assembly in accretive systems and self-destructible systems
zbMATH Open document ID: 1237.68103
author: J. Reif
author: Sudheer Sahu
author: Peng Yin
published in: Theoretical Computer Science
publication date: 2011-03-29T00:00:00Z
review text: Self-assembly is an ubiquitous process in nature, in which elementary objects associate with each other to form larger objects. It is mainly present in Chemistry and Biology, but also in other branches of Science. Therefore, there has been a growing interest to study self-assembly from the perspectives of Mathematics, Computer Science, Physics, Chemistry, and Biology. This paper is mainly concerned with the first two perspectives. It presents two models for self-assembly: accretive systems, and self-destructible systems. In the first model, an element cannot be removed from the assembly once it is glued with the other elements. In self-destructible systems, part(s) of the assembly can be removed if repulsive forces become too large. These two models differ from preceding ones in two ways: First, repulsive forces are considered, while previous works limit themselves to attractive forces. Second, the assembly process results in an arbitrary graph, whereas previous models only consider two-dimensional square grids. With this framework, the authors define and study two fundamental problems: the Accretive Graph Assembly Problem (AGAP), in accretive systems, and the Self-Destructible Graph Assembly Problem (DGAP), in self-destructible systems. In both models, the problem consists in sequentially constructing a given graph. The authors investigate the computational complexity of both problems, and they show that AGAP is \textbf{NP}-complete, and DGAP is \textbf{PSPACE}-complete. They also discuss the counting and stochastic versions of AGAP, \#AGAP and SAGAP, respectively, and show that both of them are \#\textbf{P}-complete.
reviewed by: Hebert Pérez-Rosés
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 92D10
zbMATH DE Number: 5871237
zbMATH Keywords: self-assembly
zbMATH Keywords: graph
zbMATH Keywords: complexity
zbMATH Keywords: DNA
zbMATH Keywords: nanostrcture
zbMATH Keywords: NP
zbMATH Keywords: NP-complete
zbMATH Keywords: PSPACE-complete
MaRDI profile type: Publication
full work available at URL: j.tcs.2010.10.034
OpenAlex ID: W1973868833
cites work: Running time and program size for self-assembled squares
cites work: Combinatorial optimization problems in self-assembly
cites work: Q4664413
cites work: Q5501350
cites work: Q5501351
cites work: DNA Computing
cites work: Unconventional Computation
cites work: Reducing tile complexity for self-assembly through temperature programming
cites work: Q4460313
cites work: A Grammatical Approach to Self-Organizing Robotic Systems
cites work: Planar Formulae and Their Uses
cites work: Q4298260
cites work: Undecidability and nonperiodicity for tilings of the plane
cites work: The program-size complexity of self-assembled squares (extended abstract)
cites work: Q4414648
cites work: A Self-assembly Model of Time-Dependent Glue Strength
cites work: Programmable Control of Nucleation for Algorithmic Self-Assembly
cites work: Complexity of Compact Proofreading for Self-assembled Patterns
DOI: 10.1016/J.TCS.2010.10.034
description: scientific article; zbMATH DE number 5871237