Complexity of graph self-assembly in accretive systems and self-destructible systems (Q633697): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 00:50, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Complexity of graph self-assembly in accretive systems and self-destructible systems |
scientific article |
Statements
Complexity of graph self-assembly in accretive systems and self-destructible systems (English)
0 references
29 March 2011
0 references
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.
0 references
self-assembly
0 references
graph
0 references
complexity
0 references
DNA
0 references
nanostrcture
0 references
NP
0 references
NP-complete
0 references
PSPACE-complete
0 references