On the computational efficiency of tissue P systems with evolutional symport/antiport rules

Tissue P systems with evolutional symport/antiport rules are a variant of tissue P systems, where objects are communicated through regions by symport/antiport rules, and objects may evolve during this process. It is known that such systems are able to solve NP problems in a polynomial time (and exponential space), when cell division is allowed. In this work, we continue to investigate the computational complexity aspects for tissue P systems with evolutional symport/antiport rules. We prove that problems beyond NP can also be solved. In particular, we show that deterministic systems of this type are able to solve all problems in the complexity class PP. Moreover, if non-deterministic systems are considered, then all problems in the class PSPACE can be solved.(c) 2023 Elsevier B.V. All rights reserved.

Automated summary

Tissue P systems with evolutional symport/antiport rules can solve problems beyond NP, including all problems in the complexity class PP for deterministic systems and all problems in the class PSPACE for non-deterministic systems.