Reachability with Restricted Reactions in Inhibitory Chemical Reaction Networks

Given a Priority iCRN, start configuration $\overrightarrow{C_s}$ and target configuration $\overrightarrow{C_t}$:

1. 1.

   For any species ${\lambda }_i$, if $\overrightarrow{C_t}[{\lambda }_i]\ne 0$ then remove all reactions ${\gamma }_j$ such that $𝒫({\gamma }_j)\ge i$. Since we only consider void rules, such reactions will never be applicable in any configuration along any path from $\overrightarrow{C_s}$ through $\overrightarrow{C_t}$.

2. 2.

   For $i=1$ to $|\mathrm{\Lambda }|$, if there exists a reaction of form ${\lambda }_i\to \varphi$:

   1. (a)

      then apply the reaction $\overrightarrow{C_s}[{\lambda }_i]-\overrightarrow{C_t}[{\lambda }_i]$ times.

   2. (b)

      else, skip to step $(3)$.

3. 3.

   If the final configuration is reached, return “yes”, otherwise return “no”.

$◀$

We now show that the reachability problem in Priority iCRNs with $(2,0)$ reactions is also solvable in polynomial time. To do so, we start by showing that the general reachability problem for a given Priority iCRN with $(2,0)$ void rules can be reduced to the empty reachability problem in the given CRN in Lemmas 8, 9, and 10. We then reduce the empty configuration reachability problem in the Priority iCRN to the known maximum $b$-matching problem, which is solvable in polynomial time [3], in Lemma 12.

Given a $(2,0)$ void Priority iCRN system $((\mathrm{\Lambda },\mathrm{\Gamma }),𝒫)$ such that $k={\max }_{\gamma \in \mathrm{\Gamma }}𝒫(\gamma )$. We can partition the set of species $\mathrm{\Lambda }$ into set of inhibiting species $\{{\lambda }_1,\mathrm{\dots },{\lambda }_k\}$ and set of non-inhibiting species $\{{\lambda }_{k+1},\mathrm{\dots },{\lambda }_{|\mathrm{\Lambda }|}\}$.

Given that $\forall i\le k,\overrightarrow{C_t}[{\lambda }_i]=0$, $\overrightarrow{C_s}[{\lambda }_i]-\overrightarrow{C_t}[{\lambda }_i]=\overrightarrow{C_s}[{\lambda }_i]$. Therefore, all inhibited reactions will be applicable at some point.

Since void rules only delete species, and do not add new counts for species, for all non-inhibiting species ${\lambda }_j$ with $j>k$, if $\overrightarrow{C_t}[{\lambda }_j]$ is reachable from $\overrightarrow{C_s}[{\lambda }_j]$, then $\overrightarrow{0}[{\lambda }_j]$ is reachable from $\overrightarrow{C_s}[{\lambda }_j]-\overrightarrow{C_t}[{\lambda }_j]$. $◀$

We modify the given Priority iCRN ${𝒞}_{𝒫ℐ}$ system as follows. We remove all reactions $\gamma \in \mathrm{\Gamma }$ such that $𝒫(\gamma )\ge i$, $\forall i\le k$ if $\overrightarrow{C_t}[{\lambda }_i]\ne 0$. This is because such reactions will never be applicable as they will always be inhibited. Due to this modification, the species ${\lambda }_i,\mathrm{\dots },{\lambda }_k$ no longer permanently act as inhibitors. The new reaction set ${\mathrm{\Gamma }}^{\prime }$ contains the remaining inhibited reactions with priority greater than $0$. We now compute $k^{\prime }$ over ${\mathrm{\Gamma }}^{\prime }$ as $k^{\prime }={\max }_{\gamma \in {\mathrm{\Gamma }}^{\prime }}𝒫(\gamma )$. We partition the set $\mathrm{\Lambda }$ again into set of inhibiting species $\{{\lambda }_1,\mathrm{\dots },{\lambda }_{k^{\prime }}\}$ and set of non-inhibiting species $\{{\lambda }_{k^{\prime }+1},\mathrm{\dots },{\lambda }_{|\mathrm{\Lambda }|}\}$. From Lemma 8, $\overrightarrow{C_s}\rightsquigarrow \overrightarrow{C_t}\iff \overrightarrow{C_s}-\overrightarrow{C_t}\rightsquigarrow \overrightarrow{0}$ in a Priority iCRN ${𝒞}_{𝒫ℐ}=((\mathrm{\Lambda },{\mathrm{\Gamma }}^{\prime }),𝒫)$. $◀$

