This paper studies the effects of interactivity on molecular computation, specifically in the Step Chemical Reaction Networks model (Step CRNs), by adding the ability for a user to interact with the system by selecting which species to add at each step, or by having some control over which reactions execute. The two proposed variants are Interactive CRNs and Randomized Interactive CRNs. We show that in Interactive CRNs, even when restricted to void (deletion-only) rules of relatively small size, if a user can decide which species to add at each step based on the configuration, reachability is PSPACE-complete when bounded and EXPTIME-hard when unbounded. In Randomized Interactive CRNs, we prove that reachability with void rules is PSPACE-complete.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Reachability in Interactive Chemical Reaction Networks

  • Aberto Avila-Jimenez,
  • Bin Fu,
  • Elise Grizzell,
  • Robert Schweller,
  • Tim Wylie

摘要

This paper studies the effects of interactivity on molecular computation, specifically in the Step Chemical Reaction Networks model (Step CRNs), by adding the ability for a user to interact with the system by selecting which species to add at each step, or by having some control over which reactions execute. The two proposed variants are Interactive CRNs and Randomized Interactive CRNs. We show that in Interactive CRNs, even when restricted to void (deletion-only) rules of relatively small size, if a user can decide which species to add at each step based on the configuration, reachability is PSPACE-complete when bounded and EXPTIME-hard when unbounded. In Randomized Interactive CRNs, we prove that reachability with void rules is PSPACE-complete.