Correspondence:
[*]
Address for correspondence: Research Group on Natural Computing, Department of Computer Science and Artificial Intelligence, Universidad de Sevilla, Avda. Reina Mercedes s/n, 41012 Sevilla, Spain
Abstract: Biological membranes play an active role in the evolution of cells over time. In the framework of Membrane Computing, P systems with active membranes capture this idea, and the possibility to increase the number of membranes during a computation. Classically, it has been considered, by using division rules, inspired in the mitosis process. Initially, the membranes in these models are supposed to have an electrical polarization (positive, negative or neutral) and the semantics is minimalist, in the sense that rules are applied in parallel, but in one transition step, each membrane can be the subject of at most one rule of types communication, dissolution or division. This paper focuses on polarizationless P systems with active membranes in which membrane creation rules are considered instead of membrane division rules as a mechanism to construct an exponential workspace, expressed both in terms of number of objects and membranes, in linear time. Moreover, the minimalist semantics is considered and some complexity results are provided in this framework, allowing to tackle the P versus NP problem from a new perspective. An original frontier of the efficiency in this context is unveiled in this paper: allowing membrane creation rules to be applicable in any membrane of the system, instead of restricting them to only elementary membranes, yields a significant boost on the computational power. More precisely, only problems in P can be efficiently solved in the restricted case, while in the non-restricted case an efficient and uniform solution to a PSPACE-complete problem is provided.