Follows from Lemmas 8 and 9. $◀$

The runtime of the maximum $b$-matching problem is strictly polynomial and runs in $O({|V|}^2\log (|V|)(|E|+|V|\log (|V|)))$ [3]. We use this runtime to solve the reachability problem for Priority iCRNs with only $(2,0)$-size reactions in polynomial time.

To solve the empty-configuration reachability problem in $(2,0)$ void Priority iCRN, we reduce it to an instance of the maximum $b$-matching problem.

Given a Priority iCRN ${𝒞}_{𝒫ℐ}=((\mathrm{\Lambda },\mathrm{\Gamma }),𝒫)$ with starting configuration $\overrightarrow{C_s}$, we construct a $b$-matching instance by building a graph $G=(V,E)$ as follows. Here we assume that the given Priority iCRN only includes reactions $\gamma :{\lambda }_i+{\lambda }_j\to \varphi$ where $i,j>𝒫(\gamma )$; any self-inhibiting reactions that exist ($i$ or $j$ is less than the priority) are ignored. We turn every species ${\lambda }_i\in \mathrm{\Lambda }$ into a vertex $v_i\in V$ and set the $b$-values for each of the vertices $b(v_i)=\overrightarrow{C_s}[{\lambda }_i]$. For each $\gamma :{\lambda }_i+{\lambda }_j\to \varphi$ in $\mathrm{\Gamma }$ such that $i\ne j$, add an undirected edge $e=(v_i,v_j)$ in $E$. For any reaction of the form ${\lambda }_i+{\lambda }_i\to \varphi$, add vertices $v_i^1,v_i^2$ to the set $V$ and set the b-values $b(v_i^1)=b(v_i^2)=\lfloor \frac{b(v_i)}{2}\rfloor$. We also add undirected edges $(v_i,v_i^1),(v_i,v_i^2),(v_i^1,v_i^2)$ in $E$.

From the rules above, we have the graph $G$ well defined. We now present the following claims regarding $G$.

This is straightforward for the case when applying a reaction of the form ${\lambda }_i+{\lambda }_j\to \varphi$ such that $i\ne j$. The reaction application results in the removal of one copy of species ${\lambda }_i$ and ${\lambda }_j$. This corresponds to an edge matching of $(v_i,v_j)$ on the graph $G$ according to the construction above. We reduce the values of $b(v_i)$ and $b(v_j)$ by one, and the pair $(v_i,v_j)$ form a perfect matching. For the case when applying a reaction of form ${\lambda }_i+{\lambda }_i\to \varphi$, two copies of ${\lambda }_i$ are deleted from the configuration. This rule application corresponds to selecting edges $(v_i,v_i^1)$ and $(v_i,v_i^2)$. We reduce the counts of $b(v_i^1)$ and $b(v_i^2)$ by one, and that of $b(v_i)$ by two. The remaining $b$-values of vertices $v_i^1$ and $v_i^2$ are reduced by selecting edge $(v_i^1,v_i^2)$. And the pairs $(v_i,v_i^1)$, $(v_i,v_i^2)$, and $(v_i^1,v_i^2)$ form a perfect matching.

