Babbage meets Zuse: A Minimal Mechanical Computer
Raúl Rojas – 2016
Chemical Reaction Networks (CRNs) model the behavior of molecules in a well-mixed solution. The emerging field of molecular programming uses CRNs not only as a descriptive tool, but as a programming language for chemical computation. Recently, Chen, Doty and Soloveichik introduced rate-Independent continuous CRNs (CCRNs) to study the chemical computation of continuous functions. A fundamental question for any CRN model is reachability, the question whether a given target state is reachable from a given start state via a sequence of reactions (a path) in the network. In this paper, we investigate CCRN-REACH, the reachability problem for rate-independent continuous chemical reaction networks. Our main Theorem is that, for CCRNs, deciding reachability - and constructing a path if there is one - is computable in polynomial time. This contrasts sharply with the known exponential space hardness of the reachability problem for discrete CRNs. We also prove that the related problem Sub-CCRN-REACH, which asks about reachability in a CCRN using only a given numer of its reactions, is NP-complete.