Efficient solutions to hard computational problems by P systems with symport/antiport rules and membrane division

Efficient solutions to hard computational problems by P systems with symport/antiport rules and membrane division Bosheng Song a,b, Mario J. Pérez-Jiménez b, Linqiang Pan a a Key Laboratory of Image Information Processing and Intelligent Control, School of Automation, Huazhong University of Science and Technology, Wuhan 430074, Hubei, China b Research Group on Natural Computing, Department of Computer Science and Artificial Intelligenc, University of Sevilla, Avda. Reina Mercedes s/n, 41012 Sevilla, Spain Keywords: Cell-like P system Symport/Antiport rule Membrane division Subset Sum problem QSAT problem abstract P systems are computing models inspired by some basic features of biological membranes. In this work, membrane division, which provides a way to obtain an exponential workspace in linear time, is introduced into (cell-like) P systems with communication (symport/antiport) rules, where objects are never modified but they just change their places. The computational efficiency of this kind of P systems is studied. Specifically, we present a (uniform) linear time solution to the NP-complete problem, Subset Sum by using division rules for elementary membranes and communication rules of length at most 3. We further prove that such P system allowing division rules for non-elementary membranes can efficiently solve the PSPACE-complete problem, QSAT in a uniform way. 1. Introduction Membrane computing is a flexible and versatile branch of natural computing, which arises as an abstraction of the compartmentalized structure of living cells, and the way biochemical substances are processed in (or moved between) membrane bounded regions P˘aun (2000). Membrane computing is a paradigm providing computing devices called P systems, which are parallel, non-deterministic and distributed computational models. Inspired by that structure, two main classes of P systems have been investigated: (a) a hierarchical arrangement of membranes as in a cell P˘aun (2000), processing information by multisets of symbols; and (b) a net of processor units placed in the nodes of a directed graph, inspired by the cell intercommunication in tissues Martín-Vide et al. (2003) or inspired by the way neurons communicate with each other by means of short electrical impulses, identical in shape (voltage), but emitted at precise moments of time Ionescu et al. (2006). These models have two interesting properties: the capability to solve as many problems as a Turing machine (computational completeness) and the ability to solve computationally hard problems in a feasible time, by trading space for time (computational efficiency). General information on membrane computing can be found in P˘ aun et al. (2010), Frisco (2009), and for the most up-to-date references, one can refer to the P systems website http://ppage.psystems.eu. A basic P system is based on a cell-like arrangement of membranes, that are placed in a nested hierarchical structure; each membrane delimits a compartment (also called region) where multisets of objects and rules for evolving these objects are placed. A membrane with no compartments inside is called elementary, otherwise it is called non-elementary. The outmost membrane is called askin membrane, the space outside the skin membrane is called the environment. There are two main types of evolution rules of cell-like P systems associated with membranes: multiset rewriting rules and communication (symport/antiport) rules. The present work focuses on a class of P systems with symport/antiport rules, which were proposed in P˘ aun and P˘ aun (2002). Symport rules are of form (u,in)or(u,out), and move objects of multiset uthrough a membrane; antiport rules are of form (u, out;v,in), and move the objects of multiset uoutside a membrane while moving the objects of multiset vinside. Cell-like P systems have been studied widely. Up to now, researchers have proposed lots of classes of cell-like P systems, and many of them have been proved to be computationally complete (see, e.g., Alhazov and Freund (2005), Alhazov et al. (2006), Bernardini and Gheorghe (2003), Ciobanu et al. (2007), P˘ aun and P˘ aun (2002), P˘ aun et al. (2005)). The computational efficiency of cell-like P systems has also been investigated P˘ aun et al. (2010). A particularly interesting class of cell-like P systems is that of P systems with active membranes P˘ aun (2000), which contain object evolution rules, in communication rules, out communication rules, dissolving rules and membrane division rules. Membrane division rules can generate an exponential workspace in polynomial time (even in linear time). Therefore, P systems with active membranes can be used to solve computationally hard problems by a time-space trade-off P˘ aun (2001), Pérez-Jiménez and Riscos-Nú˜ nez (2004), Pérez-Jiménez and Riscos-Nú˜ nez (2005). In this work, membrane division is introduced into cell-like P systems, and they evolve by means of symport/antiport or division rules, that is, we present a class of P systems with symport/antiport rules and membrane division, where objects are never modified but they just change their places, moreover, objects can be communicated with the environment only through the skin membrane. The computational efficiency of such kind of P systems is studied. Specifically, we present polynomial time solutions to the Subset Sum problem by using division rules for elementary membranes and for the QSAT problem by using division rules for non-elementary membranes. In both cases, the solutions are uniform and they are obtained by using communication rules of length at most 3. 2. Preliminaries In this Section, we only introduce some basic notions and notations from formal languages theory. Readers can refer to Rozenberg and Salomaa (1997) for details. An alphabet is a non-empty set and their elements are called symbols. An ordered finite sequence of symbols over forms a string. The length of a string u, denoted by |u|, is the number of occurrences of symbols it contains. We denote by ∗the set of all strings over . The empty string (with length 0) is denoted by , and by +=∗\{}we denote the set of non-empty strings. For an alphabet ,amultiset over is a pair (,f) where f:→Nis a mapping, Nis the set of natural numbers. If m=(,f) is a multiset, then its support is defined as supp(m)={x∈|f(x)>0}. If supp(m)={a1,...,ak}then we denote m={af(a1) 1,...,a f(ak) k}.A multiset is finite if its support is a finite set. We denote by ∅ the empty multiset and by Mf() the set of all finite multisets over .Ifm1=(,f1), m2=(,f2) are multisets over , then the union of m1and m2, denoted by m1+m2, is the multiset (,g), where g(x)=f1(x)+f2(x) for each x∈; the relative complement of m2in m1, denoted by m1\m2, is the multiset (,g), where g(x)=f1(x)−f2(x)iff1(x)≥f2(x), and g(x) = 0 otherwise. 3. P systems with symport/antiport rules and membrane division In this Section, we study P systems with symport/antiport rules, a class of computing devices aiming to abstract the active transport of molecules across the membranes. In this kind of P systems, objects are processed in a pure communicative way, that is, objects do not evolve and only change their places during the computation process. Membrane division rules are allowed in such P systems. Definition 1. A P system with symport/antiport rules and membrane division of degree q≥1 is a tuple = (, E,,M1,...,Mq,R1,...,Rq,i out), where: •is an alphabet (the working alphabet) and E⊆; •is a rooted tree with qnodes labeled by 1, ...,q; •Mi,1≤i≤q, are finite multisets over ; •Ri,1≤i≤q, are finite sets of rules of the following forms: (a1) Symport rules: (u,out)or(u,in), for u∈Mf(), |u|>0; (a2) Antiport rules: (u, out;v,in), for u, v∈Mf(), |u|>0,|v|>0; (b) Division rules: [a]i→[b]i[c]i, for i∈{2, ...,q},i/=iout,a,b, c∈; •iout ∈{0, 1, ...,q}. A P system with symport/antiport rules and membrane division of degree q≥1 can be viewed as a set of qmembranes labeled by 1, ...,q, arranged in a hierarchical structure of a rooted tree (the root labeled by 1 is called the skin membrane), such that: (a) M1,...,Mqrepresent the finite multisets of objects initially placed in the qmembranes of the system; (b) Eis the set of objects initially located in the environment of the system, all of them available in an arbitrary number of copies; (c) R1,...,Rqare finite sets of rules (Ricorresponds to the membrane iof ); (d) iout is a distinguished region which will encode the output of the system. We use the term region i(0 ≤i≤q) to refer to membrane iin case 1 ≤i≤qand to refer to the environment in case i= 0. The length of a symport rule (u,out) or (u,in) (an antiport rule (u, out;v,in), respectively) is defined as |u|(|u|+| v|, respectively). For each membrane i∈{2, ...,q}, we denote by p(i) the parent of membrane iin the rooted tree , the “parent” of the skin membrane is the environment, denoted by p(1)=0. Aconfiguration of such a P system at any moment is described by the current membrane structure (the rooted tree), together with all multisets of objects over associated with the regions of this membrane structure and the multiset of objects over \Eassociated with the environment at that moment. The initial configuration of (, E,,M1,...,Mq,R1,...,Rq,i out)is(, M1,...,Mq;∅). A symport rule (u, out)∈Riis applicable to a configuration at a moment if membrane icontains multiset uat that moment. When such a rule is applied, multiset uis sent to the parent of membrane i. A symport rule (u, in)∈Riis applicable to a configuration at a moment if the parent of membrane icontains multiset uat that moment. When such a rule is applied, multiset uenters membrane ifrom the parent of i. An antiport rule (u, out;v,in)∈Riis applicable to a configuration at a moment if membrane icontains multiset uand its parent contains multiset vat that moment. When such a rule is applied, multiset ufrom membrane iis sent out of membrane i, and simultaneously, multiset venters region ifrom the parent of i. A division rule [a]i→[b]i[c]iis applicable to a configuration at a moment if the following conditions hold at that moment: (1) membrane icontains object a; (2) membrane iis neither the skin membrane nor the output membrane. When applying such a rule, membrane iis divided into two membranes with the same label: in the first copy, object ais replaced by object b, in the second one object ais replaced by object c, and all the objects in the original membrane, different from the object triggering the rule, are replicated in the two new membranes. Besides, if membrane iis a non-elementary membrane, then all membranes inside membrane ias well as objects contained in them, will be replicated in each of the new membranes. The rules of a P system with symport/antiport rules and membrane division are used in a maximally parallel way. At each step, a maximal multiset of rules is applied (no further rule can be added being applicable) with the following restriction: when a membrane is divided, the division rule is the only one which is applied for that membrane at that step, the objects inside that membrane do not evolve by means of communication rules. The objects in the new membranes resulting from division could participate in the interaction with the objects in the (upper or lower) neighbor of membranes by means of communication rules at the next step if these new membranes are not divided once again. Starting from the initial configuration and applying rules as described above, one obtains a sequence of consecutive configurations. Each passage from a configuration Cto a next configuration Cis called a transition and denoted by C⇒C.A configuration is a halting configuration if no rule of the system is applicable to it. A computation of such a P system is a (finite or infinite) sequence of transitions between configurations such that: (1) the first term of the sequence is the initial configuration; (2) each non-first term of the sequence is obtained from the previous configuration by applying rules in a maximally parallel way with the above mentioned restriction; (3) if the sequence is finite, then the last term of the sequence is a halting configuration, and such a computation is called a halting computation. Only halting computations give a result, encoded by the multiset of objects present in the output region iout. 3.1. Recognizer P systems with symport/antiport rules and membrane division Recognizer P systems were introduced in Pérez-Jiménez et al. (2006), as a natural framework to solve decision problems. Definition 2. A recognizer P system with symport/antiport rules and membrane division of degree q≥1 is a tuple =(, E,,,M1,...,Mq,R1,...,Rq,i in,i out), such that: •(, E,,M1,...,Mq,R1,...,Rq,i out) is a P system with symport/antiport rules and membrane division of degree q≥1; •has two distinguished objects yes and no, with at least one copy of them present in some multisets M1,...,Mq, but none of them present in E; •is an (input) alphabet strictly contained in , and such that E⊆\; •M1,...,Mqare finite multisets over \; •iin ∈{1, ...,q}is the input membrane, and iout =0; •all computations halt; •if Cis a computation of , then either object yes or object no (but not both) must have been released into the environment, and only at the last step of the computation. For each finite multiset w∈Mf(), the computation of a P system with symport/antiport rules and membrane division with input wstarts from a configuration of the form (, M1,...,Miin + w,...,Mq,∅), where the input multiset wis added to the contents of the input membrane iin. We denote by CDeC(k)(CDneC(k), respectively) the class of recognizer P systems with division rules for elementary membranes (non-elementary membranes, respectively) whose symport/antiport rules have length at most k. 3.2. Polynomial complexity classes of recognizer P systems Next, we define the concept of polynomial time solvability (in a uniform way) by means of family of P systems (see Pérez-Jiménez (2005) for details). Definition 3. A decision problem X=(IX,X) is solvable in polynomial time by a family ={(n)|n∈N}of recognizer P systems from CDeC(k)orCDneC(k), in a uniform way, if the following conditions hold: 1. The family is polynomially uniform by Turing machines. 2. There exists a pair (cod,s) of polynomial-time computable functions over IXsuch that: (a) for each instance u∈IX,s(u) is a natural number and cod(u) is an input multiset of the system (s(u)); (b) for each n∈N,s−1(n) is a finite set; and (c) the family  is polynomially bounded, sound and complete with regard to (X,cod,s). We denote by PMCCDeC(k)(PMCCDneC(k), respectively) the set of all decision problems which can be solved in a uniform way and polynomial time by means of recognizer P systems from CDeC(k) (CDneC(k), respectively). 4. Solving the Subset Sum problem by using CDeC(3) Subset Sum problem is a numerical NP-complete problem, which has been investigated widely in membrane computing. Specifically, different (uniform) polynomial time solutions have been provided by using families of P systems with active membranes Pérez-Jiménez and Riscos-Nú˜ nez (2005), P systems with membrane creation Gutiérrez-Naranjo et al. (2005), and tissue P systems with cell division Díaz-Pernil et al. (2007). Next, we present a solution to the Subset Sum problem by combining the symport/antiport rules used in tissue-like P systems and the membrane division of P systems with active membranes. The Subset Sum problem is described as follows: Given a finite set A, a weight function,w:A→N, and a constant k∈N,determine whether or not there exists a subset B ⊆A, such that w(B)=k. Let g:N×N→Nbe the function defined by g(n, k)=((n+k)(n+k+ 1)/2) + n. It is a primitive recursive and bijective function. We denote g(n,k)=n,k. For each (n, k)∈N×N, we consider the recognizer P system from CDeC(3) (n, k)=(, E,,,M1,M2,R1,R2,i in,i out), defined as follows: •={q}∪{ vi|1≤i≤n}; •E={˛i|1≤i≤n+logn+log(k+1)+7}∪{ai|1≤i≤ n+logn+log(k+1)+1}∪{bi|1≤i≤n+logn+log(k+ 1)+2}∪{ci|1≤i≤n+logn+log(k+1)+4}∪{di,j,l |1≤ i≤n, 1≤j≤log(k+1),1≤l≤n+j+1}∪{e, p}; •=∪E∪{Ai,B i|1≤i≤n}∪{g, h, m, n, z, yes, no}; •=[[]2]1; •M1={d1,1,1,...,d 1,log(k+1),1,d 2,1,1,...,d 2,log(k+1),1,..., dn,1,1,..., dn,log(k+1),1,a1,b1,c1,n,˛1,yes,no}; and M2={g, h, m, A1,...,A n}; •iin = 2istheinputmembrane; and iout = 0istheoutputregion; •The set R1consists of the following rules: r1,i≡(˛i,out ;˛i+1,in), 1 ≤i≤n+logn+log(k+1)+6. r2,i ≡(ai, out;a2 i+1,in), 1≤i≤n+logn+log(k+1). r3,i ≡(bi, out;b2 i+1,in), 1 ≤i≤n. r4,i≡(bi,out ;bi+1,in), n+1≤i≤n+logn+log(k+1)+1. r5,i ≡(ci, out;c2 i+1,in), 1 ≤i≤n. r6,i≡(ci,out ;ci+1,in), n+1≤i≤n+logn+log(k+1)+3. r7,i,j,l ≡(di,j,l, out;d2 i,j,l+1,in)1≤i≤n, 1≤j≤log(k+1) 1≤l≤n+j r8≡(an+logn+log(k+1)+1,out ;p,in). r9≡(bn+logn+log(k+1)+2,out ;e,in). r10 ≡(m n yes ,out). r11 ≡(n˛n+logn+log(k+1)+7 no,out). •The set R2consists of the following rules: r12,i ≡[Ai]2→[Bi]2[z]2,1≤i≤n. r13,i ≡(Bi, out;d2 i,1,n+2,in), 1 ≤i≤n. r14,i,j,l ≡(di,j,l, out;d2 i,j+1,l+1,in)1≤i≤n, 1≤j≤log(k+1)−1 n+2≤l≤n+log(k+1) r15,i ≡(di,log(k+1),n+log(k+1)+1vi, out;p, in), 1 ≤i≤n. r16 ≡(pq,out). r17 ≡(g,out ;e,in). r18 ≡(ep,out). r19 ≡(eq,out). r20 ≡(h,out ;cn+logn+log(k+1)+4,in). r21 ≡(emc n+logn+log(k+1)+4,out). The computation process can be divided in the following phases. •Generation phase: at the first nsteps, all possible subsets of Aare generated by applying membrane division rules to membranes with label 2. Simultaneously, 2ncopies of objects di,j,n+1,an+1,bn+1, cn+1 are produced in membrane 1, and the counter ˛ievolves in membrane 1. •Pre-checking phase: after the generation phase, there are 2ncopies of membrane 2, each of them containing a subset of A. Then as many copies of object pas the weight of the corresponding subset are introduced in membrane 2. To this aim, we should introduce enough copies of aiin membrane 1 first, then as many copies of pas object an+logn+log(k+1)+1 will be introduced in membrane 1. •Checking phase: in each membrane with label 2, the number of copies of objects pand qare compared by sending all possible pairs (p,q) to membrane 1. After doing that, a membrane with label 2 will encode a subset of Awhose weight is equal to kif and only if no object por qremains in that membrane. •Output phase: after the checking phase, the system sends an affirmative answer to the environment if there exists at least one membrane with label 2 without objects por q;oranegative answer if each membrane with label 2 contains some object(s) por q. 4.1. An overview of the computation First, we consider a pair (cod,s) of polynomial time functions over the set of instances of the Subset Sum problem. For that, let u=(A, w, k) be an instance of the problem and A={z1,z2,...,zn}. Then, •cod(u)={ vj i|w(zi)=j∧1≤i≤n}∪{qk}„ where vj i(jcopies of object vi) represents that jis the weight of element zi. •s(u)=n,k. In this situation, instance u=(A, w, k) will be processed by system (s(u)) with input multiset cod(u). In what follows, we describe informally how the recognizing P system (s(u)) from CDeC(3) with input cod(u) works. At the initial configuration, we have objects a1,b1,c1,n,˛1,d1,1,1, ...,d1,log(k+1),1,d2,1,1,...,d2,log(k+1),1,...,dn,1,1,...,dn,log(k+1),1, yes,no in membrane 1, objects A1,...,An,g,h,m,cod(u)inmembrane 2. The generation phase spends nsteps and the division rules r12,i are applied in membrane 2 producing 2ncopies of membrane 2, each of them contains a subset of A; simultaneously, in membrane 1, by using rules r2,i,r3,i,r5,i,r7,i,j,l, objects ai,bi,ci,di,j,lwill be duplicated until getting 2ncopies in exactly nsteps; besides, by applying rule r1,i, the counter object ˛iincreases its subscript by 1 at each step. Rule r1,iwill be applied in the whole computation process except for the last step in the case that the answer is negative. Note that object zis an idle object in cells with label 2. The pre-checking phase starts at step n+ 1. In this phase, we should introduce enough copies of object pin each membrane 2, but those objects are first introduced in membrane 1. Specifically, at step n+1, 2 n+1 copies of objects di,j,n+2 are produced in membrane 1 by applying rules r7,i,j,n+1 (1≤i≤n,1≤j≤log(k+1)). At next step, by using rules r13,i, one copy of object Biin each membrane 2 is exchanged with two copies of object di,1,n+2 in membrane 1 (at that step, in all membranes 2 there are at most 2ncopies of object Bi, and in membrane 1, there are 2n+1 copies of object di,1,n+2). Besides, at step n+ 2, objects di,j,n+2 (1≤i≤n,2≤j≤log(k+1)) are duplicated by using rules r7,i,j,n+2, and 2n+2 copies of objects di,j,n+3 are produced in membrane 1. At step n+ 3, objects di,j,n+3 (1≤i≤n,3≤j≤log(k+1)) are duplicated by using rules r7,i,j,n+3, and 2n+3 copies of objects di,j,n+4 are produced in membrane 1. Simultaneously, each copy of object di,1,n+2 in all membranes 2 is exchanged with two copies of object di,2,n+3 in membrane 1 (at that step, in all membranes 2 there are at most 2n+1 copies of object di,1,n+2, and in membrane 1, there are 2n+2 copies of object di,2,n+3). By applying rules r7,i,j,land r14,i,j,las many times as possible, at step n+log(k+1)+1, in each membrane 2 that contains object Bi,we obtain 2log(k+1)copies of object di,log(k+1),n+log(k+1)+1, so at least k+ 1 copies will be available. From step n+ 1 to step n+logn+log(k+1), object aiwill be duplicated by using rule r2,i, that is, at step n+logn+log(k+1), there are 2n+logn+log(k+1)copies of object an+logn+log(k+1)+1 in membrane 1. In this process, counters bi,ciincrease their subscripts by applying r4,i,r6,i. At step n+logn+log(k+1)+1, object an+logn+log(k+1)+1 in membrane 1 is exchanged with object pfrom the environment by using rule r8. All copies of objects bi,ciincrease their subscripts at this step. At step n+logn+log(k+1)+2, object bn+logn+log(k+1)+2 has 2ncopies in membrane 1 and each such copy is exchanged with object efrom the environment (rule r9). By using rule r6,i,2 ncopies of object cn+logn+log(k+1)+3 will present in membrane 1. Simultaneously, by applying rules r15,iin all membranes 2, for each element Biin the subset associated with the membrane we get min{2log(k+1),w(si)}copies of object p. The checking phase starts at step n+logn+log(k+1)+3. In this step, by using rule r16, all pairs of objects pand qpresent in any membrane with label 2 are sent to membrane 1. In this way, if the weight of the subset associated with a membrane 2 is equal to k, then no object por qremains in this membrane at the next step. Otherwise, at least one copy of object por qwill remain in the membrane. Simultaneously, in every membrane 2 object gis exchanged with object ein membrane 1 (rule r17), that is, each membrane 2 will contain one copy of object e; object ciincreases its subscript, and 2ncopies of object cn+logn+log(k+1)+4 appear in membrane 1. When the checking phase finishes, the output phase starts at step n+logn+log(k+1)+4. There are two cases. •There exists at least one membrane 2 with a subset whose weight is equal to k. In this case, at step n+logn+log(k+1)+4, if a membrane 2 contains at least one copy of object por q, then object ewill be sent to membrane 1 by using rule r18 or r19; otherwise, object ewill remain in that membrane. Simultaneously, object h in all membranes 2 is exchanged with object cn+logn+log(k+1)+4 by using rule r20 (each membrane 2 will contain one copy of object cn+logn+log(k+1)+4). At the next step, by applying rule r21, objects e,m,cn+logn+log(k+1)+4 are sent to membrane 1 in case the weight of the subset in that membrane 2 is equal to k. At step n+logn+log(k+1)+6, by using rule r10, objects m,n,yes are sent to the environment and the computation halts. Thus, the answer of the system is affirmative. •There is no membrane 2 with a subset whose weight is equal to k. In this case, at step n+logn+log(k+1)+4, object e is sent to membrane 1 from each membranes 2 by using rule r18 or r19. Simultaneously, by applying rule r20, each membrane 2 will contain one copy of object cn+logn+log(k+1)+4.At the next two steps, only the counter object ˛ievolves by applying rule r1,i. At step n+logn+log(k+1)+7, by using rule r11, objects n,˛n+logn+log(k+1)+7,no are sent to the environment and the computation halts. Thus, the answer of the system is negative. 4.2. Some formal details Family ={(n, k)|n, k ∈N}is polynomially uniform by Turing machines, because the rules of a system (n,k)ofthe family are defined recursively from the values nand k. Besides, the necessary resources for defining each such system are of polynomial order. •size of the alphabet: ((2n2+3n+8)·log(k+1)+n·log(k+1)2 +12n+8logn+46)/2 ∈O(n2·logk+n·logk2); •initial number of membranes: 2 ∈O(1); •initial number of objects: n·log(k+1)+n+10∈O(n·logk); •number of rules: ((2n2−3n+8)·log(k+1)+3n·log(k+1)2 +8logn+20n+ 40)/2 ∈O(n2·logk+n·logk2); •maximum length of a rule: 3 ∈O(1). Hence, there exists a deterministic Turing machine that builds the system (n,k) in a polynomial time with respect to nand k. According to the above mentioned computation process, it is clear that P system (n,k) with input multiset cod(u) always halts and sends to the environment object yes (at step n+logn+log(k+1)+6) or object no (at step n+logn+log(k+1)+7). Therefore, there exists a polynomial bound for the number of steps of the computation. Hence, the family of recognizer P systems with symport/antiport rules and membrane division solves the Subset Sum problem in polynomial time according to Definition 3. So, the following result is obtained. Theorem 1. SubsetSum ∈PMCCDeC(3). Corrolary 1. NP ∪co −NP ⊆PMCCDeC(3). Proof 1. Itsufficesto makethefollowing observations: theSubset Sum problem is NP-complete, SubsetSum ∈PMCCDeC(3) and the class PMCCDeC(3) is closed under polynomial time reduction, and is also closed under complement.  5. Solving the QSAT problem by using CDneC(3) In this Section, we provide a (uniform) polynomial time solution to the QSAT problem (quantified satisfiability problem), a well-known PSPACE-complete problem Papadimitriou (1994),by a family of P systems with division rules for non-elementary membranes and symport/antiport of length at most 3. Given a Boolean formula ϕ(x1,...,xn) in conjunctive normal form, with Boolean variables x1,...,xn, the sentence ϕ*=∃x1∀x2...Qnxnϕ(x1,...,xn) (where Qnis ∃if nis odd, and Qn is ∀otherwise) is said to be the (existential) fully quantified formula associated with ϕ(x1,...,xn). We say that ϕ*is satisfiable if there exists a truth assignment, , over {i:1≤i≤n∧iodd}such that each extension, *,ofover {1, ...,n}verifies *(ϕ(x1,...,xn)) = 1. The QSAT problem is the following one: Given the (existential) fully quantified formula ϕ∗associated with a Boolean formula ϕ(x1, ...,x n) in conjunctive normal form, determine whether or not ␸*is satisfiable. The solution proposed follows a brute force algorithm in the framework of recognizer P systems with symport/antiport rules and membrane division, and it consists of the following phases: •Generation phase: using membrane division for non-elementary membranes, all truth assignments for the variables associated with the Boolean formula are produced. •Checking phase: checking whether or not the formula ϕ(x1,...,xn) is satisfied. •Quantifier phase: checking whether the whole formula ϕ*with quantifiers is satisfied. Fig. 1. The initial membrane structure of the P system. •Output phase: the system sends to the environment the right answer according to the results of the previous phase. We define a family ={(t)|t∈N}of recognizer P systems from CDneC(3) such that each system (t) will process all instances of the QSAT problem with nvariables and mclauses, where t=m, n, provided that the appropriate input multiset is supplied to the system. For each (m, n)∈N×N, we consider the recognizer P system from CDneC(3), (m, n)=(, E,,,M1,...,M2n+3,R1,...,R2n+3,i in,i out), defined as follows: •={xi,j, xi,j |1≤i≤n, 1≤j≤m}. •E={di,g i|0≤i≤n2+3n+2m+3−k}∪{gn2+3n+2m+4−k} (where k=n 2is the number of universal quantifiers in ϕ*). •=∪E∪{ai,b i,t i,f i|1≤i≤n}∪{Ei|0≤i≤m+1}∪ {t, yes, no}. •=[[[[...[[[]2n+1]n[]2n−1]n−1...]2[]n+1]1[]2n]2n+2]2n+3(the root is the membrane with label 2n+ 3 whose child is labeled by 2n+ 2; this membrane has two children labeled by 2nand 1, respectively; each membrane with label i,1≤i≤n−1, contains a non-elementary membrane with label i+ 1 and an elementary membrane with label n+i, see Fig. 1). •M1={a1},Mn+i={bi},1≤i≤n,M2n+2=Mi=∅,2≤i≤n. •M2n+1={t, a2,...,a n,E 0,E 1,...,E m+1},M2n+3= {d0,g 0, yes, no}. •iin =2n+ 1istheinputmembrane, and iout = 0istheoutputregion. •The sets of rules are defined below: •Rules in Ri(1 ≤i≤n): r1,i ≡[ai]i→[ti]i[fi]i. •Rules in Ri(2 ≤i≤n): r2,i,j≡(tj,in) and r3,i,j≡(fj,in), 1 ≤j≤i−1. •Rules in Ri(3 ≤i≤n): r4,i,j≡(aj,out), 2 ≤j≤i−1. •Rules in R2n+1: r5,i≡(ai+1,out ;ti,in), 1 ≤i≤n−1. r6,i≡(ai+1,out ;fi,in), 1 ≤i≤n−1. r7≡(E0E1,out ;tn,in). r8≡(E0E1,out ;fn,in). r9,i,j≡(tixi,j,out ;Ej,in), 1 ≤i≤n,1≤j≤m. r10,i,j ≡(fixi,j, out;Ej,in), 1 ≤i≤n,1≤j≤m. r11,i,j≡(Ej+1,out ;tixi,j,in), 1 ≤i≤n,1≤j≤m. r12,i,j ≡(Ej+1, out;fixi,j,in), 1 ≤i≤n,1≤j≤m. r13 ≡(t,out ;Em+1,in). •Rules in Rn:r14 ≡(t,out). •If Qi+1 =∀(1 ≤i≤n−1): () Rules in Rn+i:r15,i≡(bi,out ;t,in). () Rules in Ri:r16,i≡(bit,out). •If Qi+1 =∃(1 ≤i≤n−1): () Rules in Rn+i:r17,i≡(t,in) and r18,i≡(bit,out). () Rules in Ri:r19,i≡(bit,out). •Rules in R2n:r20 ≡(t,in) and r21 ≡(bnt,out). •Rules in R2n+2:r22 ≡(bnt,out). •Rules in R2n+3: r23 ≡(dn2+3n+2m+3−kt yes, out). r24,i≡(di,out ;di+1,in), 0 ≤i≤n2+3n+2m+2−k. r25,i≡(gi,out ;gi+1,in), 0 ≤i≤n2+3n+2m+3−k. r26 ≡(dn2+3n+2m+3−kgn2+3n+2m+4−kno, out). 5.1. An overview of the computation In what follows, we informally describe how P system (s(ϕ*)) with input multiset cod(ϕ*) works. Let us recall that kdenotes the number of universal quantifiers in ϕ*, that is, k=n 2. At the initial configuration, we have object a1in membrane 1, object bi(1 ≤i≤n) in membrane n+i, objects a2,...,an,E1,...,Em+1, t,cod(ϕ*) in membrane 2n+ 1, objects g0,yes, no in membrane 2n+3. Let us start with the generation phase. This phase has two parallel processes. On the one hand, the system assigns truthassignments to all variables xi(1 ≤i≤n). When generation phase completes, we produce 2ncopies of membrane 2n+ 1, each of them contains a different truth assignments of the variable set {x1,..., xn}associated with the Boolean formula. On the other hand, the counter objects di,giin membrane 2n+ 3 grow their subscripts by using rules r26,i,r27,i. We describe the process of generation phase as follows. With the appearance of object aiin each membrane iat the same step, the system starts to assign truth-assignment of variable xi (1 ≤i≤n−1). Specifically, by using rule r1,iin all membranes i, each non-elementary membrane iis divided into two copies with the same label, which contain objects ti(representing the truth value true) and fi(representing the truth value false), respectively. Note that all the membranes and objects placed inside the membrane iare replicated in the new copies. At next steps, all object ti(fi, respectively) in membranes with label iwill be sent to membranes nby using rules r2,j,i(r3,j,i, respectively) (i+1≤j≤n) one by one. When object ti(fi, respectively) appears in each membrane nat the same step, rule r5,i(r6,i, respectively) is enabled and applied, object ai+1 in membrane 2n+ 1 is exchanged with object ti(fi, respectively) in membrane n. When object ai+1 appears in membranes n, by using rules r4,j,i+1 (i+2≤j≤n) one by one, object ai+1 will be presented in each membrane i+ 1 at the same step. Similar to the case of variable xi, the system continues to assign a truth-assignment to variable xi+1. It is easy to see that the process of assigning truth-assignment of variable xi(1 ≤i≤n−1) takes 2n−2i+ 1 steps. With the appearance of object anin membranes nat the same step, the system starts to assign truth-assignment of variable xn. By using rule r1,n, each non-elementary membrane nis divided into two copies at the same step, which contain objects tn(representing the truth value true) and fn(representing the truth value false), respectively. At the next step, rule r7(r8, respectively) is enabled and applied, objects E0,E1in membranes 2n+ 1 are exchanged with object tn (fn, respectively) in membranes n. The process of assigning a truthassignment to variable xntakes two steps. Hence, the generation phase takes n2+ 1 steps. The membrane structure of the system at that moment when the generation phase completes is shown in Fig. 2. Fig. 2. The membrane structure of the system when the generation phase completes. Numbers at nodes indicate labels of membranes. The checking phase takes 2msteps and consists of mloops (each loop takes 2 steps). In parallel with checking whether there is a truth assignment that makes the formula ϕevaluate to be true, the counter objects di,gialso grow their subscripts by one for each step in membrane 2n+3. At the first step of the j-th loop (1 ≤j≤m) of checking phase, objects ti,xi,j(fi, xi,j, respectively) in membrane 2n+ 1 are exchanged with object Ejin membrane nby using rule r9,i,j(r10,i,j, respectively), in case membrane 2n+ 3 encodes a truth assignment making clauses C1,...,Cjtrue. Note that for any membrane 2n+1, which contains a truth assignment that does not make the clause Cjtrue, the computation in that membrane stops at the time when r9,i,jor r10,i,jis applied. At the second step of the j-th loop (1 ≤j≤m) of checking phase, with the appearance of objects ti,xi,j(fi, xi,j, respectively) in membrane n, by using rule r11,i,j(r12,i,j, respectively), object Ej+1 in membrane 2n+ 1 is exchanged with the objects ti,xi,j(fi, xi,j, respectively) in membrane n. After n2+2m+ 1 steps, we have checked whether or not formula ϕissatisfied bythe correspondingtruth assignment.For eachclause Cjwhich is satisfied, the subscript jof Eis increased by one; hence object Em+1 will appear in membrane nif and only if its lower neighbor membrane 2n+ 1 encodes the truth assignment that satisfies all clauses. At step n2+2m+ 2, if membrane ncontains Em+1 then by using rule r13, object tin membrane 2n+ 1 is exchanged with object Em+1 in membrane n. At the next step, if object tappears in membrane n, by applying rule r14, then it will be sent to membrane n−1. The quantifier phase starts at the (n2+2m+ 4)-th step. In membrane 2n+ 3 the counter objects di,gigrow their subscripts by one for each step. A membrane with label icorresponds to the quantifier Qj, where 1 ≤i≤n−1, j=i+ 1, and a membrane with label 2n+2 corresponds to the quantifier Q1.IfQj=∀, object tis passed to the upper level only if it comes from both lower level membranes, that is, the respective clauses are satisfied for both truth values of xj.If Qj=∃, then a single object tcoming from lower level is enough. In what follows, we describe how the system simulates quantifiers ∀ and ∃. For quantifier Qi+1 =∀(1 ≤i≤n−1 and iis odd), one copy of object tcan be sent to the upper level membrane if and only if there are two copies of object tin a membrane i, where each lower level membrane provides one copy of object t. Specifically, by using rule r15,i, object biin membranes n+iis exchanged with object tin their upper level membranes i. Note that there is one copy of object biin a membrane n+i, thus, only one copy of object tis sent to membrane n+ifrom a membrane i. At the next step, objects bi,tin membranes iare sent to their upper level membranes by applying rule r16,i. In case Qi+1 =∃(1 ≤i≤n−1 and iis even), by using the rule r17,i in all membranes n+i, all copies of object twill be sent to their lower level membranes n+i. At the next step, objects bi,tare sent to membrane iby using rule r18,i. If there are two copies of object tin membrane n+i, then only one copy of object tis sent to membrane ibecause there is only one copy of object biin a membrane n+i.At the next step, objects bi,tin membranes iare sent to their upper level membranes by using rule r19,i.AsQ1=∃, by using the rules r20, r21,r22 one by one, one copy of object tis sent to the membrane 2n+3. Hence, the simulation of all universal quantifiers takes 2ksteps, and the simulation of all existential quantifiers takes 3(n−k) steps (the number of such quantifiers is n−k). Thus, the quantifier phase takes 3n−ksteps. The output phase starts at the (n2+3n+2m+4−k)-th step, and it takes 1 step (affirmative answer) or 2 steps (negative answer). Let us recall that membrane 2n+ 3 at configuration Cn2+3n+2m+3−k contains objects dn2+3n+2m+3−k,gn2+3n+2m+3−k,yes and no. There are two cases. –Affirmative answer: if object tappears in membrane 2n+ 3 at configuration Cn2+3n+2m+3−k, then rules r23 and r25,n2+3n+2m+3−kare applicable and objects dn2+3n+2m+3−k,t and yes are sent to the environment. Membrane 2n+ 3 at configuration Cn2+3n+2m+4−k only contains objects gn2+3n+2m+4−kand no. Therefore, the computation halts. –Negative answer: if object tdoes not appear in membrane 2n+3 at configuration Cn2+3n+2m+3−k, then only rule r25,n2+3n+2m+3−kis applicable. Thus, that membrane at configuration Cn2+3n+2m+4−k contains objects yes, no,gn2+3n+2m+4−k,d n2+3n+2m+3−k. At the next step, by using rule r26, objects gn2+3n+2m+4−k,d n2+3n+2m+3−k and no are sent to the environment and membrane 2n+ 3 at configurationCn2+3n+2m+5−konly contains object yes, so it isa halting configuration. 5.2. Some formal details In order to show that the family ={(m, n)|m, n ∈N} defined above is polynomially uniform by Turing machines we need to prove that (m,n) is built in polynomial time with respect to the size parameter m,nof instances of the QSAT problem (recalling that k≤n). It is easy to show that the rules of a system (m,n) of the family are defined recursively from the values m,n, and the necessary resources to construct (m,n) are as follows: •size of the alphabet: 2n2+2nm +10n+5m−2k+12∈O(n2+nm); •initial number of membranes: 2n+3∈O(n); •initial number of objects: 2n+m+7∈O(n+m); •number of rules: (7n2+8nm +23n+8m−4k+ 20)/2 ∈O(n2+nm); •maximum length of a rule: 3 ∈O(1). Thus, there exists a deterministic Turing machine that builds the system (m,n) in a polynomial time with respect to mand n. By the above checking of the computation process, we can prove that the P system (m,n) with input multiset cod(ϕ*) always halts and sends to the environment object yes or no in the last step, that is, at step n2+3n+2m+4−k, object yes is sent to the environment and the system halts; object no is sent to the environment at step n2+3n+2m+5−kand the system halts. Therefore, there exists a polynomial bound for the number of steps of the computation. Hence, the family of recognizer P systems with symport/antiport rules and membrane division solves the QSAT problem in polynomial time according to Definition 3. So, the following result is obtained. Theorem 2. QSAT ∈PMCCDneC(3). Since the complexity class PMCCDneC(3) is closed under polynomial time reductions, we have the following result. Corrolary 2. PSPACE ⊆PMCCDneC(3). 6. Conclusions and discussion The computational efficiency of different computing devices in membrane computing has been established. With regard to celllike computing devices, efficient solutions to hard problems have been given in the framework of P systems with active membranes that use evolution, send-in, send-out, dissolution and division rules. Specifically, polynomial time solutions to the SAT problem Pérez- Jiménez et al. (2003) (in a uniform way by using electrical charges) and the QSAT problem Alhazov and Pérez-Jiménez (2007) (in a semi-uniform way, without electrical charges and allowing division for non-elementary membranes) have been proposed. With regard to tissue-like computing devices, an efficient (uniform) solution to the HAM-CYCLE problem by a family of tissue P systems with cell division and symport/antiport rules of length at most 2, has been given Porreca et al. (2012). In this work, the computational efficiency of cell-like polarizationless P systems with symport/antiport rules and membrane division has been investigated. Specifically, a (uniform) linear time solution to the NP-complete problem Subset Sum by using division rules for elementary membranes and communication rules of length at most 3, has been given. We further proved that such P system can efficiently solve the PSPACE-complete problem QSAT problem, in a uniform way, when division rules for non-elementary membranes are allowed. It is worth noting that the solution to QSAT given in the paper can be adapted to a uniform solution bearing in mind that for (existential) fully quantified formula associated with ϕ(x1,...,xn), the number of universal quantifiers is n 2. We propose some open problems related to the role of communication rules in cell-like P systems with membrane division from a computational complexity point of view. (a) In the solution to QSAT proposed in this paper, division rules for non-elementary membranes have been considered. Is it possible to provide an efficient solution to QSAT by using only division rules for elementary membranes? (b) The P systems constructed in Section 4and in Section 5have both symport rules and antiport rules. What about the computational efficiency of P systems with membrane division that use only either symport or antiport rules? (c) It is known that NP ∪co −NP ⊆PMCTDC(2) Porreca et al. (2012). What about the computational efficiency of CDeC(2)? (d) The environment is not relevant for tissue P systems with symport/antiport rules and cell division from a complexity point of view Pérez-Jiménez et al. (2013). What about the efficiency of recognizer P systems from CDC(k) when the alphabet of the environment is an empty set? P systems capture the inherent degree of freedom present in biological systems through the non-determinism. With the inclusion of this ingredient, P systems are able to solve hard problems in an “efficient” way at the theoretical level by trading time for space. New boundaries between tractability and NP-hardness, in terms of syntactical ingredients of P systems, provide new tools to tackle the Pversus NP problem. Different simulators for P systems running on conventional computers have been developed during the last decade. The addition of parallel computing techniques, like those based on GPU, is accelerating these simulators. With the aid of P systems simulators, researchers aim to solve larger instances of NP hard problems than the best ones provided so far, running on electronic computers. However, we would like to stress that such simulators are not real implementation of P systems. Obviously, an efficient real implementation of P systems would provide a “constructive” proof of the result P=NP, that is, similarly to what would happen with a practical implementation of non-deterministic Turing machines. Acknowledgements The work of B. Song and L. Pan was supported by National Natural Science Foundation of China (61033003, 91130034, and 61320106005), Ph.D. Programs Foundation of Ministry of Education of China (2012014213008), and Natural Science Foundation of Hubei Province (2011CDA027). The work of M.J. Pérez-Jiménez was supported by “Ministerio de Economía y Competitividad” of Spain (TIN2012-37434), cofunded by FEDER funds. References Alhazov, A., Freund, R., 2005. P systems with one membrane and symport/antiport rules of five symbols are computationally complete. In: Proceedings of Third Brainstorming Week On Membrane Computing, Sevilla, Spain, pp. 19–28. Alhazov, A., Rogozhin, Yu., 2006. Towards a characterization of P systems with minimal symport/antiport and two membranes. In: Vol. 4361 of Lecture Notes in Computer Science. Springer, Berlin/Heidelberg, pp. 135–153. Alhazov, A., Pérez-Jiménez, M.J., 2007. Uniform solution of QSAT using polarizationless active membranes. In: Vol. 4664 of Lecture Notes in Computer Science. Springer, Berlin/Heidelberg, pp. 122–133. Bernardini, F., Gheorghe, M., 2003. On the power of minimal symport/antiport. In: Proceedings of the 3rd Workshop on Membrane Computing, Tarragona, pp. 72–83. Ciobanu, G., Pan, L., P˘ aun, Gh., Pérez-Jiménez, M.J., 2007. P systems with minimal parallelism. Theor. Comput. Sci. 378, 117–130. Díaz-Pernil, D., Gutiérrez-Naranjo, M.A., Pérez-Jiménez, M.J., Riscos-Nú˜ nez, A., 2007. A linear solution for Subset Sum problem with tissue P systems with cell division. In: Vol. 4527 of Lecture Notes in Computer Science. Springer, Berlin/Heidelberg, pp. 170–179. Frisco, P., 2009. Computing with Cells: Advances in Membrane Computing. Oxford University Press, Oxford. Gutiérrez-Naranjo, M.A., Pérez-Jiménez, M.J., Romero-Campero, F.J., 2005. A linear solution of subset sum problem by using membrane creation. In: Vol. 3561 of Lecture Notes in Computer Science. Springer, Berlin/Heidelberg, pp. 258–267. Ionescu, M., P˘ aun, Gh., Yokomori, T., 2006. Spiking neural P systems. Fund. Inform. 71 (2–3), 279–308. Martín-Vide, C., Pazos, J., P˘ aun, Gh., Rodriguez-Paton, A., 2003. Tissue P systems. Theor. Comput. Sci. 296 (2), 295–326. Papadimitriou, C.H., 1994. Computational Complexity. Addison-Wesley, Reading, Mass. P˘ aun, A., 2000. On P systems with active membranes. In: Proceedings of the Second International Conference on Unconventional Models of Computation, UMC’2K, Brussels, Belgium, pp. 187–201. P˘ aun, A., P˘ aun, Gh., 2002. The power of communication: P systems with symport/antiport. New Gener. Comput. 20 (3), 295–305. P˘ aun, Gh., 2000. Computing with membranes. J. Comput. Syst. Sci. 61 (1), 108–143. P˘ aun, Gh., 2001. P systems with active membranes: attacking NP-complete problems. J. Auto. Lang. Comb. 6, 75–90. P˘ aun, Gh., Pazos, J., Pérez-Jiménez, M.J., Rodríguez-Patón, A., 2005. Symport/antiport P systems with three objects are universal. Fund. Inform. 64, 1–4. P˘ aun, Gh., Rozenberg, G., Salomaa, A., 2010. The Oxford Handbook of Membrane Computing. Oxford University Press, Oxford. Pérez-Jiménez, M.J., Romero-Jiménez, A., Sancho-Caparrini, F., 2003. Complexity classes in models of cellular computing with membranes. Nat. Comput. 2 (3), 265–285. Pérez-Jiménez, M.J., Riscos-Nú˜ nez, A., 2004. A linear time solution to the Knapsack problem using P systems with active membranes. In: Vol. 2933 of Lecture Notes in Computer Science. Springer, Berlin/Heidelberg, pp. 250–268. Pérez-Jiménez, M.J., Riscos-Nú˜ nez, A., 2005. Solving the Subset-Sum problem by active membranes. New Gener. Comput 23, 367–384. Pérez-Jiménez, M.J., 2005. An approach to computational complexity in membrane computing. In: Vol. 3365 of Lecture Notes in Computer Science. Springer, Berlin/Heidelberg, pp. 85–109. Pérez-Jiménez, M.J., Romero-Jiménez, A., Sancho-Caparrini, F., 2006. A polynomial complexity class in P systems using membrane division. J. Auto. Lang. Comb. 11 (4), 423–434. Pérez-Jiménez, M.J., Riscos-Nú˜ nez, A., Rius-Font, M., Romero-Campero, F.J., 2013. A polynomial alternative to unbounded environment for tissue P systems with cell division. Int. J. Comput. Math. 90 (4), 760–775. Porreca, A.E., Murphy, N., Pérez-Jiménez, M.J., 2012. An optimal frontier of the efficiency of tissue P systems with cell division. In: Proceedings of the Tenth Brainstorming Week on Membrane Computing, Volume II, Sevilla, Spain, pp. 141–166. Rozenberg, G., Salomaa, A., 1997. Handbook of Formal Languages, vol. 3. Springer- Verlag, Berlin.