If there exists a perfect $b$-matching for the graph $G$, there exists an assignment $f:E\to \mathbb{N}$ such that ${\sum }_{e\in \delta (v)}f(e)=b(v)$ for all $v\in V$. From the construction of the graph, all edges $(v_i,v_j)\in E$ such that $i\ne j$ correspond to a reaction ${\lambda }_i+{\lambda }_j\to \varphi$ in $\mathrm{\Gamma }$ in the Priority iCRN. And, edges of the form $(v_i,v_i^1),(v_i,v_i^2)\in E$ correspond to a reaction ${\lambda }_i+{\lambda }_i\to \varphi$ in $\mathrm{\Gamma }$. We argue that, given any perfect $b$-matching, we can apply a corresponding set of reactions in a rearranged order based on their priority to reach the empty configuration.

Let $M$ contain the set of edges to be a perfect $b$-matching for $G$. We apply reactions in Priority iCRN corresponding to the edges in $M$ as follows.

1. 1.

   Apply all reactions $\gamma ={\lambda }_i+{\lambda }_j\to \varphi$ corresponding to edges $e_k=(v_i,v_j)$, $f(e_k)$ times, if $e_k\in M$, $i\ne j$ and $𝒫(\gamma )=0$. All such reactions are uninhibited and can be applied.

2. 2.

   Apply all reactions $\gamma ={\lambda }_i+{\lambda }_i\to \varphi$ corresponding to edges $e_k=(v_i,v_i^1)$ and $e_{\mathrm{\ell }}=(v_i,v_i^2)$, $f(e_k)$ times, if $e_k,e_{\mathrm{\ell }}\in M$ and $𝒫(\gamma )=0$. The vertices $v_i^1$ and $v_i^2$ are only connected to each other and to vertex $v_i$. To achieve perfect b-matching for vertices $v_i^1$ and $v_i^2$, assigned values $f(e_k)$ and $f(e_{\mathrm{\ell }})$ must be exactly equal, $f(e_k)=f(e_{\mathrm{\ell })}=b(v_i^1)-f(e_m)$ where $e_m=(v_i^1,v_i^2)$. Applying such a reaction will delete $2\ast f(e_k)$ copies of species ${\lambda }_i$.

3. 3.

   For all $p$ in $1$ through ${\max }_{\gamma \in \mathrm{\Gamma }}𝒫(\gamma )$:

   1. (a)

      apply all reactions $\gamma ={\lambda }_i+{\lambda }_j\to \varphi$ corresponding to edges $e_k=(v_i,v_j)$, $f(e_k)$ times, if $e_k\in M$, $i\ne j$ and $𝒫(\gamma )=p$.

   2. (b)

      apply all reactions $\gamma ={\lambda }_i+{\lambda }_i\to \varphi$ corresponding to edges $e_k=(v_i,v_i^1)$ and $e_{\mathrm{\ell }}=(v_i,v_i^2)$, $f(e_k)$ times, if $e_k,e_{\mathrm{\ell }}\in M$, and $𝒫(\gamma )=p$.

Furthermore, the reactions applied in each iteration in Step $3$ are guaranteed to be applicable (absence of inhibitors and sufficient count of reactants) because $(1)$ all species count go to zero; $(2)$ no reaction that uses a reactant ${\lambda }_i$ has a priority $p>i$; and $(3)$ each reaction $e_k$ is only applied $f(e_k)$ times. If multiple reactions use a species ${\lambda }_i$, the total applications of all those reactions ${\sum }_{e\in \delta (v_i)}f(e)$ will be exactly $b(v_i)$. Therefore, rearranging applications of each of those reactions will not affect the availability of reactants in later applications. $◀$

Given a Priority iCRN with starting configurations $\overrightarrow{C_s}$ and target configuration $\overrightarrow{C_t}$, create the configuration $\overrightarrow{C_s}-\overrightarrow{C_t}$. From Lemma 12, empty configuration reachability is decidable from $\overrightarrow{C_s}-\overrightarrow{C_t}$ in polynomial time. Finally, from Lemma 10, empty configuration reachability in $(2,0)$ Priority iCRN implies reachability. $◀$

