Brief Announcement: Reachability in Deletion-Only Chemical Reaction Networks

We study reachability [8, 9, 10] in a restricted class of Chemical Reaction Networks [4, 5], that considers deletion-only systems [1, 2] (called void rules) where reactions only ever consume species and reduce the size of the system. Despite the closure of this problem for general CRNs [6, 7], and in fact due to how complicated these systems can be, there is a natural motivation to explore reachability for these more restricted systems. This limited class of systems permits tractable and intractable problems, placing it along an interesting complexity boundary. We also consider step CRNs, an experimentally motivated model introduced in [2, 3], where species are added in discrete stages to reflect the progressive addition of molecules in laboratory protocols [11, 12]. In this paper we show that adding even a single step drastically changes the computational complexity of the reachability problem, moving from $P$ (and even $NL$) to NP-complete in many cases.

In this paper we present a number of results for the various types of deletion-only interaction rules that, when taken together, yield (1) a complete characterization of reachability complexity for uniform-size void rules in standard CRNs, (2) a nearly complete characterization of reachability for arbitrary combinations of void rule sizes in standard CRNs, and (3) a complete characterization of reachability for void rules in step CRNs. These results are outlined in Figure 1. In cases where reachability is NP-complete, we derive lower bounds under the Exponential Time Hypothesis and establish nearly matching upper bounds, though these are not included in this brief announcement. Also deferred to the full version are results on optimization and counting variants of reachability, including approximation algorithms for species deletion and hardness results for counting reaction sequences.

A discrete Chemical Reaction Network is a pair $(\mathrm{\Lambda },\mathrm{\Gamma })$ that consists of a finite set of species $\mathrm{\Lambda }$ and a finite set of reactions $\mathrm{\Gamma }$ that dictate how species interact with one another. A configuration is a vector $C$ over $\mathrm{\Lambda }$ specifying the count of each species. A reaction $R\in \mathrm{\Gamma }$ is an ordered pair of configurations $(R_r,R_p)$ representing reactants and products. A reaction is applicable to a configuration $C$ if $C$ has sufficient species to satisfy $R_r$, and applying $R$ results in a new configuration $C^{\prime }=C-R_r+R_p$. A configuration is called terminal with respect to a CRN $(\mathrm{\Lambda },\mathrm{\Gamma })$ if no rule $R$ can be applied to it. We denote the set of reachable configurations (from initial configuration $I$) of a CRN as $REAC{H}_{I,\mathrm{\Lambda },\mathrm{\Gamma }}$. We define the subset of reachable configurations that are terminal as $TER{M}_{I,\mathrm{\Lambda },\mathrm{\Gamma }}$.

A void rule is any rule that does not create any new copies of any species types (only deletes). Formally, $R=(R_r,R_p)$ is a void rule if $R_p[i]\le R_r[i]$ for all species $i$, with at least one strict inequality. Thus, a void rule either has no products or has products that are a subset of its reactants (in which case these products are termed catalysts). We classify void rules by their size: a rule has size $(i,j)$ if the total number of reactants is $i$ and the total number of products is $j$. A reaction is trimolecular if $i=3$, bimolecular if $i=2$, and unimolecular if $i=1$.

A step CRN is a CRN augmented with a finite sequence of steps, where after reaching a terminal configuration at each step, additional species are added to the system. Formally, a step CRN of $k$ steps is an ordered pair $((\mathrm{\Lambda },\mathrm{\Gamma }),(s_0,s_1,s_2,\mathrm{\dots }{s}_{k-1}))$, where the first element of the pair is a normal CRN $(\mathrm{\Lambda },\mathrm{\Gamma })$, and the second is a sequence of configuration vectors denoting how many copies of each species type to add after each step. Figure 2 illustrates a simple step CRN system. Given a step CRN, ${\text{REACH}}_1$ is the set of configurations reachable from the initial configuration $s_0$, and ${\text{TERM}}_1\subseteq {\text{REACH}}_1$ is the subset of terminal configurations. For each subsequent step $i$, ${\text{REACH}}_i$ is defined as the union of configurations reachable from $s_0$ by adding $s_{i-1}$ to each terminal configuration in ${\text{TERM}}_{i-1}$. Similarly, ${\text{TERM}}_i$ is the subset of terminal configurations within ${\text{REACH}}_i$. The set of reachable configurations for a $k$-step CRN is the set ${\text{REACH}}_k$, and the set of terminal configurations is ${\text{TERM}}_k$. A classical CRN can be represented as a step CRN with $k=1$ steps and an initial configuration of $I=s_0$.

The primary computational problem studied in this paper is reachability. Informally, reachability asks if a given initial configuration $A$ can be turned into a target configuration $B$ by applying a sequence of rules from the given CRN. The precise problem statement is given below.

We initiate our study of deletion-only systems by observing that reachability stays within the class NP with only void rules, even with step-CRNs.

Our first collection of results focus on bimolecular systems with either all size $(2,0)$ rules (non-catalytic) or $(2,1)$ rules (catalytic). Recently, $(2,0)$ rule reachability was proven to be polynomial [1]. For $(2,1)$, we present a polynomial-time algorithm for reachability. In contrast, we show that in either scenario the problem becomes NP-complete with the addition of a second step. In Section 3.2, we consider the same problems for CRNs that use both $(2,0)$ and $(2,1)$ rules together.

Our next results involve CRNs with reactions that require more than two reactants. If a system’s rules have all but one reactant serving as catalysts (i.e., $(k,k-1)$ void rules), then reachability remains polynomial-time solvable. In contrast, reachability for systems with any other form of void rule (with 3 or more reactants) becomes NP-complete.