We investigate the computational power of Step-Cycle Chemical Reaction Networks (CRNs) when restricted to void reactions of size at most (3, 1). Step-Cycle CRNs extend the previously introduced step CRN model by repeatedly cycling through a fixed sequence of species additions and reaction phases. We show that even under the severe constraint of trimolecular void rules—which can only delete or preserve species—the model retains full computational power. In particular, we prove that (3,1) void Step-Cycle CRNs can polynomially simulate (1) any general CRN, (2) any general Step CRN, and (3) any general Step-Cycle CRN. Ultimately, these results demonstrate that the Step-Cycle model retains its complete expressive power even when restricted to (3, 1)-size void rules.

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

Polynomial Simulations of CRN Models with Trimolecular Void Step-Cycle CRNs

  • Austin Luchsinger,
  • Aiden Massie,
  • Robert Schweller,
  • Evan Tomai,
  • Tim Wylie

摘要

We investigate the computational power of Step-Cycle Chemical Reaction Networks (CRNs) when restricted to void reactions of size at most (3, 1). Step-Cycle CRNs extend the previously introduced step CRN model by repeatedly cycling through a fixed sequence of species additions and reaction phases. We show that even under the severe constraint of trimolecular void rules—which can only delete or preserve species—the model retains full computational power. In particular, we prove that (3,1) void Step-Cycle CRNs can polynomially simulate (1) any general CRN, (2) any general Step CRN, and (3) any general Step-Cycle CRN. Ultimately, these results demonstrate that the Step-Cycle model retains its complete expressive power even when restricted to (3, 1)-size void rules.