The dynamic programming algorithm uses a $|\mathrm{\Lambda }|\times (|\mathrm{\Lambda }|+1)$ table $D$ of boolean entries, where each row represents a different species. Since each $(k,k-1)$ catalytic void reaction reduces the count of exactly one species, only one of the reactions need to be applied at most $\overrightarrow{C_s}[{\lambda }_i]-\overrightarrow{C_t}[{\lambda }_i]$ times to reduce the count of a species ${\lambda }_i$. Hence, only $|\mathrm{\Lambda }|$ distinct reactions need to be considered to reach the target configurations, if possible. The total number of rule applications, however, will be polynomial in the volume of the system.

A bottom-up approach is used to determine the ordering of the species in which their count needs to be reduced. This is essential since a species ${\lambda }_i$ shouldn’t go to zero before it is used as a catalyst in other reactions that need to be applicable. The algorithm starts by filling first column of $D$ with $1$ for species who have reached their target count. It then progresses column-by-column, applying reactions based on the ordering on species. If the last column has all $1$s, then the configuration is reached. $◀$

This follows as a modification of the dynamic programming algorithm for general CRNs with only void rules of size $(k,k-1)$ from Lemma 16. Let $\overrightarrow{C_f}$ denote the target configuration, with ${\lambda }_1,\mathrm{\dots },{\lambda }_{|\mathrm{\Lambda }|}$ denoting the order assigned to the species. Remove all rules of the form ${\lambda }_j+(.){\to }^k(.)$, where . The rest of the system remains the same.

Start with a counter $l=|\mathrm{\Lambda }|$. Construct an $|\mathrm{\Lambda }|\times (|\mathrm{\Lambda }|+1)$ table $D(s,j)$ of boolean entries, where each row represents a different species. Reduce the count of each species to $max(k,s^f)$, where $s^f$ represents the final count of species $s$, if there exists a rule that can do so. Starting from the first column $j=0$, place a $1$ if the respective species is already in its final count. Then, for each entry $D(s,j)$, place a $1$ if $D(s,j-1)$ is a $1$, or if there exists a reaction $\gamma \in \mathrm{\Gamma }$ for $s\in \mathrm{\Lambda }$ that reduces $s$ to its final count such that 1) $\overrightarrow{C_f}[s]>0$ or 2) $s={\lambda }_l$, where all the reactants of $\gamma$ have either reached their final counts or will not prevent the reaction from occurring once they do. Any time species ${\lambda }_l$ has found a reaction to reach a final count $0$, set $l=l-1$. If column $|\mathrm{\Lambda }|+1$ contains all 1’s, then reachability is possible. Otherwise, it is not.

The algorithm follows the same bottom-up approach as for general CRNs. The main difference is that now there exists a predetermined ordering that species must go to zero for other rules to be applicable. Thus, any species ${\lambda }_j$ such that is not considered until species ${\lambda }_l$ has found a suitable reaction and reaches a count of zero. The proof then follows from general CRNs. $◀$

Consider a sequence of applicable void rules $A$ for a given (Priority) iCRN that is not contiguous. We construct a contiguous sequence as described in the Rearrangement Lemma in [12]. For the given sequence $A$, suppose rule $\gamma$ occurs at positions $i$ and $j$ such that , and there is at least one non-$\gamma$ rule in between $i$ and $j$. Construct a sequence $A^{\prime }$ by shifting the rule $\gamma$ at position $i$ up to position $j-1$, and shifting all rules in between down one position.

This new sequence must be applicable as $(1)$ the only rule that moved to a higher index in the sequence is of type $\gamma$, and we know that $\gamma$ is applicable at position $j-1$ since it is applicable at position $j$, and $(2)$ because, in a system with just void rules, species are only deleted and not produced. Therefore, all rules that occur between positions $i$ and $j$ must not be inhibited by the reactants of $\gamma$ (since the reactants of $\gamma$ are present until position $j$); therefore, such rules can be applied before all occurrences of $\gamma$.

Since this swapping preserves the applicability of the sequence while reducing the number of non-contiguous blocks of one rule type in the sequence, we can repeat this process of swapping rule positions until the sequence is contiguous. $◀$

