P systems with evolutional symport and membrane creation rules solving QSAT

Theoretical Computer Science 908 (2022) 56–63 Contents lists available at ScienceDirect Theoretical Computer Science www.elsevier.com/locate/tcs Psystems with evolutional symport and membrane creation rules solving QSAT David Orellana-Martín∗, Luis Valencia-Cabrera, Mario J. Pérez-Jiménez Research Group on Natural Computing, Department of Computer Science and Artificial Intelligence, Avda. Reina Mercedes s/n, 41012, Universidad de Sevilla, Sevilla, Spain a r t i c l e i n f o a b s t r a c t Article history: Received 31 May 2021 Received in revised form 22 November 2021 Accepted 24 November 2021 Available online 6 December 2021 Keywords: Membrane computing Membrane creation QBF-SAT Computational complexity theory P systems are computing devices based on sets of rules that dictate how they work. While some of these rules can change the objects within the system, other rules can even change the own structure, like creation rules. They have been used in cell-like membrane systems with active membranes to efficiently solve NP-complete problems. In this work, we improve a previous result where a uniform family of P systems with evolutional communication rules whose left-hand side (respectively, right-hand side) have most 2 objects (resp., 2 objects) and membrane creation solved SAT efficiently, and we obtain an efficient solution to solve QBF-SAT or QSAT (a PSPACE-complete problem) having at most 1 object (respectively, 1 object) in their left-hand side (resp., right-hand side) and not making use of the environment. ©2022 Elsevier B.V. All rights reserved. 1. Introduction In 1998, Membrane Computing was introduced as a model of computation inspired by the structure and behaviour of living cells [1], abstracting the inner organelles as internal regions and chemical elements as objects of the system. The devices generated in this framework are called membrane systems or P systems. The type of region depends on the exact living model selected: On the one hand, a single cell with its inner compartments is abstracted as a cell-like membrane system (or P system) [1], where these membranes are semi-permeable walls that have control over the objects that can pass through it. The structure of these systems can be represented as a graph arranged as a rooted tree, where the root node is the outermost membrane, called skin membrane. On the other hand, several cells communicating among them can be found in nature forming a tissue. We can find two main abstractions of this phenomenon: tissue-like membrane systems, or tissue P systems [2,3], where cells can interchange objects with other cells or even with the environment, and spiking neural P systems [4], where the flow of communication through electrical impulses between neurons is abstracted through a directed graph. Cell-like membrane systems use a membrane structure that can be either static or dynamic. In the first case, objects can move through the different membranes in each step of computation. P systems with symport/antiport rules [5]make an abstraction of the symport/antiport mechanism of the organelles of a cell that allow only some objects to pass, or can interchange chemical elements from two adjoining compartments. In transition P systems and P systems with active membranes [1,6], the membrane structure could be changed, by dissolving the membranes or, in the latter, by duplicating *Corresponding author. E-mail addresses: [email protected] (D. Orellana-Martín), [email protected] (L. Valencia-Cabrera), [email protected] (M.J. Pérez-Jiménez). https://doi.org/10.1016/j.tcs.2021.11.012 0304-3975/©2022 Elsevier B.V. All rights reserved. D. Orellana-Martín, L. Valencia-Cabrera and M.J. Pérez-Jiménez Theoretical Computer Science 908 (2022) 56–63 a membrane and its contents by using division rules. Another method for duplicating a membrane is by using membrane separation rules [7], where the contents of the original membrane are distributed among the two new membranes. Another method to increase the number of membranes of the system is by means of membrane creation rules [8], where a single object creates a new membrane. It could be seen as the chemical element taking some of the substrate of the membrane where it is and using it to create a new membrane. This kind of structure-changing mechanisms makes P systems capable of efficiently solving computationally hard problems. More precisely, NP-complete or even PSPACE-complete problems have been solved by means of families of P systems that use one of these kinds of rules [9–17]. In [18], a new variant of tissue P systems was introduced, where symport/antiport rules allow objects to evolve in the process of the communication from a region to another region. Some relevant results have been obtained in [19–22], where some frontiers of efficiency have been obtained. In the framework of cell-like membrane systems, creation rules have been used lately besides evolutional communication rules in [23]to solve the SAT problem by means of a family of recognizer P systems with evolutional communication rules and creation rules. In [24], an efficient solution to QSAT is given by means of a family of recognizer polarizationless P systems with active membranes and membrane creation. In this work, we replicate the results of the latter paper; that is, we provide an efficient solution to the QSAT problem, in this case by means of a uniform family of recognizer P systems with evolutional symport rules with a minimal amount of objects per communication rule. This is an important improvement in terms of the transport of objects, since, in this case, no cooperation between objects is needed in the left-hand side to obtain presumed efficiency. For an overview of the state of the art in the area, we refer the reader to [25]. The rest of the work is organized as follows: Section 2is devoted to introduce some concepts used later through the paper. In Section 3, the definition of recognizer P systems with evolutional communication rules and membrane creation is given. In the following section, a polynomial-time and uniform solution to QSAT is given by means of a family of recognizer P systems with evolutional symport/antiport rules of length at most (1, 1)and membrane creation, and an overview of the computations and the formal verification of the design are specified. Finally, some remarks and open research lines are indicated. 2. Preliminaries Some basic notions of formal languages, set theory and other terms used throughout the paper are recalled in this section. For a deeper explanation on formal languages and membrane computing, we refer the reader to [26,27]. An alphabet is a non-empty and finite set, and its elements are called symbols. A string uover is a finite sequence of symbols from . The number of occurrences of a symbol ain uis denoted by |u|a. The length of u, denoted |u|is a∈u|u|a. A multiset m over is a pair (, fm)where fm: →Nis a mapping from to the set of natural numbers N. Let m1, m2two multisets over . The union of m1and m2, denoted by m1+m2or m1∪m2is defined as (m1+m2)(x) = fm1(x) +fm2(x), ∀x ∈. The relative complement of m2in m1, denoted by m1\m2, is the defined as (m1\m2)(x)=fm1(x)−fm2(x)if fm1(x)≥fm2(x) 0iffm1(x)< fm2(x) The empty multiset (the multiset with no elements) is denoted by ∅, and the set of all finite multisets over is denoted by Mf(). The Cantor pairing function ·, · over N2is a bijective function defined as a, b =(a+b+1)(a+b) 2+b. A decision problem Xover the alphabet is a pair (IX, θX)such that IX∈∗is the set of instances of Xand θXis a Boolean function over IX. Let Ra class of recognizer P systems. 3. Recognizer P systems with evolutional communication rules and creation rules In this section, a definition of recognizer P systems with evolutional communication rules and creation rules is given, and both the syntax and semantics are recalled. It must be taken into account that, in recognizer P systems, the output region is the environment, marked as env. Definition 1. A recognizer P system with evolutional communication rules and membrane creation of degree q ≥1is a tuple =(,,E,H,μ,M1,...,Mq,R,iin,iout) where: 1. is a finite alphabet of objects (the working alphabet), and , E⊆,  ∩E=∅ (being the input alphabet and Ethe environment alphabet); 2. His a finite set of labels; 3. μis a membrane structure whose elements are bijectively labelled by elements of H; 4. Mi, 1 ≤i ≤qare finite multisets over  \( ∪E); 5. Ris a set of rules of the following forms: 57 D. Orellana-Martín, L. Valencia-Cabrera and M.J. Pérez-Jiménez Theoretical Computer Science 908 (2022) 56–63 •Evolutional symport rules: –Between membranes: ∗[ u [ ]i]j→[ [ u]i]j, where i, j ∈H, i = j, u, u∈Mf(), |u| >0; ∗[ [ u ]i]j→[ u[ ]i]j, where i, j ∈H, i = j, u, u∈Mf(), |u| >0; –Between the environment and the skin membrane: ∗[ u [ ]i]env →[ [ u]i]env , where i ∈H, being ithe label of the skin membrane, u, u∈Mf(), |u| >0, there exists at least one a ∈usuch that a ∈ \E(otherwise, since there exists an arbitrary number of objects from Ein the environment, that rule could be applied an infinite number of times); ∗[ [ u ]i]env →[ u[ ]i]env , where i ∈H, being ithe label of the skin membrane, u, u∈Mf(), |u| >0; •Evolutional antiport rules: [ u [ v ]i]j→[ v[ u]i]j, where i ∈H, j ∈H∪{env}, u, v, u, v∈Mf(), |u|, |v| >0; •Creation rules: [ a →[ u ]i]j, where i, j ∈H, i ∈ {skin}, where skin is the label of the skin membrane, a ∈, u ∈ Mf(); 6. iin ∈H; 7. iout =env. A configuration Ctof a P system with evolutional communication rules and creation rules is described by the membrane structure at the moment tand the multisets of objects over of each membrane, and the multiset of objects over  \Eof the environment. Objects from the environment do not appear, in the initial configuration, within the P system. Therefore, E∩Mi=∅, 1 ≤i ≤q. Besides, objects from are exclusively introduced to the corresponding input membrane encoding the instance of the problem. If E=∅, it is usually omitted in the tuple of the system. The initial configuration of such a P system is defined as (M1, ..., Miin +m, ..., Mq; ∅), begin mthe input multiset and the last element being the multiset of objects from  \Ein the environment. We use the term region ito refer to a membrane if i ∈Hand to the environment if i =env. μis a tree-like structure representing the initial structure of the P system, where parent and children regions/membranes are defined in a natural way. The parent node of the skin membrane is the environment (with label env). In this sense, env is an artificial label to the environment, since it usually does not have any label. In this type of systems, due to the definition of the rules, this artificial label must be given to the environment. An evolutional symport rule [ u [ ]i]j→[ [ u]i]j, called evolutional send-in rule, can be applied to a configuration Ctif there exists a membrane labelled by iwhose parent region is labelled by j, and this region jcontains a multiset of objects u. When applying such a rule, the multiset of objects uis consumed from the region jand a multiset of objects uis produced in the membrane iin the next configuration. An evolutional symport rule [ [ u ]i]j→[ u[ ]i]j, called evolutional send-out rule, can be applied to a configuration Ct if there exists a membrane labelled by ithat contains a multiset of objects u, and whose parent region is labelled by j. When applying such a rule, the multiset of objects uis consumed from the membrane iand a multiset of objects uis produced in the region jin the next configuration. An evolutional antiport rule [ u [ v ]i]j→[ v[ u]i]jcan be applied to a configuration Ctif there exists a membrane labelled by ithat contains a multiset of objects v, and whose parent region is labelled by jand contains a multiset of objects u. When applying such a rule, the multisets of objects vand uare consumed from the membrane iand the region j, respectively, and multisets uand vare produced in the membrane iand the region j, respectively. A creation rule [ a →[ u ]i]jcan be applied to a configuration Ctif there exists a membrane labelled by jthat contains an object a. When applying such a rule, object ais consumed from membrane jand a new membrane labelled by iand containing the multiset of objects uappears as a child membrane of j. A recognizer P system with evolutional communication rules and creation rules that does not send objects from the environment to the system is said to be a P system with evolutional communication rules and creation rules without environment (or with passive environment). In this case, the set of objects of the environment Eis usually not defined in the tuple. A transition of a P system is defined as a computational step of , passing from one configuration to the next one, and denoted by Ct⇒Ct+1. A computation of a P system is a sequence of configurations such that a configuration Ct+1is always obtained from Ctby applying a computation step. C0is the initial configuration of . A family of recognizer P systems with evolutional communication rules and creation rules solving a decision problem X=(IX, θX)is a sequence  ={(n) |n ∈N}such that (n)solves every instance of length n. For this purpose, a pair of two polynomial-time computable functions (cod, s)must be provided, such that cod(u), for u ∈IXis a multiset of objects from representing the particular instance uof the problem X, and s(u)is the length of the instance. As recognizer membrane systems, {yes, no} ⊆, representing the solution for each instance, and either an object yes or an object no (but not both) must appear in the environment only in the last step of computation. 58 D. Orellana-Martín, L. Valencia-Cabrera and M.J. Pérez-Jiménez Theoretical Computer Science 908 (2022) 56–63 In [28,29], the semantics applied are maximalist in the following sense: In each membrane, an arbitrary number of creation rules can be applied, and they do not interfere with the application of other types of rules. In [24,23], more restrictive semantics were introduced. When a creation rule is applied in a membrane h, no other rules can be applied in the same computational step. In the case of P systems with evolutional symport/antiport rules, either evolutional communication rules in a maximal parallel way or a single creation rule can be applied in a membrane in a transition, but not both at the same time. As a recognizer membrane system, all the computation of a recognizer P system with evolutional communication rules and creation rules halt and either an object yes or an object no (but not both) is sent to the environment at the last step of the computation. The class of all recognizer P systems with evolutional symport/antiport rules (respectively, symport rules) and membrane creation is denoted by CCEC(k1, k2)(resp., CCES(k1, k2)), where k1represents the maximal number of objects in the LHS of an evolutional communication rule (resp., evolutional symport rule) and k2represents the maximal number of objects in the RHS of an evolutional communication rule (resp., evolutional symport rule). The class of recognizer membrane systems of this type when environment plays a passive role is denoted by  CCEC(k1, k2)(resp.,  CCES(k1, k2)). Besides, CCEC(k)(respectively,  CCEC(k)) represents the class of recognizer P systems with evolutional communication rules with rules of length at most kand membrane creation (resp., without environment), where the length of evolutional communication rules in this case is the sum of the number of objects of both the LHS and the RHS of the rule. In the same way, CCES(k)(respectively,  CCES(k)) represent the evolutional symport-only counterparts of the previously described classes of P systems. Then PMCRis the set of decision problems solvable by a uniform family of recognizer P systems from R. The term uniform is used as in circuit complexity; instead of using one P system for each instance (non-uniform solutions), a P system is able to solve all the instances of the same length. A more comprehensive introduction to the concepts of decision problems and the class of decision problems that can be solved by means of a family of membrane systems from CCES(k1, k2), as well as from the other classes mentioned above, can be extracted from [23,26,30]. The class of problems that can be solved in polynomial time by means of a uniform family of recognizer P systems with evolutional communication rules of length at most (k1, k2)(i.e., k1objects in the LHS of the rules, k2objects in the RHS of the rules) (respectively, (k)) and membrane creation is denoted by PMCCCES(k1,k2)(resp., PMCCCES(k)), and the corresponding complexity class for membrane systems without environment is PMC CCES(k1,k2)(resp., PMC CCES(k)). 4. An efficient solution to QSAT in  CCES(1, 1) In this section, an efficient solution to QSAT problem by means of a uniform family of P systems from  CCES(1, 1) with evolutional communication rules and creation rules. Each P system (n, p)from solves all instances from QSAT with nvariables and pclauses. Let ϕ∗=∃x1∀x2...Qnxnϕ(x1, ..., xn)be an existential fully quantified formula associated with a Boolean formula ϕ(x1, ..., xn) ≡C1∧...∧Cpin CNF, where each clause Cj=lj,1∨...∨lj,rj, Var(ϕ) ={x1, ..., xn}and lj,k∈{xi, ¬xi|1 ≤i ≤n} for all jand all k. Without loss of generality, we assume that existential and universal quantifiers are alternated. The problem QSAT can be described as follows: given a existential fully quantified formula ϕ∗, determine if it is true or false. For each pair n, p ∈N, we consider a recognizer P system with evolutional communication rules of length (1, 1)and creation rules (n,p)=(,,H,μ,Mskin,M<0,#>,R,iin,iout) that will solve all instances with nvariables and pclauses, where the input multiset is defined as cod(ϕ)={xi,j|xi∈Cj}∪{xi,j|¬xi∈Cj} s(ϕ)=<n,p> 1. The working alphabet is defined as follows: =∪{yes,no,d,d t,d f,d}∪ {αi|0≤i≤n2·p+5n+2p+3}∪{α i|0≤i≤n2·p+5n+2p+4}∪ {ci,j,r|1≤i≤n,1≤j≤p,r∈{t,f}}∪ {di,r|0≤i≤n,r∈{t,f}} ∪ {zi,zi,t,zi,f|1≤i≤n}∪ {xi,i,j,t,xi,i,j,f|1≤i,i≤n,1≤j≤p} . 2. The input alphabet  ={xi,j, xi,j| 1 ≤i ≤n, 1 ≤j ≤p}. 3. H={skin,1,...,p,yes,no,#}∪{<i,r>|0≤i≤n,r∈{t,f}}∪ {<i,Q,r,r>|0≤i≤n,Q∈{∃,∀},r,r∈{t,f}}∪ {<i,#>|0≤i≤n2·p+5n+2p+4} . 4. μ =[ [ ]<0,#>]skin. 5. Mskin ={z1,t, z1,f}, M<0,#>={α0, α 0}. 6. The set of rules R: 59 D. Orellana-Martín, L. Valencia-Cabrera and M.J. Pérez-Jiménez Theoretical Computer Science 908 (2022) 56–63 6.1 Rules for the counter of the elements of <0, # > [αi→[αi+1]<i+1,#>]<i,#>for0 ≤i≤n2·p+5n+2p+2 [α i→[α i+1]<i+1,#>]<i,#>for0 ≤i≤n2·p+5n+2p+3 [[αn2·p+5n+2p+3]<i,#>]<i−1,#>→[αn2+5n+2p+3[] <i,#>]<i−1,#> for0 ≤i≤n2·p+5n+2p+3 [[α n2·p+5n+2p+4]<i,#>]<i−1,#>→[α n2+5n+2p+4[] <i,#>]<i−1,#> for1 ≤i≤n2·p+5n+2p+4 [[αn2+5n+2p+3]<0,#>]skin →[αn2+5n+2p+3[] <0,#>]skin [[α n2+5n+2p+4]<0,#>]skin →[α n2+5n+2p+4[] <0,#>]skin 6.2 Rules to return a positive answer [αn2+5n+2p+3[] yes]skin →[[αn2+5n+2p+3]yes ]skin [αn2+5n+2p+3→[yes ]#]yes [[yes ]#]yes →[yes [] #]yes [[yes ]yes ]skin →[yes [] yes ]skin [[yes ]skin ]env →[yes [] skin ]env 6.3 Rules to return a negative answer [α n2+5n+2p+4→[ ] no ]skin [αn2+5n+2p+3[] no ]skin →[[αn2+5n+2p+3]no ]skin [αn2+5n+2p+3→[no ]#]no [[no ]#]no →[no [] #]no [[no ]no ]skin →[no [] no ]skin [[no ]skin ]env →[no [] skin]env 6.4 Rules to generate the membrane structure [z1,r→[z1d ]<1,r>]skin forr∈{t,f} [zi,r→[zid]<i,r>]<i−1,r>for1 ≤i≤n,iodd,r,r∈{t,f} [zi,r→[zid ]<i,r>]<i−1,r>for2 ≤i≤n,ieven,r,r∈{t,f} [zi→[zi+1,tzi+1,f]#]<i,r>for1 ≤i<n,r∈{t,f} [[zi,r]#]<i,r>→[zi,r[] #]<i,r>for1 ≤i≤n,r∈{t,f} 6.5 Rules to check which clauses are satisfied [xi,j→[x1,i,j,tx1,i,j,f]#]skin for1 ≤i≤n,1≤j≤p [xi,i,j,r→[xi+1,i,j,txi+1,i,j,f]#]<i+1,r> for1 ≤i<i≤n,1≤j≤m,r∈{t,f} [xi+1,i,j,r[] <i+1,r>]<i,r>→[[xi+1,i,j,r]<i+1,r>]<i,r> for1 ≤i<i≤n,1≤j≤p,r,r∈{t,f} [xi,i,j,t→[ci,j,tci,j,f]#]<i,t>for1 ≤i<n,1≤j≤p [xi,i,j,f→[ci,j,tci,j,f]#]<i,f>for1 ≤i<n,1≤j≤p [xn,n,j,t→[cn,j,t]#]<n,t>for1 ≤j≤p [xn,n,j,f→[cn,j,f]#]<n,f>for1 ≤j≤p [[ci,j,r]#]<i,r>→[ci,j,r[] #]<i,r> for1 ≤i≤n,1≤j≤p,r,r∈{t,f} [ci,j,r[] <i+1,r>]<i,r>→[[ci,j,r]<i+1,r>]<i,r> for1 ≤i<n,1≤j≤p,r∈{t,f} [ci,j,r→[ci+1,j,tci+1,j,f]#]<i,r> for1 ≤i≤i<n,1≤j≤p,r∈{t,f} 6.6 Rules to check if all clauses are satisfied [zn→[d0]#]<n,r>forr∈{t,f} [cn,j,r→[ ]j]<n,r>for1 ≤j≤p,r,r∈{t,f} [dj[] j+1]<n,r>→[[dj]j+1]<n,r>for0 ≤j<p,r∈{t,f} [cn,j,r→[ ]j]<n,r>for1 ≤j≤p,r∈{t,f} [dj→[dj+1]#]i+1for0 ≤j<p [[dj]#]j→[dj[] #]jfor0 ≤j≤p,r∈{t,f} [[dj]j]<n,r>→[dj[] j]<n,r>for0 ≤j≤p,r∈{t,f} [dp→[dn,r]#]<n,r>forr∈{t,f} [[dn,r]#]<n,r>→[dn,r[] #]<n,r>forr∈{t,f} 6.7 Rules to check if quantifiers are satisfied [[di,r]<i,r>]<i−1,r>→[di,r[] <i,r>]<i−1,r> for1 ≤i≤n,r,r∈{t,f} [di+1,r→[ ] <i,∃,r,r>]<i,r>for1 ≤i≤n,iodd,r,r∈{t,f} [di+1,r→[ ] <i,∀,r,r>]<i,r>for2 ≤i≤n,ieven,r,r∈{t,f} 60 D. Orellana-Martín, L. Valencia-Cabrera and M.J. Pérez-Jiménez Theoretical Computer Science 908 (2022) 56–63 [d[] <i,∃,r,r>]<i,r>→[[d]<i,∃,r,r>]<i,r> for1 ≤i≤n,iodd,r,r∈{t,f} [d→[di,r]#]<i,∃,r,r>for1 ≤i≤n,iodd,r,r∈{t,f} [[d<i,r>]#]<i,∃,r,r>→[d<i,r>[] #]<i,∃,r,r> for1 ≤i≤n,iodd,r,r∈{t,f} [[d<i,r>]<i,∃,r,r>]<i,r>→[d<i,r>[] <i,∃,r,r>]<i,r> for1 ≤i≤n,iodd,r,r∈{t,f} [d [] <i,∀,r,r>]<i,r>→[[d ]<i,∀,r,r>]<i,r> for2 ≤i≤n,ieven,r,r∈{t,f} [d →[d r]#]<i,∀,r,r>for2 ≤i≤n,ieven,r,r∈{t,f} [[d r]#]<i,∀,r,r>→[d r[] #]<i,∀,r,r>for1 ≤i≤n,r,r∈{t,f} [[d r]<i,∀,r,r>]<i,r>→[d r[] <i,∀,r,r>]<i,r> for1 ≤i≤n−1,r,r∈{t,f} [d r [] <i,∀,r,r>]<i,r>→[[d]<i,∀,r,r>]<i,r> for2 ≤i≤n,ieven,r,r,r ∈{t,f},r= r [d r →[di,r]#]<i,∀,r,r>for2 ≤i≤n,ieven,r,r,r ∈{t,f},r= r [[di,r]#]<i,∀,r,r>→[di,r[] #]<i,∀,r,r>for1 ≤i≤n,r,r∈{t,f} [[di,r]<i,Q,r,r>]<i,r>→[di,r[] <i,Q,r,r>]<i,r> for1 ≤i≤n−1,r,r∈{t,f},Q∈{∃,∀} [d1,r→[ ] yes ]skin forr∈{t,f} 7. iin =skin. 8. iout =env. 4.1. An overview of the computation Let ϕ∗with n ≥2 variables and p ≥2clauses be an instance of QSAT as defined before. Let us suppose that the number of variables, n, and the number of clauses, p, is at least 2. We consider a polynomial encoding (cod, s)from QSAT in as follows: for each formula ϕassociated to an existential fully quantified formula ϕ∗with nvariables and pclauses, s(ϕ) =n, pand cod(ϕ) ={xi,j|xi∈Cj} ∪{xi,j|¬xi∈Cj}. The proposed solution follows a brute force scheme of recognizer P systems with evolutional communication rules and membrane creation without environment, and it consists of the following stages. 4.1.1. Generation and first checking stage By applying rules from 6.4, a membrane structure is generated. In some sense, it reminds a binary tree, but having some “auxiliary” membranes, labelled by #, used to generate the objects zi+1,tand zi+1,f. The truth assignment of each branch is determined by the labels of the membranes forming that branch. Besides, using rules from 6.5, objects from cod(ϕ)will be passed throughout the membrane structure in such a way that in the level i, the i-th variable will be checked and, if the corresponding truth assignment makes true a literal in a clause j, then objects ci,j,tand ci,j,fwill appear, that will be passed by the membranes up to a membrane labelled by <n, r>, for r∈{t, f}. In this stage, the minimalist creation rules semantics take special importance. Since two creation rules cannot be applied at the same time in the same membrane, the system has to make the objects wait the correct amount of time in order to go up to the different “levels” of the system at the same time. This protocol makes the system slower than it would if maximalist semantics are chosen. On the other hand, the selected semantics make it easier to control that, in each computational step t+1, at most 2 ·mnew membranes can be created, where mis the number of membranes present in the configuration Ct. This stage takes 2n2·2psteps. 4.1.2. Second checking stage Rules from 6.6 are in charge of checking whether all the clauses are satisfied in a truth assignment. For that, if there exists an object cn,j,rin a membrane labelled by <n, r>, it means that the corresponding truth assignment makes true the clause j. Therefore, a membrane labelled by jis created within such a membrane <n, r>. Object d0will go through all membranes within the membrane <n, r>, creating a “auxiliary” membrane within them and passing to the next one, possibly arriving to membrane p. In that case, object dpcreates a new auxiliary membrane with an object dn,r, that will be useful in the next stage. This stage takes 3p +5steps. 4.1.3. Quantifier checking stage If an object di,r(r∈{t, f}) appears in a membrane, then the quantifier in this level is checked. Depending on the parity of the level, either a universal or an existential quantifier is checked. In the generation stage, objects dand d were created for this purpose. On the one hand, when an existential quantifier is being checked, an object dwill exist in such a membrane, and will change into an object di−1,rif and only if there is at least one object di,rthat has created a membrane <i, ∃, r, r>. On the other hand, when a universal quantifier is to be checked, an object d will be present in such a membrane, and will change into an object di−1,rif and only if there are two objects di,rthat have created two membranes labelled by 61 D. Orellana-Martín, L. Valencia-Cabrera and M.J. Pérez-Jiménez Theoretical Computer Science 908 (2022) 56–63 <i, ∀, r, r>. These objects will reach the skin membrane giving way to the last stage. This whole stage is computed by the application of rules from 6.6. This stage takes 8n −6steps if nis even and 8nsteps if nis odd. 4.1.4. Output stage Counters αand αare used in this stage in order to know if an object d1,rhas reached the skin membrane. In such a case, a membrane labelled by yes will be created, and when object αn2·p+5n+2p+3reaches the skin membrane, it will go into membrane yes and will change into an object yes that will be sent to the environment. In the case that object d1,rdoes not appear in the skin membrane, object α n2·p+5n+2p+4will generate a membrane labelled by no, that will make the counter αn2·p+5n+2p+3change into an object no, that will be sent to the environment. Rules from 6.2 and 6.3 are the responsible of this stage, that takes p +8steps if nis even and p +9steps if nis odd. 4.2. Formal verification Next, we prove that provides a polynomial time and uniform solution to QSAT. Theorem 1. QSAT ∈PMCCCES(1,1) The family of P systems verifies the following: •Every system of the family is polynomially uniform by Turing machines because, for each n, p ∈N, the rules of (n, p)of the family are recursively defined from n, p ∈Nand the amount of resources needed to build an element of the family is of a polynomial order in nand p. •The pair (cod, s)of polynomial-time computable functions defined fulfill the following: for each formula ϕ∗of QSAT, s(ϕ∗)is a natural number, cod(ϕ∗)is an input multiset of the system (s(ϕ∗)) and for each ϕ∈IQSAT, s−1(ϕ∗)is a finite set. •The family is polynomially bounded: for each input formula ϕ∗of QSAT, the P system (n, p)with input cod(ϕ∗) takes ksteps, with k ≤2n2+10n +4p +12 steps, being nthe number of variables and pthe number of clauses of ϕ∗. •The family is sound with regard to (X, cod, s): for each formula ϕ∗, if the computation of (s(ϕ∗)) +cod(ϕ∗)is an accepting computation, then ϕ∗is true. •The family is complete with regard to (X, cod, s): for each input formula ϕ∗such that it is satisfiable, the computation of (s(ϕ∗)) +cod(ϕ∗)is an accepting computation. Corollary 1. PSPACE ⊆PMC CCES(1,1) Proof. It suffices to know that QSAT is aPSPACE-complete problem, QSAT ∈PMC CCES(1,1)and the class PMC CCES(1,1)(in general, PMCR) is closed under polynomial-time reduction and under complementation [30]. Corollary 2. PSPACE ⊆PMC CCES(2) Proof. It suffices to see that, in the family the maximum amount of objects in an evolutional communication rule is 2. 5. Conclusions and future work In this work, a previous result has been improved, passing from being able to solve a NP-complete problem (SAT) by means of a family of membrane systems from CCEC(2, 2)to solving a PSPACE-complete problem (QSAT) by means of a family of membrane systems from  CCES(1, 1). This is a demonstration of the power of creation rules, showing that rules with a minimal number of objects both in the LHS and in the RHS are enough to reach presumed efficiency; that is, to solve problems supposed not to be solvable in polynomial time by a Turing machine. The use of division rules and separation rules with this length of evolutional symport/antiport rules give tissue P systems the power to efficiently solve only problems from P[18,19]. An interesting research work would be to investigate the same result for tissue-like membrane systems. From the beginning, creation rules have been only used in cell P systems, because of the biological inspiration of the use of parts of a membrane to create a new membrane within it, but using creation rules in tissue P systems, where new cells would be created in the environment, and not in the cell itself, would be an interesting research line. Declaration of competing interest The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper. 62 D. Orellana-Martín, L. Valencia-Cabrera and M.J. Pérez-Jiménez Theoretical Computer Science 908 (2022) 56–63 Acknowledgements This work was supported by “FEDER/Ministerio de Ciencia e Innovación – Agencia Estatal de Investigación/ _Proyecto (TIN2017-89842-P)” - MABICAP. D. Orellana-Martín also acknowledges Contratación de Personal Investigador Doctor. (Convocatoria 2019) 43 Contratos Capital Humano Línea 2. Paidi 2020, supported by the European Social Fund and Junta de Andalucía. References [1] Gh. P˘ aun, Computing with membranes, Tech. Rep., Turku Centre for Computer Science, 1998. [2] C. Martín-Vide, G. P˘ aun, J. Pazos, A. Rodríguez-Patón, Tissue P systems, Theor. Comput. Sci. 296 (2) (2003) 295–326. [3] G. P˘ aun, M.J. Pérez-Jiménez, A. Riscos-Núñez, Tissue P systems with cell division, Int. J. Comput. Commun. Control 3(3) (2008) 295–303. [4] M. Ionescu, Gh. P˘ aun, T. Yokomori, Spiking neural P systems, Fundam. Inform. 71 (2, 3) (2006) 279–308. [5] A. P˘ aun, Gh. P˘ aun, The power of communication: P systems with symport/antiport, New Gener. Comput. 20 (3) (2002) 295–305. [6] Gh. P˘ aun, P systems with active membranes: attacking NP-complete problems, J. Autom. Lang. Comb. 6(1) (2001) 75–90. [7] L. Pan, T.-O. Ishdorj, P systems with active membranes and separation rules, J. Univers. Comput. Sci. 10 (5) (2004) 630–649. [8] M. Mutyam, K. Krithivasan, P systems with membrane creation: universality and efficiency, in: Proceedings of the Third International Conference on Machines, Computations, and Universality, MCU ’01, Springer-Verlag, Berlin, Heidelberg, 2001, pp. 276–287. [9] P. Sosík, P systems attacking hard problems beyond NP: a survey, J. Membr. Comput. 1 (09 2019). [10] A. Alhazov, C. Martín-Vide, L. Pan, Solving a PSPACE-complete problem by recognizing P systems with restricted active membranes, Fundam. Inform. 58 (2) (2003) 67–77. [11] A. Alhazov, L. Pan, Gh. P˘ aun, Trading polarizations for labels in P systems with active membranes, Acta Inform. 41 (2–3) (2004) 111–144. [12] P. Sosík, A. Rodríguez-Patón, Membrane computing and complexity theory: a characterization of PSPACE, J. Comput. Syst. Sci. 73 (1) (2007) 137–152. [13] B. Song, X. Zeng, M. Jiang, M.J. Pérez-Jiménez, Monodirectional tissue P systems with promoters, IEEE Trans. Cybern. 51 (2021) 438–450. [14] A. Leporati, L. Manzoni, G. Mauri, A.E. Porreca, C. Zandron, Solving QSAT in sublinear depth, CoRR, arXiv:1902 .03879 [abs], 2019, arXiv:1902 .03879, http://arxiv.org /abs /1902 .03879. [15] T. Ishdorj, A. Leporati, L. Pan, X. Zeng, X. Zhang, Deterministic solutions to QSAT and Q3SAT by spiking neural P systems with pre-computed resources, Theor. Comput. Sci. 411 (25) (2010) 2345–2358, https://doi .org /10 .1016 /j .tcs .2010 .01.019. [16] A.E. Porreca, A. Leporati, G. Mauri, C. Zandron, P systems with elementary active membranes: beyond NP and coNP, in: M. Gheorghe, T. Hinze, G. Paun, G. Rozenberg, A. Salomaa (Eds.), Membrane Computing - 11th International Conference, CMC 2010, Jena, Germany, August 24–27, 2010, in: Lecture Notes in Computer Science, vol. 6501, Springer, 2010, pp. 338–347. Revised Selected Papers. [17] A. Alhazov, R. Freund, On the efficiency of P systems with active membranes and two polarizations, in: G. Mauri, G. Paun, M.J. Pérez-Jiménez, G. Rozenberg, A. Salomaa (Eds.), Membrane Computing, 5th International Workshop, WMC 2004, Milan, Italy, June 14–16, 2004, in: Lecture Notes in Computer Science, vol. 3365, Springer, 2004, pp. 146–160. Revised Selected and Invited Papers. [18] B. Song, C. Zhang, L. Pan, Tissue-like P systems with evolutional symport/antiport rules, Inf. Sci. 378 (2017) 177–193. [19] L. Pan, B. Song, L. Valencia-Cabrera, M.J. Pérez-Jiménez, S.F. Hafstein, The computational complexity of tissue P systems with evolutional symport/antiport rules, Complexity 2018 (Jan. 2018). [20] D. Orellana-Martín, L. Valencia-Cabrera, B. Song, L. Pan, M.J. Pérez-Jiménez, Narrowing frontiers with evolutional communication rules and cell separation, in: Proceedings of the 16th Brainstorming Week on Membrane Computing, Sevilla, Spain, 2018, pp. 123–162. [21] D. Orellana-Martín, L. Valencia-Cabrera, B. Song, L. Pan, M.J. Pérez-Jiménez, Tuning frontiers of efficiency in tissue P systems with evolutional communication rules, Complexity 2021 (Apr. 2021). [22] B. Song, K. Li, X. Zeng, Monodirectional evolutional symport tissue P systems with promoters and cell division, IEEE Trans. Parallel Distrib. Syst. (2021). [23] B. Song, K. Li, D. Orellana-Martín, L. Valencia-Cabrera, M.J. Pérez-Jiménez, Cell-like P systems with evolutional symport/antiport rules and membrane creation, Inf. Comput. 275 (2020) 104542. [24] D. Orellana-Martín, L. Valencia-Cabrera, A. Riscos-Núñez, M.J. Pérez-Jiménez, Membrane creation in polarizationless P systems with active membranes, Fundam. Inform. 171 (2020) 297–311. [25] B. Song, K. Li, D. Orellana-Martín, M.J. Pérez-Jiménez, I. Pérez-Hurtado, A survey of nature-inspired computing: membrane computing, ACM Comput. Surv. 54 (2021) 1–31. [26] Gh. P˘ aun, G. Rozenberg, A. Salomaa, The Oxford Handbook of Membrane Computing, Oxford University Press, Inc., USA, 2010. [27] G. Rozenberg, A. Salomaa (Eds.), Handbook of Formal Languages. 3 vols., Springer-Verlag, Berlin, Heidelberg, 1997. [28] M.A. Gutiérrez-Naranjo, M.J. Pérez-Jiménez, F.J. Romero-Campero, A linear solution of subset sum problem by using membrane creation, in: J. Mira, J.R. Álvarez (Eds.), Mechanisms, Symbols, and Models Underlying Cognition, Springer Berlin Heidelberg, Berlin, Heidelberg, 2005, pp. 258–267. [29] M.A. Gutiérrez-Naranjo, M.J. Pérez-Jiménez, F.J. Romero-Campero, A linear solution for QSAT with membrane creation, in: R. Freund, G. P˘ aun, G. Rozenberg, A. Salomaa (Eds.), Membrane Computing, Springer Berlin Heidelberg, Berlin, Heidelberg, 2006, pp. 241–252. [30] M.J. Péerez-Jiménez, Álvaro Romero-Jiménez, F. Sancho-Caparrini, Complexity classes in models of cellular computing with membranes, Nat. Comput. 2(3) (2003) 265–285. 63