1. On the computational efficiency of tissue P systems with evolutional symport/antiport rules
- Author
-
Linqiang Pan, Bosheng Song, Claudio Zandron, Pan, L, Song, B, and Zandron, C
- Subjects
Computational complexity ,Information Systems and Management ,Cell division ,Artificial Intelligence ,Membrane computing ,Bio-inspired computing ,Software ,Tissue P system ,Management Information Systems - Abstract
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.
- Published
- 2023