Reachability with Restricted Reactions in Inhibitory Chemical Reaction Networks
Divya Bajaj, Bin Fu, Ryan Knobel, Austin Luchsinger, Aiden Massie, Pablo Santos, Ramiro Santos, Robert Schweller, Evan Tomai, Tim Wylie · 2026
Read Reachability with Restricted Reactions in Inhibitory Chemical Reaction Networks by Divya Bajaj, Bin Fu, Ryan Knobel, Austin Luchsinger, Aiden Massie, Pablo Santos, Ramiro Santos, Robert Schweller, Evan Tomai, Tim Wylie (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-17510.txt.
Introduction
Bajaj and nine colleagues study reachability in chemical reaction networks, asking whether one mix of molecular species can turn into another through allowed reactions. General reachability was recently proved Ackermann-complete, far beyond feasible computation, but restricted rules like deletion-only or volume-preserving reactions pull it back down. The paper extends that analysis to inhibitory networks. There, a reaction is blocked while certain species are present, and the paper maps where reachability stays tractable under restricted unimolecular and bimolecular reactions.
Catalog record
| CREATOR | Divya Bajaj, Bin Fu, Ryan Knobel, Austin Luchsinger, Aiden Massie, Pablo Santos, Ramiro Santos, Robert Schweller, Evan Tomai, Tim Wylie |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 85095 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.17510
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Reachability with Restricted Reactions in Inhibitory Chemical Reaction Networks Divya Bajaj, Bin Fu, Ryan Knobel, Austin Luchsinger, Aiden Massie, Pablo Santos, Ramiro Santos, Robert Schweller, Evan Tomai, Tim Wylie Abstract Chemical Reaction Networks (CRNs) are a well-established model of distributed computing characterized by quantities of molecular species that can transform or change through applications of reactions. A fundamental problem in CRNs is the reachability problem, which asks if an initial configuration of species can transition to a target configuration through an applicable sequence of reactions. It is well-known that the reachability problem in general CRNs was recently proven to be Ackermann-complete. However, if the CRN’s reactions are restricted in both power, such as only deleting species (deletion-only rules) or consuming and producing an equal number of species (volume-preserving rules), and size (unimolecular or bimolecular rules), then reachability falls below Ackermann-completeness, and is even solvable in polynomial time for deletion-only systems. In this paper, we investigate reachability under this set of restricted unimolecular and bimolecular reactions, but in the Priority-Inhibitory CRN and Inhibitory CRN models. These models extend a traditional CRN by allowing some reactions to be inhibited from firing in a configuration if certain species are present; the exact inhibition behavior varies between the models. We first show that reachability with Priority iCRNs mostly remains in P for deletion-only systems, but becomes NP-complete for one case. We then show that reachability with deletion-only reactions for iCRNs is mostly NP-complete, and PSPACE-complete even for ( 1 , 1 ) (1,1) -size (general) reactions. We also provide FPT algorithms for solving most of the reachability problems for the iCRN model. Finally, we show reachability for CRNs with states is already NP-hard for the simplest deletion-only systems, and is PSPACE-complete even for (general) ( 1 , 1 ) (1,1) -size reactions. University of Texas Rio Grande [email protected] University of Texas Rio Grande [email protected] University of Texas Rio Grande [email protected] University of Texas Rio Grande [email protected] University of Texas Rio Grande [email protected] University of Texas Rio Grande [email protected] University of Texas Rio Grande [email protected] University of Texas Rio Grande [email protected] University of Texas Rio Grande [email protected] University of Texas Rio Grande [email protected] ccs Theory of computation Models of Computation ccs Theory of computation Computational Complexity keywords Chemical Reaction Networks, Vector Addition Systems, Petri-nets, Reachability, Inhibitors, Void Reactions † † runningauthor: D. Bajaj et al. † † copyright: Divya Bajaj and Bin Fu and Ryan Knobel and Austin Luchsinger and Aiden Massie and Adrian Salinas and Pablo Santos and Ramiro Santos and Robert Schweller and Evan Tomai and Tim Wylie † † relatedversion: Full Version † † funding: This research was supported in part by National Science Foundation Grant CCF-2329918. † † editors: Pierre Fraigniaud † † event-title: 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026) † † event-shorttitle: SWAT 2026 † † event-acronym: SWAT † † year: 2026 † † event-date: June 17–19, 2026 † † event-location: Copenhagen, Denmark † † series-volume: 370 † † articleno: 5 1 Introduction Chemical Reaction Networks (CRNs) [ 4 , 5 ] are an abstract model of molecular computation in which molecular species can evolve through applications of reactions . Although initially motivated by modeling natural chemical interactions, CRNs have been recently explored for developing artificial chemical systems [ 25 ] , computations of semilinear functions [ 8 ] , digital logic [ 7 , 17 , 19 ] , and neural networks [ 17 ] , along with successful implementations in DNA Strand Displacement (DSD) systems [ 30 ] . CRNs are computationally equivalent to two classical models of infinite-state systems: Petri-nets [ 27 ] and Vector Addition Systems (VAS) [ 20 , 21 ] . This equivalence connects molecular computation with decades of complexity-theoretic results concerning reachability [ 9 , 15 ] . In all three models, the reachability problem asks whether a target configuration \overrightarrow{C_{t}} can be reached from a given initial configuration \overrightarrow{C_{s}} via a sequence of rule applications. Although certain characteristics of reachability in general CRNs (and equivalently, Petri-nets and VAS) were well-known for decades, such as EXPSPACE-hardness [ 23 ] and decidability [ 24 ] , only recently has the problem been proven to be Ackermann-complete [ 10 , 22 ] . A crucial limitation of the classical models is the absence of zero-checking . To address this, a natural and well-studied extension across all three models is to allow inhibition , which allows certain reactions to be disabled by the presence of designated species. Petri-nets with inhibitor arcs [ 16 , 28 ] , Priority Vector Addition Systems [ 14 ] , and Inhibitory Chemical Reaction Networks [ 6 ] all explore this idea. Because inhibition enables zero-checking, these inhibitory extensions gain substantial power, achieving Turing Universality [ 6 , 26 ] . However, due to the Turing-universal power of zero-checking, the reachability problem becomes undecidable in general for such systems with inhibition. For this reason, and to better understand the boundaries between decidable/tractable and undecidable/intractable, we limit our study to restricted classes of CRNs with inhibition that use only deletion-only or volume-preserving rules. For CRNs, deletion-only (void) reactions never create any new species in the system (e.g., \lambda_{1}+\lambda_{2}\rightarrow\emptyset , or \lambda_{1}+\lambda_{2}\rightarrow\lambda_{1} ), and volume-preserving reactions contain an equal number of reactants and products, ensuring that the system’s volume never changes (e.g., \lambda_{1}+\lambda_{2}\rightarrow\lambda_{3}+\lambda_{4} ). These restrictions are well-motivated: unlike general CRN systems, which can exhibit complex and error-prone behaviors that are challenging to implement [ 31 ] , deletion-only and volume-preserving systems are potentially simpler to realize and analyze [ 1 , 13 ] . Moreover, in the absence of inhibition, such restrictions significantly reduce computational power: deletion-only systems cannot compute even simple functions [ 2 ] , reachability with bimolecular void reactions is solvable in polynomial time [ 1 , 13 ] , and reachability with (1,1) -size reactions is solvable in polynomial time [ 1 ] . These observations raise a central question: to what extent do inhibitory extensions increase the computational power of CRNs when restricted to these small-sized restricted reactions? Under these structural restrictions, we consider two types of inhibitory CRN systems. The general Inhibitory CRN (iCRN) [ 6 ] model simply allows reaction execution to be inhibited by the presence of some subset of species in the configuration. The Priority-Inhibitory CRN (P-iCRN) model establishes a priority for each reaction, in which a reaction with priority k is inhibited from firing unless the first k species are absent from the system. Here, the order of species is used to determine the inhibitors for each reaction. In this paper, we study the reachability problem under deletion-only and volume-preserving reactions for both of these models. 1.1 Our Results For the restricted reaction types studied in this paper, we use the notation (r,p) to denote reactions with r reactants and p products (e.g., (2,0) is a bimolecular void reaction and (1,1) is a volume-preserving unimolecular reaction). For reference, in a traditional CRN model, reachability is in P for all of our considered void reactions [ 1 , 13 ] , NL-hard for (1,1) -size reactions [ 1 ] , PSPACE-complete for (2,2) -size reactions [ 12 ] , and Ackermann-complete for general systems [ 10 , 22 ] . As