Complexity of graph self-assembly in accretive systems and self-destructible systems (Q633697): Difference between revisions

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.