Cycles and global attractors of reactantless and inhibitorless reaction systems

We explore the computational complexity of deciding the existence of fixed points and cycles that can be reached from any other states (called global attractors) in the dynamics of inhibitorless and reactantless reaction systems. The problems we consider are all known to be PSPACE-complete in the case of unconstrained reaction systems; in this paper, we show that some of them become polynomially solvable when limited to inhibitorless and reactantless reaction systems, while others remain PSPACE-complete. Specifically, we prove that the problems of deciding (i) if a given state belongs to a cycle, (ii) whether two reaction systems have at least one cycle in common, and (iii) whether they have the same set of cycles, remain PSPACE-complete even in the inhibitorless and reactantless classes, as well as the problem of deciding if a global cycle attractor exists in a reactantless reaction system. Interestingly, however, we demonstrate that no global cycle attractor of length at least 2 can exist in inhibitorless reaction systems; and no global cycle attractor of length greater than 2 can exist in reactantless reaction systems. Furthermore, we show that the problems of deciding whether a given state is a global attractor and whether a global fixed point attractor exists become polynomially solvable when restricted to inhibitorless and reactantless reaction systems.