Computational complexity of atomic chemical reaction networks

Chemical reaction network has been a model of interest to both theoretical and applied computer scientists, and there has been concern about its physical-realisticity which calls for study on the atomic property of chemical reaction networks. Informally, a chemical reaction network is “atomic” if each reaction may be interpreted as the rearrangement of indivisible units of matter. There are several reasonable definitions formalizing this idea. We investigate the computational complexity of deciding whether a given network is atomic according to each of these definitions. Primitive atomic, which requires each reaction to preserve the total number of atoms, is shown to be equivalent to mass conservation. Since it is known that it can be decided in polynomial time whether a given chemical reaction network is mass-conserving (Mayr and Weihmann, in: International conference on applications and theory of petri nets and concurrency, Springer, New York, 2014), the equivalence we show gives an efficient algorithm to decide primitive atomicity. Subset atomic further requires all atoms be species, so intuitively this type of network is endowed with a “better” property than primitive atomic (i.e. mass conserving) ones in the sense that the atoms are not just abstract indivisible units, but also actual participants of reactions. We show that deciding if a network is subset atomic is in \({\mathsf{NP}}\), and “whether a network is subset atomic with respect to a given atom set” is strongly \({\mathsf{NP}}\)-\({\mathsf {complete}}\). Reachably atomic, studied by Adleman et al. (On the mathematics of the law of mass action, Springer, Dordrecht, 2014.  https://doi.org/10.1007/978-94-017-9041-3_1), and Gopalkrishnan (2016), further requires that each species has a sequence of reactions splitting it into its constituent atoms. Using a combinatorial argument, we show that there is a polynomial-time algorithm to decide whether a given network is reachably atomic, improving upon the result of Adleman et al. that the problem is decidable. We show that the reachability problem for reachably atomic networks is \({\mathsf {PSPACE}}\)-\({\mathsf {complete}}\). Finally, we demonstrate equivalence relationships between our definitions and some cases of an existing definition of atomicity due to Gnacadja (J Math Chem 49(10):2137, 2011).