We analyze the computational complexity of basic reconfiguration problems for the recently introduced surface Chemical Reaction Networks (sCRNs), where ordered pairs of adjacent species nondeterministically transform into a different ordered pair of species according to a predefined set of allowed transition rules (chemical reactions). In particular, two questions that are fundamental to the simulation of sCRNs are whether a given configuration of molecules can ever transform into another given configuration, and whether a given cell can ever contain a given species, given a set of transition rules. We show that these problems can be solved in polynomial time, are NP-complete, or are PSPACE-complete in a variety of different settings, including when adjacent species just swap instead of arbitrary transformation (swap sCRNs), and when cells can change species a limited number of times (k-burnout). Most problems turn out to be at least NP-hard except with very few distinct species (2 or 3).

Abstract Consider an agent traversing a graph of “gadgets”, where each gadget has local state that changes with each traversal by the agent according to specified rules. Prior work has studied the computational complexity of deciding whether the agent can reach a specified location, a problem we call reachability. This paper introduces new goals for the agent, aiming to characterize when the computational complexity of these problems is the same or differs from that of reachability. First we characterize the complexity of universal traversal—where the goal is to traverse every gadget at least once—for DAG gadgets (partially), one-state gadgets, and reversible deterministic gadgets. Then we study the complexity of reconfiguration—where the goal is to bring the system of gadgets to a specified state. We prove many cases PSPACE-complete, and show in some cases that reconfiguration is strictly harder than reachability, while in other cases, reachability is strictly harder than reconfiguration.