Given a sequence of applicable void rules in a given iCRN, we encode this sequence with a sequence of rule types accompanied by a count on the number of applications of each rule type, which must exist by Lemma 18. Although the original sequence is potentially exponential in length, the result of the contiguous sequence can be computed in polynomial time. Therefore, we utilize a contiguous sequence of applicable rules as a certificate for the reachability problem. $◀$

Due to space constraints, we provide a proof sketch here, while the complete proof can be found in the full version of the paper on arxiv.

From Lemma 19, we have that the reachability problem for Priority iCRNs with purely void rules is in NP. To show hardness, we reduce from Vertex Cover. Given an instance of VC $⟨G,k⟩$ where $k>0$, we construct a Priority iCRN ${𝒞}_{𝒫ℐ}$. We create one copy of $v$ for all $v\in V$ and one copy of $e$ for all $e\in E$. We also add two new species to the ${𝒞}_{𝒫ℐ}$ system. In the initial configuration, we add $|V|-k$ copies of a species $R$, used to eliminate $|V|-k$ vertices, and $k$ copies of a species $X$, used to remove the remaining $k$ vertices. Denote this configuration the starting configuration $\overrightarrow{C_s}$. We also order our species set as: $\mathrm{\Lambda }=⟨R,v_1,\mathrm{\dots },v_{|V|},e_1,\mathrm{\dots },e_{|E|},X⟩$.

For all $v\in V$, we create the assignment reaction $v+R\to \mathrm{\varnothing }$ and the clean-up reaction $v+X\stackrel{1}{\to }\mathrm{\varnothing }$. For all edges $e\in E$, for all vertices $v\in V$ where $v$ is incident to $e$, we create the covering reaction $v+e\stackrel{1}{\to }v$. Each of the clean-up and covering reactions have priority $1$.

The target configuration $\overrightarrow{C_t}$ is the empty configuration $\overrightarrow{0}$. A vertex cover of size $k$ can only exist in $G$ iff all the species copies can be completely deleted. $◀$

Given that the system is volume-preserving, the reachability problem is solvable by a non-deterministic Turing machine using only polynomial space, where the tape of the machine stores a configuration (counts of species). Therefore, the problem is in NPSPACE, and hence in PSPACE [27]. $◀$

The hardness follows from the reachability problem in regular CRNs with only $(2,2)$-size rules being PSPACE-complete [11], and membership follows from Lemma 21. $◀$

Run any applicable rule in the system, reducing the corresponding species to its final count. If the final configuration is reached, then reachability is possible. Otherwise, if no more rules can be applied, reachability is not possible. $◀$

Due to space constraints, we provide a proof sketch here, while the complete proof can be found in full version of the paper on arxiv.

Lemma 19 shows reachability in void iCRNs is in NP. To show hardness, we reduce from the Hamiltonian path problem. Given a HAMPATH instance $⟨G,s,t⟩$, we transform it into an instance of reachability with an iCRN ${𝒞}_{ℐ𝒞}$. For each vertex $v\in V$, we create the species $v$ and $v_c$. We also add an extra species $s^{\prime }$. For each directed edge $\{u,v\}\in E$, we create the choosing reaction $u_c+v\stackrel{𝑢}{\to }\mathrm{\varnothing }$. We also create the starting reaction $s^{\prime }+s\to \mathrm{\varnothing }$. Let the initial configuration $\overrightarrow{A}$ be a single copy of each species and the target configuration $\overrightarrow{B}$ be a single copy of $t_c$. A Hamiltonian path from $s$ to $t$ can only exist in $G$ iff the system can delete all copies except for $t_c$. An example reachability instance is illustrated in Figure 2. $◀$

We now explore the reachability problem for a $(2,0)$ void iCRN with a constant number of inhibiting species. We follow the same format as in Priority iCRN section to show that the reachbility problem is polynomial time solvable for a constant number of inhibitors. To do so we show that reachability problem in such an iCRN can be reduced to the empty reachability problem in Lemmas 25, 26, and 27. Finally, we reduce the empty reachability problem in the given iCRN to the empty reachability problem in Priority iCRN with $(2,0)$ reactions.

