Source-linked AI summary
Deterministic Function Computation with Chemical Reaction Networks
Ho-Lin Chen, David Doty, David Soloveichik
TL;DR
The paper asks which functions can be computed deterministically by chemical reaction networks rather than merely which predicates they can decide. It formalizes molecular-count function computation and proves that the computable functions are exactly those with semilinear graphs, with expected polylogarithmic-time computation for this class.
Problem
The computational behavior of CRNs under guaranteed convergence was known for predicates, but the corresponding range of deterministically computable functions was not characterized.
Method
The paper represents function inputs and outputs as counts of molecular species and analyzes CRNs whose convergent outputs are correct regardless of reaction order.
Results
The deterministically computable functions are exactly those whose graphs are semilinear, and every semilinear function can be computed in expected polylogarithmic time.
Takeaways & Limitations
Deterministic CRN computation has a precise boundary: finite-union-of-linear graph structure characterizes the functions achievable under guaranteed convergence.
Takeaways & Limitations
The construction relies on a carefully chosen initial chemical context, including leader species, and leaves open whether that control can be removed.
Abstract
from arXiv · showhide
Chemical reaction networks (CRNs) formally model chemistry in a well-mixed solution. CRNs are widely used to describe information processing occurring in natural cellular regulatory networks, and with upcoming advances in synthetic biology, CRNs are a promising language for the design of artificial molecular control circuitry. Nonetheless, despite the widespread use of CRNs in the natural sciences, the range of computational behaviors exhibited by CRNs is not well understood. CRNs have been shown to be efficiently Turing-universal when allowing for a small probability of error. CRNs that are guaranteed to converge on a correct answer, on the other hand, have been shown to decide only the semilinear predicates. We introduce the notion of function, rather than predicate, computation by representing the output of a function f:N^k --> N^l by a count of some molecular species, i.e., if the CRN starts with n_1,...,n_k molecules of some "input" species X1,...,Xk, the CRN is guaranteed to converge to having f(n_1,...,n_k) molecules of the "output" species Y1,...,Yl. We show that a function f:N^k --> N^l is deterministically computed by a CRN if and only if its graph {(x,y) | f(x) = y} is a semilinear set. Furthermore, each semilinear function f can be computed on input x in expected time O(polylog(|x|)).
1 Introduction
This paper extends deterministic CRN computation from predicates to functions, asking which molecular-count transformations remain correct regardless of reaction order. It characterizes exactly the computable functions and addresses composition, limitations, and convergence time.
- Motivation: CRNs provide a programming language for engineered molecular systems, including biochemical and nanotechnological controllers.Recent work has shown that CRNs can be physically implemented using nucleic-acid strand displacement.
- Prior work: Prior deterministic CRN results characterized predicate computation, showing that decidable yes/no input sets are precisely semilinear subsets.Predicate computation represents answers through the eventual presence of one voting species and absence of the other.
- Function computation: The paper extends this framework to functions whose inputs and outputs are represented by molecular counts and whose correct result is independent of reaction order and rate constants.The examples include stoichiometric division, conditional conversion, and maximum computation.
- General properties: The paper also shows that deterministic CRNs accept input molecules added at any time, because otherwise some reaction sequence could leave unreacted input while reaching an incorrect terminal state.This property supports reasoning about when inputs become available during computation.
- Composition: Composition is nontrivial because a downstream CRN may consume an upstream output before the upstream computation has finished, producing an incorrect result.Simple concatenation works when the first CRN produces its output monotonically, but not generally when it consumes that output.
- Characterization and efficiency: The deterministically computable functions are exactly those with semilinear graphs, while functions such as x1x2, x^2, and 2x are excluded.A semilinear graph is a finite union of linear sets; the paper also gives an expected polylogarithmic-time construction for every semilinear function.
2 Preliminaries
This section defines the semilinear and affine structures used to characterize CRN function computation, then formalizes CRNs, stable predicate computation, and stable function computation. It also outlines the systematic construction that decomposes semilinear functions into linear pieces selected by semilinear predicates.
- A linear set has the form A = {b + n1u1 + . . . + npup | n1, . . . , np ∈ N}, and a semilinear set is a finite union of linear sets.
- A function is semilinear when its graph is a semilinear set, informally making it a finite piecewise-linear function over linear domains.
- Any semilinear function can be represented by partial affine functions whose domains are selected using semilinear predicates.
- The construction computes each linear piece monotonically with produce and consume species, while predicate outputs select or switch the global output between candidate values.
- The framework characterizes stable computation through fair executions: every fair execution must contain a stable configuration with the correct output counts.
3 Exactly the semilinear functions can be deterministically computed
The section proves that deterministic CRN function computation is exactly characterized by semilinear functions. It establishes both directions by reducing between stable function computation and stable graph decision.
- Only-if direction: The reduction tracks produced and consumed output molecules with separate indicator species.For each output Yi, species YP_i and YC_i represent production and consumption counts, allowing the tested value to change monotonically in either direction.
- Only-if direction: Every function stably computable by a CRC is semilinear.The proof constructs a CRD that decides the function’s graph, despite outputs potentially changing while computation proceeds.
- If direction: Every semilinear function is stably computable by a CRC.The construction uses a predicate decider to search candidate output values represented through production and consumption species.
- If direction: The construction stabilizes when the candidate output matches the function and the predicate decider reaches an output-stable yes state.If the candidate is incorrect, the decider produces L0, enabling further output adjustment; once the correct value is found and no L0 can recur, the output is stable.
- Main theorem: A function f:N^k→N^l is stably computable by a CRC if and only if it is semilinear.This theorem follows immediately from the two preceding lemmas.
- Limitation: The converse construction reduces computation to deciding a related set bF rather than the graph F directly.The paper identifies this indirect reduction as an unsatisfactory aspect because direct monotonic production for the CRC is not obvious.
4 Semilinear functions can be quickly computed
The paper gives semilinear-function computation a systematic CRN construction and shows that these functions converge in expected O(log^5 n) time. The construction combines affine partial functions, semilinear predicate decisions, and parallel fast and slow computations.
- Construction: An affine partial function can be computed in expected time O(n log n) with monotonically increasing output counts and at most O(n) produced molecules.Monotonic output production supports composing the computation with later CRNs.
- Construction: The construction runs multiple CRNs in parallel and activates only the outputs associated with the predicate-selected partial function.The expected completion time remains O(n log n) because the number of parallel computations depends on the fixed function, not n.
- Construction: A semilinear function can be decomposed into finitely many affine partial functions whose domains are linear sets.The construction selects the applicable partial function using semilinear predicate computation.
- Fast kinetic computation: A fast, error-prone computation is paired with a slow deterministic computation that detects incorrect answers and corrects them.This technique preserves eventual correctness while enabling polylogarithmic expected time.
- Fast kinetic computation: Every semilinear function can be stably computed in expected time O(log^5 n).The bound is stated for input size n measured by the number of input molecules.
5 Conclusion
The paper characterizes deterministic CRN function computation as exactly the class of functions with semilinear graphs and shows that all such functions can be computed efficiently. It also identifies limitations involving carefully chosen initial contexts and the nontrivial relationship between stochastic CRNs and mass-action systems.
- Conclusion: Deterministic CRN computation corresponds exactly to functions with semilinear graphs.The computation is guaranteed to converge correctly regardless of reaction order.
- Conclusion: All functions in the semilinear class can be computed efficiently.
- Limitations: The systematic construction relies on a carefully chosen initial context containing extra molecules, including some species present as a single-copy leader.
- Limitations: Whether deterministic computation can dispense with this environmental control remains unanswered.The paper identifies prescribed molecular-count generation from an uncontrolled context as computationally challenging.
- Mass-action systems: The relationship between deterministic stochastic-CRN computation and parameter-robust mass-action systems is not simple.In mass-action models, one example loses floor-function computation, while another can produce rate-dependent outputs under specified conditions.