Reachability problems for continuous chemical reaction networks

作     者：Case, Adam Lutz, Jack H. Stull, D. M. 

作者机构：Drake Univ Dept Math & Comp Sci Des Moines IA 50311 USA Iowa State Univ Dept Comp Sci Ames IA 50011 USA 

出 版 物：《NATURAL COMPUTING》 (Nat. Comput.)

年 卷 期：2018年第17卷第2期

页      面：223-230页

核心收录：

学科分类：08[工学] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：National Science Foundation [1247051, 1545028] Direct For Computer & Info Scie & Enginr Division Of Computer and Network Systems Funding Source: National Science Foundation Division of Computing and Communication Foundations Direct For Computer & Info Scie & Enginr Funding Source: National Science Foundation 

主　　题：Reachability Continuous chemical reaction networks Analysis of algorithms 

摘      要：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 number of its reactions, is NP-complete.