Search Results

We initiate the study of "rate-constant-independent" computation of Boolean predicates (decision problems) and numerical functions in the continuous model of chemical reaction networks (CRNs), which model the amount of a chemical species as a nonnegative, real-valued concentration, representing an average count per unit volume. Real-valued numerical functions have previously been studied [Chen et al., 2023], finding that exactly the continuous, piecewise rational linear (meaning linear with rational slopes) functions f: ℝ_{>0}^k → ℝ_{>0} can be computed stably (a.k.a., rate-independently), meaning roughly that the CRN gets the answer correct no matter the rate at which reactions occur. For example the reactions X₁ → Y and X₂+Y → ∅, starting with inputs X₁ ≥ X₂, converge to output Y having concentration equal to the initial difference of inputs X₁ - X₂, no matter the relative rate at which each reaction proceeds. We first show that, contrary to the case of real-valued functions, continuous CRNs are severely limited in the Boolean predicates they can stably decide, reporting a yes/no answer based only on which inputs are 0 or positive, but not on the exact positive value of any input. This limitation motivates a slightly relaxed notion of rate-independent computation in CRNs that we call robust computation. The standard mass-action rate model is used, in which each reaction (e.g., A+B →^k C) is assigned a rate (A ⋅ B ⋅ k in this example) equal to the product of its reactant concentrations and its rate constant k. We say the computation is correct in this model if it converges to the correct output for any positive choice of rate constants. This adversary is weaker than the adversary defining stable computation, the latter being able to run reactions at rates that are not those of mass-action for any choice of rate constants (e.g., the stable adversary may deactivate a reaction temporarily, even if all reactants are positive). We show that CRNs can robustly decide every predicate that is a finite Boolean combination of threshold predicates, where a threshold predicate is defined by taking a rational weighted sum of the inputs x ∈ ℝ^k_{≥ 0} and comparing to a constant, answering the question "Is ∑_{i = 1}^k w_i ⋅ x(i) > h?", for rational weights w_i and real threshold h. Turning to function computation, we show that CRNs can robustly compute any piecewise affine function with rational coefficients, where threshold predicates determine which affine piece to evaluate for a given input x.