首页    期刊浏览 2024年09月15日 星期日
登录注册

文章基本信息

  • 标题:Reachability Problems for Continuous Chemical Reaction Networks
  • 本地全文:下载
  • 作者:Adam Case ; Jack H. Lutz ; Donald Stull
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2015
  • 卷号:2015
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:

    Chemical reaction networks (CRNs) model the behavior of molecules in a well-mixed system. 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 a new model of chemical kinetics, rate-independent continuous CRNs (CCRNs), to study the chemical computation of continuous functions. A fundamental question of a CRN is whether a state of the system is reachable through a sequence of reactions in the network. This is known as the reachability problem. In this paper, we investigate CCRN-REACH, the reachability problem for this model of chemical reaction networks. We show that, for continuous CRNs, constructing a path to a state of the network is computable in polynomial time. We also prove that a related problem, Sub-CCRN-REACH, is NP-complete.

国家哲学社会科学文献中心版权所有