3-SAT → Reachability in priority-inhibited unimolecular reaction networks Complexity open
Unsolved
Why this question matters
Moderate: hardness would separate priority inhibition from ordinary unimolecular reaction reachability and sharpen a basic model of biochemical computation. It would not give the exact class if the priority problem is harder than NP.
The SWAT 2026 table and conclusion mark (1,1) Priority iCRN reachability open, between polynomial basic CRNs and PSPACE-complete general inhibitory CRNs. The paper's Theorem 36 one-inhibitor hardness does not apply to prefix inhibition.
The reduction to construct
An explicit Boolean 3-CNF formula is given. Output YES exactly when it is satisfiable, and NO otherwise.
The input lists an ordered finite set of species, explicit reactions each converting exactly one molecule of one species to one of another species, an integer priority p between zero and the species count for each reaction, and binary-encoded start and target molecule-count vectors. A reaction with priority p is enabled only when its reactant is present and each of the first p species has count zero. Output YES exactly when a finite enabled reaction sequence reaches the target vector, and NO otherwise.
Construct deterministic polynomial-time F and G from 3-SAT to reachability in this exact (1,1) Priority iCRN model. The maps must preserve YES and NO for every legal source instance; a positive result establishes NP-hardness for the 2026 open priority-inhibition cell.
High: the published 3-SAT reduction for arbitrary single-inhibitor (1,1) networks uses independently chosen inhibitor species, whereas a priority rule tests an entire prefix. A plausible route imposes a species order and clears earlier blockers in controlled phases; the missing invariant is that these extra clearings cannot create false accepting paths.
What a complete answer must include
Specify the ordered species, prefix priorities, reactions and configurations; prove that every reachable target represents a satisfying choice and every satisfying choice gives a valid sequence; bound molecule counts, vector lengths and runtime. Later checks should simulate small reaction networks independently.
References
Literature checked 2026-09-26. Checked SWAT 2026 primary paper, Table 1, Priority iCRN dynamics in Section 2.2.1, Theorem 36 and Conclusion; searched 2026-09-26 for 'Priority iCRN (1,1) reachability complexity' and later versions. No matching resolution surfaced. Gates 1-4 pass; Gate 5 holds on a prefix-inhibition simulation; Gate 6 was not assessed.