Leaderless Deterministic Chemical Reaction Networks

Abstract

This paper answers an open question of Chen, Doty, and Soloveichik [5], who showed that a function f:ℕ^(k)  → ℕ^(l) is deterministically computable by a stochastic chemical reaction network (CRN) if and only if the graph of f is a semilinear subset of ℕ^(k + l) . That construction crucially used "leaders": the ability to start in an initial configuration with constant but non-zero counts of species other than the k species X_(1,…,X_k) representing the input to the function f. The authors asked whether deterministic CRNs without a leader retain the same power. We answer this question affirmatively, showing that every semilinear function is deterministically computable by a CRN whose initial configuration contains only the input species X_(1,…,X_k), and zero counts of every other species. We show that this CRN completes in expected time O(n), where n is the total number of input molecules. This time bound is slower than the O(log^5 n) achieved in [5], but faster than the O(n logn) achieved by the direct construction of [5].

Files

Additional details