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.

TitelBabbage meets Zuse: A Minimal Mechanical Computer
VerfasserRaúl Rojas
VerlagSpringer International Publishing Switzerland
ThemaBabbage, Zuse, minimal computer
KennungISBN 978-3-319-41311-2, DOI 10.1007/978-3-319-41312-9.
Erschienen inProceedings of the 15th International Conference, UCNC 2016, Manchester, UK, July 11-15, 2016. Lecture Notes of Computer Science 9726.
Größe oder Längepp. 25-34
RechteCopyright by Springer. When citing this work cite the original link.