Given a $(2,0)$ void iCRN ${𝒞}_{ℐ𝒞}=((\mathrm{\Lambda },\mathrm{\Gamma }),ℐ)$, where the set of species $\mathrm{\Lambda }$ is partitioned into the set of inhibiting species ${\mathrm{\Lambda }}_{ℐ}={\bigcup }_{\gamma \in \mathrm{\Gamma }}ℐ(\gamma )$ and the set of remaining species $\mathrm{\Lambda }\setminus {\mathrm{\Lambda }}_{ℐ}$. We use $\overrightarrow{0}$ to denote an empty configuration where all species have a count of zero.

Follows from Lemma 8 because the proof does not rely on any ordering of inhibitors. $◀$

The proof is similar to that of Lemma 9. Here we remove any reactions inhibited by species ${\lambda }_i\in {\mathrm{\Lambda }}_{ℐ}$. Now ${\lambda }_i$ is no longer an inhibitor. The remaining set of reactions is ${\mathrm{\Gamma }}^{\prime }$. From Lemma 25, $\overrightarrow{C_s}\rightsquigarrow \overrightarrow{C_t}\iff \overrightarrow{C_s}-\overrightarrow{C_t}\rightsquigarrow \overrightarrow{0}$ in a iCRN ${𝒞}_{ℐ𝒞}=((\mathrm{\Lambda },{\mathrm{\Gamma }}^{\prime }),ℐ)$. $◀$

Follows from Lemmas 25 and 26. $◀$

We construct an ordered species set ${\mathrm{\Lambda }}^{\prime }$ containing all species from the given iCRN. The species are arranged such that all the inhibitors (in order) appear first in the set. The configuration and reactions are also rearranged to match the ordering of species in ${\mathrm{\Lambda }}^{\prime }$. For each reaction, the priority is set to be the maximum index of all inhibitors. Finally, we remove any reactions that are self-inhibiting, i.e., the priority of the reaction is greater or equal to the index of at least one of the reactants. The complete proof can be found in full version of the paper on arxiv. $◀$

Given an iCRN ${𝒞}_{ℐ𝒞}=((\mathrm{\Lambda },\mathrm{\Gamma }),ℐ)$ with $(2,0)$ void rules and some start configuration $\overrightarrow{C_s}$. Given that the iCRN has at most $c$ inhibitors, there exist at most $c!$ different orderings in which the inhibitors are removed.

To solve the empty configuration reachability problem in iCRN, we reduce it to $c!$ instances of the empty configuration reachability problem in Priority iCRN. From Lemma 12 we know that this problem is solvable in $O(f(\mathrm{\Lambda },\mathrm{\Gamma }))$. For each ordering $⟨i_1,i_2,\mathrm{\dots },i_c⟩$ where $i_j$ is some species that acts as an inhibitor, we construct a Priority iCRN as described in Lemma 28. We now show that the empty configuration is reachable in the given iCRN iff the empty configuration is reachable in at least one of the $c!$ Priority iCRNs.

This is true simply by construction of the Priority iCRNs. If the iCRN reaches the empty configuration, then all species, including inhibitor species, go to zero. Therefore, there must exist an ordering in which these inhibitors are deleted. Since we consider every possible ordering, at least one of the $c!$ Priority iCRNs orderings will reach the empty configuration.

Let the ordering corresponding to the Priority iCRN for which the empty configuration is reachable be $⟨i_1,\mathrm{\dots },i_c⟩$. Modify the reaction set $\mathrm{\Gamma }$ of the given iCRN by removing all reactions of the form $i_j+\mathrm{\_}\to \varphi$ or $\mathrm{\_}+i_j\to \varphi$ if they are inhibited by species $i_{k>j}$ since $i_j$ is deleted before $i_k$. For the remaining reactions, apply the reactions in the same order in which their corresponding reactions in ${𝒞}_{𝒫ℐ}$ are applied. If none of the $c!$ Priority iCRNs reach the empty configuration, then the given iCRN will also not reach the empty configuration. $◀$

Similar to the case of $(2,0)$ Priority iCRN, proof follows from Lemmas 27 and 29. $◀$

Due to space constraints, we provide a proof sketch here, while the complete proof can be found in full version of the paper on arxiv.

From Lemma 19, we have that the reachability problem in void iCRNs is in NP. To show hardness, we reduce from the 3-satisfiability problem. Given an instance of 3SAT $⟨\mathrm{\Phi }⟩$, we create a new iCRN ${𝒞}_{ℐ𝒞}$. For each variable $x_i\in X_n$, we create the species $T_i$ and $F_i$. Additionally, for each clause $c_j\in C_m$, we create the species $c_j$. Finally, we create the species $X$. For each variable $x_i$, we also create the assignment reactions $T_i+F_i\to T_i$ and $T_i+F_i\to F_i$. For each clause $c_j$ and a variable of $c_j$ $x_k$, we create the clause reaction $C_i+T_k\stackrel{F_k}{\to }{T}_k$ if assigning true to $x_k$ satisfies $c_j$, or $C_i+F_k\stackrel{T_k}{\to }{F}_k$ if the false assignment satisfies instead. Finally, for each variable, we create the clean-up reaction $T_i+X\to X$ and $F_i+X\to X$. The initial configuration $\overrightarrow{C_s}$ is a single copy of each species and the target configuration $\overrightarrow{C_t}$ is a single copy of $X$. $\mathrm{\Phi }$ can only be satisfied iff the system can delete all copies except for $X$. An example reachability instance is illustrated in Figure 3. $◀$

Follows from Theorem 31. Given an iCRN ${𝒞}_{ℐ𝒞}$, we modify it by adding a species $d$ and modifying each reaction to include $k-2$ copies of $d$ for both reactants and products (i.e., $T_x+F_x+d\to T_x+d$ for $k=3$). We include $k-2$ copies of $d$ for $\overrightarrow{C_s}$ and $\overrightarrow{C_t}$. Since $d$ acts as a catalyst species for all reactions, its count will never change, and it does not affect the behavior of ${𝒞}_{ℐ𝒞}$. Thus, the forward and reverse directions from Lemma 31 follow here. $◀$

This follows by using the algorithm for Priority iCRN void systems with size $(k,k-1)$ rules from Theorem 17 as a subroutine. Denote this algorithm $g$. Consider an arbitrary ordering of the $c$ inhibitors ${\lambda }_1,\mathrm{\dots },{\lambda }_c$. Run algorithm $g$ with this ordering. If a solution is found, then reachability is possible. Otherwise, consider another ordering until all are considered. The algorithm then runs in $𝒪(c!\cdot {|\mathrm{\Lambda }|}^2|\mathrm{\Gamma }|)$ time. $◀$

We show that reachability is NP-complete with $(2,0)$ and $(2,1)$ reactions, even if only one species is used to inhibit reactions.

From Lemma 19, we have that the reachability for iCRNs with purely void rules is in NP. We now show hardness with a similar reduction as in Theorem 20. We construct our iCRN ${𝒞}_{ℐ𝒞}$ in a similar manner, where our species set is now unordered. Here, the species set $\mathrm{\Lambda }=\{R,v_1,\mathrm{\dots },v_{|V|},e_1,\mathrm{\dots },e_{|E|},X\}$. Our reaction set contains assignment reactions $v+R\to \varphi$, clean-up reactions $v+X\stackrel{𝑅}{\to }\varphi$, and covering reactions $v+e\stackrel{𝑅}{\to }v$. The initial and target configurations remain the same. $◀$

PSPACE membership follows from Lemma 21. We now show hardness. Given a Turing machine $ℳ=(Q,\mathrm{\Sigma },\mathrm{\Gamma },\delta ,q_s,q_a,q_r)$ with bounded tape length $n$, we create an iCRN ${𝒞}_{ℐ𝒞}=(\mathrm{\Lambda },{\mathrm{\Gamma }}_C)$. The set $\mathrm{\Lambda }$ consists of the helper species $D$, $H$, and $E$, the tape symbols $\{x_i,0_i,1_i\}$ for each tape cell $i\in [1,n]$, and the following sets of species: $𝒬=\{Q_y|q_y\in Q\}$, ${𝒬}^0={\{Q_y{0}_i\}}_{q_y\in Q,i\in [1,n]}$ and ${𝒬}^1={\{Q_y{1}_i\}}_{q_y\in Q,i\in [1,n]}$. Table 2 shows the reactions created.

The initial configuration $I$ of the system consists of one instance of $0_i$ or $1_i$ for each tape cell $i$, according to the initial tape of $ℳ$. Given the start state $q_s$, we also add a single copy of $Q_s$. If the tape head starts at cell $i$, we include one instance of each species $x_j$ for all $j\ne i$, i.e., ${\{x_j\}}_{j\ne i}$. Finally, we include one copy each of the helper species $D$ and $H$. The target configuration $T$ is volume $I$ copies of $E$.

Assume we are given a Turing Machine that will reach a halt state by applying a series of transitions from $\delta$, each according to the tape value at head and the state. The corresponding iCRN ${𝒞}_{ℐ𝒞}$ will likewise reach target configuration $T$ by applying a series of reactions representing those transitions, according to the current configuration $C$. When a single $D$ is present in $C$, $C$ maps to the Turing Machine. $Q_y$ indicates $ℳ$ is in state $q_y\in Q$. The Tape head is at tape cell $j$ where $x_j$ is absent. The data for tape cell_i is saved in the presence of a copy of $1_i$, or one of $0_i$. All reactions shown in Table 2 except 1.3, 7.1 and 7.2 handle normal transitions, updating the given configuration to map to the result of the next transition. In this order, the reactions: (1) read the tape, (2) determine the next state, (3) mark the tape head ready to move, (4) change the state, (5) write and move the tape head, and (6) indicate ready for next transition. If the current state is a halt state, reaction 1.3 is applied, than (7) is repeatedly applied until we reach a terminal configuration. The final terminal configuration will only be $T$ if the TM’s tape and state input deterministically transitions to $q_a$ according to $\delta$.

To reach the target configuration $T$ of iCRN ${𝒞}_{ℐ𝒞}$ which was designed to simulate bounded length $N$ TM $A$, reaction 7.2 must run $2N$ times. This can only happen if $Q_a$ was present, preventing reactions 1.1 and 1.2, and not being $Q_r$, which would also prevent the reactions, but could not be removed by 7.2. For $Q_a$ to be present, it either was in $I$, or was produced by a type 4 reaction. To have $Q_a$ produced by a type 4 reaction, the most recent type 2 reaction must have produced $Q_{ai}$. For any reaction of type 2 to be applicable, D cannot be present, so before this reaction could occur, a reaction of type 1.1 or 1.2 must have been run. It produced a copy of $Q_y{V}_i$ where $Q_y$ represents the state the system was in before $Q_a$, and $V$ is the symbol at our tape head. $Q_y{V}_i$ prevents all type 2 reactions except ${\delta }_{state}(y,V)$, so we could only have reached $Q_a$ if ${\delta }_{s}tate(y,V)$ = $q_a$. For our configuration to have included a $1_i$ or $0_i$ and $Q_y$ which would lead to $Q_a$, they either must have been in $I$, or were produced by repetitions of the same process. This process also includes one reaction of type 3 and one of type 5, which together update the tape. Thus we could only have reached the target configuration if the initial tape values and State deterministically Halt in an accept state. $◀$

We show this by a reduction from 3SAT. Consider a 3SAT instance of $n$ variables $X_1,\mathrm{\dots }{X}_n$ and $m$ clauses $C_1,\mathrm{\dots }{C}_m$, and assume no clause contains both $x_i$ and $\overline{x_i}$. From this instance, we create the following $(1,1)$ iCRN system and start and end configurations for the Reachability problem.