Cell-like P systems with polarizations and minimal rules

Cell-like P systems with polarizations and minimal rules Linqiang Pan a, David Orellana-Martín b, Bosheng Song c,∗, Mario J. Pérez-Jiménez b a Key Laboratory of Image Information Processing and Intelligent Control of Education Ministry of China, School of Artificial Intelligence and Automation, Huazhong University of Science and Technology, Wuhan 430074, Hubei, China b Research Group on Natural Computing, Department of Computer Science and Artificial Intelligence, University of Sevilla, Avda. Reina Mercedes s/n, 41012 Sevilla, Spain c College of Information Science and Engineering, Hunan University, Changsha 410082, Hunan, China a b s t r a c t Keywords: Bio-inspired computing Membrane computing Minimal rule Universality PSPACE P systems with active membranes are a class of computation models in the area of membrane computing, which are inspired from the mechanism by which chemicals interact and cross cell membranes. In this work, we consider a normal form of P systems with active membranes, called cell-like P systems with polarizations and minimal rules, where rules are minimal in the sense that an object evolves to exactly one object with the application of an evolution rule or a communication rule, or an object evolves to two objects that are assigned to the two new generated membranes by applying a division rule. The present work investigates the computational power of P systems with polarizations and minimal rules. Specifically, results about Turing universality and non-universality are obtained with the combination of the number of membranes, the number of polarizations, and the types of rules. We also show that polarizationless P systems with minimal rules are equivalent to Turing machines working in a polynomial space, that is, the class of problems that can be solved in polynomial time by polarizationless P systems with minimal rules is equal to the class PSPACE. 1. Introduction A cell is the basic unit of biological organization that constitutes all living organisms. Motivated by the behavior of a single cell and multiple cells cooperating in a certain environment, a lively branch of natural computing, called membrane computing, was proposed in 1998, and the literature of membrane computing has been growing fast covering theoretical results [44,48,53,62], applications on real-life problems [40,41,64], and implementation of computation models [21,24]. The computation models in membrane computing are called P systems, which have two main families (identified by the membrane structure): cell-like P systems (a rooted tree) [36] and tissue-like P systems [23,32](a graph) or neural-like P systems [14,46,47](a directed graph). For a more detailed presentation of membrane computing the reader can refer to [39], while a complete bibliography of this area is available on the web site http://ppage .psystems .eu. Cell-like P systems have a hierarchical arrangement of membranes embedded in a main membrane, called the skin membrane [36]. The range of each membrane is defined as a compartment (region), which contains multisets of objects, *Corresponding author. E-mail addresses: [email protected] (L. Pan), [email protected] (D. Orellana-Martín), [email protected] (B. Song), [email protected] (M.J. Pérez-Jiménez). . 2 evolution rules and possibly other membranes. The outside region of the skin membrane is called environment. A membrane with no lower neighbors is called elementary; otherwise, the membrane is called non-elementary. In cell-like P systems, multisets of objects in different regions may evolve to other objects [36]or they can move between two regions [12,35]. With different biological, mathematical, or computer science motivations, the applications of rules in cell-like P systems are investigated in various ways, such as minimal parallelism [5,10], time-freeness [4,49,52], flat maximal parallelism [9,30,51, 61]. P systems with active membranes were proposed in [37], which have the important feature that each membrane has an electrical charge, that may be +(positive), −(negative), or 0 (neutral). The polarization of a membrane can be modified at a computation step. P systems with active membranes have five types of rules: (a) object evolution rules (an object evolves to a multiset of objects in a region); (b) in communication rules (an object enters a membrane); (c) out communication rules (an object exits a membrane); (d) dissolving rules (initiated by an object, a membrane is dissolved: all the objects in this membrane are released to the immediately outside region, and the rules in this dissolved membrane are lost); (e) division rules (initiated by an object, a membrane is divided into two membranes). As computing devices, an important issue of P systems with active membranes is to study the computational power [8,11]. The first result about the universality of P systems with active membranes was presented in [34], and the result about the universality of P systems with active membranes was improved by optimizing the number of membranes, the types of rules and the number of polarizations [38]. The computational power of P systems with active membranes was also investigated with the consideration of various strategies for rule application, such as asynchronous [11]or minimal parallelism [5]. Another interesting issue of P systems with active membranes is to investigate computational efficiency, since such systems offer the attractive possibility of solving NP-complete problems in feasible time [6,22,28,37], such as the SAT problem [2,37,59,60,63], Subset Sum [43], and Vertex Cover [15]. Moreover, PSPACE-complete problems can also be solved by P systems with active membranes [27,54]. It is also known that P systems with active membranes without using membrane dissolving rules can solve the QSAT problem in linear time [1]. In [3], it is shown that the QSAT problem was solved by P systems with active membranes without polarizations and using evolution rules, send-out communication rules, dissolution rules and division for elementary and non-elementary membranes. The computational complexity of (tissue) P systems with membrane division or membrane separation has also been investigated. In [58], it was proved that P systems with active membranes characterize PSPACE, that is, the class of problems solvable by P systems with active membranes is equal to PSPACE (further studied in [16–19,57]). In [55,56], an upper bound of the computational power of tissue P systems with cell separation or cell division is provided, respectively; it was thus shown that the class of problems that are solved in polynomial time by tissue P systems with cell separation or cell division is contained in the class PSPACE. The present work considers a normal form of P systems with active membranes, called cell-like P systems with minimal rules, where the rules are minimal in the sense that an object evolves to exactly one object with the application of an evolution rule or a communication rule, or an object evolves to two objects that are assigned to the two new generated membranes by applying a division rule. More specifically, we consider six types of rules in cell-like P systems with minimal rules: (1) possibly modifying an object in a region but not moving it out of the region; (2) possibly modifying an object out of a region but not moving it into the region; (3) sending out and possibly modifying an object; (4) sending in and possibly modifying an object; (5) interchanging and possibly modifying two objects; (6) dividing elementary or non-elementary membranes. The contributions of this work are summarized as follows: (a) A normal form of P systems with active membranes is proposed, where the rules are minimal. Moreover, the environment as an important component is considered in cell-like P systems with minimal rules, and it is supposed that the objects initially located in the environment have an arbitrarily large number of copies. (b) The computational power of cell-like P systems with polarizations and minimal rules (CPPMRs, for short) is investigated. It is proved that CPPMRs with arbitrarily many membranes, using rules of types (1), (2) or using rules of types (3), (5) or using rules of type (4) are able to compute the lengths of the strings of finite languages. We further prove that CPPMRs with four membranes, using rules of types (1), (2), (4) or using rules of types (3), (4) are Turing universal; the result about the universality can also be obtained for cell-like P systems with two membranes, with two polarizations and using rules of types (4), (5). (c) The computational complexity of cell-like P systems with minimal rules and without polarizations (CPMRs, for short) is also investigated. It is shown that the computational power of CPMRs is equivalent to that of Turing machines working in polynomial space, that is, the class of problems solved by CPMRs in polynomial time is equal to the class of problems PSPACE. Specifically, on the one hand, CPMRs can solve the PSPACE-complete problem QSAT; on the other hand, Turing machines can simulate CPMRs in polynomial space. The rest of the paper is organized as follows. The definitions of CPPMRs and recognizer CPPMRs are presented in section 2. The computational power of CPPMRs is investigated in section 3. In section 4, a characterization of PSPACE using CPMRs is given. Finally, conclusions and future works are presented in section 5. 3 2. Cell-like P systems with polarizations and minimal rules In this section, we directly give the definitions of CPPMRs and recognizer CPPMRs. For the basic notions used in this work from formal language theory, one can refer to [45]. Definition 1. A cell-like P system with polarizations and minimal rules of degree q ≥1 (CPPMR, for short) is a tuple =(,H,μ,E,M1,...,Mq,R,iout), where •, Eare two alphabets of objects, where objects in E(E⊆) are initially present in the environment in an infinite number of copies; •His a finite set of labels; •μis an initial membrane structure; •Mi, 1 ≤i ≤q, are initial multisets of objects placed in each membrane; •Ris a finite set of rules: (1) [ a]α1 i→[ b]α2 i, i ∈H, α1, α2∈{+, −, 0}, a, b ∈. (A simple object evolves in membrane iunder the control of the charge of the membrane i. In this process the membrane polarization may be modified.) (2) a[ ]α1 i→b[ ]α2 i, i ∈H, α1, α2∈{+, −, 0}, a, b ∈. (A simple object evolves in the father region of membrane iunder the control of the charge of the membrane i. In this process the membrane polarization may be modified. Note that one object and one membrane can be subject of only one rule.) (3) [ a]α1 i→b[ ]α2 i, i ∈H, α1, α2∈{+, −, 0}, a, b ∈. (Send out of an object from the membrane iunder the control of the charge of the membrane i. In this process, both the object and the membrane polarization may be modified.) (4) a[ ]α1 i→[ b]α2 i, i ∈H, α1, α2∈{+, −, 0}, a, b ∈. (Send an object into the membrane iunder the control of the charge of the membrane i. In this process, both the object and the membrane polarization may be modified. Note that one object and one membrane can be subject of only one rule.) (5) a[ b]α1 i→c[ d]α2 i, i ∈H, α1, α2∈{+, −, 0}, a, b, c, d ∈. (Under the control of the charge of the membrane i, an object placed in the father region of membrane iis sent into the membrane, possibly modified, and simultaneously, an object placed in membrane iis sent out. In this process, all objects and the membrane polarization may be modified.) (6) [ a]α1 i→[ b]α2 i[ c]α3 i, i ∈H, α1, α2, α3∈{+, −, 0}, a, b, c∈. (A weak division rule is applicable if membrane ihas the polarization α1and contains object a; moreover, membrane icannot be the skin membrane or the output membrane. Under the control of object aand the polarization of membrane i, such membrane is divided into two membranes: the object specified in the rule is replaced in the two new membranes, the polarizations of the two new membranes can be modified, all the other objects are duplicated in the two generated membranes. We remark that if the division membrane is a non-elementary membrane, then all membranes and objects included in this non-elementary membrane will be duplicated in each of the new generated membranes.) •iout ∈{0, 1, ..., q}is the output region. A CPPMR works in the maximally parallel manner [36]. Note that any object can be subject to only one rule of any type, and any membrane can be subject to only one rule of any type. A configuration of a CPPMR is described by the current membrane structure, the current objects in each region, and the current multiset of objects over  \Ein the environment. By using rules described above, one can define transitions among configurations. Any sequence of transitions starting from the initial configuration is called a computation. A halting configuration is such that no rule can be used in the system. The result of a halting computation is the number of specified objects present in the output region when a computation halts. A non-halting computation produces no result. We denote by N()the set of natural numbers generated by system . The family of all sets N()of natural numbers computed by systems with at most mmembranes, with at most kpolarizations, and using rules as in list-of-rules is denoted by NOPm(chark, list-of-rules). If parameter mis not bounded then it is replaced by ∗. In this work, we use recognizer CPPMRs to solve decision problems, one can consult Chapter 12 in [39,42]for details. Definition 2. A recognizer cell-like P system without polarizations and minimal rules of degree q ≥1 (recognizer CPMR, for short) is a tuple =(,H,,μ,E,M1,...,Mq,R,iin,iout), 4 such that: •(, H, μ, E, M1, ..., Mq, R, iout)is a cell-like P system with polarizations and minimal rules 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. If all computations of CPMR with the same input always produce the same result, then such CPMR is called confluent. Definition 3. A decision problem X=(IX, θX)is solvable in polynomial time by a family ={(n) |n ∈N}of recognizer P systems from CPMR in a uniform way, if the following conditions hold: •the family is polynomially uniform by Turing machines, that is, there exists a deterministic Turing machine working in polynomial time which constructs the system (n)from n ∈N; •there exists a pair (cod, s)of polynomial-time computable functions over IXsuch that: –for each instance u ∈IX, s(u)is a natural number and cod(u)is an input multiset of the system (s(u)); –for each n ∈N, s−1(n)is a finite set; –the family is polynomially bounded with regard to (X, cod, s), that is, there exists a polynomial function p, such that for each u ∈IXevery computation of (s(u)) with input cod(u)is halting and it performs at most p(|u|)steps; –the family is sound with regard to (X, cod, s), that is, for each u ∈IX, if there exists an accepting computation of (s(u)) with input cod(u), then θX(u) =1; –the family is complete with regard to (X, cod, s), that is, for each u ∈IX, if θX(u) =1, then every computation of (s(u)) with input cod(u)is an accepting one. The set of all decision problems that can be solved by recognizer CPMRs in a uniform way and polynomial time is denoted by PMCCPMR. 3. Computational power of CPPMRs In this section, we investigate the computational power of CPPMRs. We denote by NFIN the family of all finite sets of positive integers, and by NRE the family of sets of numbers which are Turing computable. Theorem 3.1. NOP∗(char3, (1), (2)) ⊆NFIN. Proof. Obviously, by using rules of types (1) and (2), an object can evolve to another object in a membrane or outside of a membrane, and the system cannot bring objects into membranes from the environment. Therefore, in any computation, the number of objects in the CPPMRs will not change by using rules of types (1) and (2). So, the number of configurations reachable by computations is finite. Therefore, the system can only generate finite sets of natural numbers. 2 Theorem 3.2. NOP∗(char3, (4)) ⊆NFIN. Proof. According to rules of type (4), an object can be sent into a membrane, and the membrane polarization may be modified. We note that only rules of type (4) exist in a CPPMR, hence the number of objects can be increased if and only if the objects placed in the environment are sent into the skin membrane. Without loss of generality, it is assumed that the skin membrane has neutral polarization. When a rule of type (4) is used, we have the following two cases: (i) the object entering into the skin membrane does not belong to E; (ii) the object entering into the skin membrane belongs to E. •Case (i): Obviously, the number of objects from the environment (that is, from \E) is finite, so the number of objects entering into the system by using the rules of type (4) is finite. •Case (ii): When a sequence of (always different) objects is sent into the system, the polarization of the skin membrane must be changed at the step that the last object of the sequence is sent into the system, otherwise, these rules can be applied forever, and the computation never stops. Therefore, a finite number of objects can enter the systems. In general, the number of objects in the system in each configuration is finite. So, the number of reachable configurations is finite and the generated set of numbers by the system is finite. Therefore, the theorem holds. 2 5 Theorem 3.3. NOP∗(char3, (3), (5)) ⊆NFIN. Proof. By using rules of type (5), an object in a membrane is exchanged with an object out of this membrane. By applying rules of type (3), an object is sent out of a membrane. The number of objects in the system cannot be increased in any computation starting from the initial configuration to a halting configuration. Hence the number of configurations of the system is finite, and the set of natural numbers generated by the system is finite. Therefore, the theorem holds. 2 In what follows, we will show some results about the Turing universality of CPPMRs, which are proved by simulating register machines. A register machine is a tuple M=(m, H, l0, lh, I), where mis a natural number (it represents the number of registers), His a set of labels, l0, lh∈Hare initial and halting one, respectively, Iis a set of instructions li:(op(r), lj, lk)(op(r)is an ADD operation or a SUB operation on register rof M) of the following forms: •li:(ADD(r), lj, lk)(when this instruction is applied, the value of register ris increased by one and then the machine will carry out one of the instructions with labels lj, lk); •li:(SUB(r), lj, lk)(when this instruction is applied, we have two cases: if the content of register ris greater than zero, then the content of register ris decreased by one and the machine will carry out the instruction with label lj; otherwise, the content of register ris not changed and the machine will carry out the instruction with label lk); •lh:HALT (the halt instruction). A register machine Mgenerates the set of numbers N(M)as follows: initially all registers are empty, Mstarts with the initial instruction l0, by applying instructions as indicated by the labels, the register machine will halt if and when it reaches the halting instruction lh. The number stored in the first register at the halting moment is called the number generated by the register machine. It is known that register machines and Turing machines are equivalent, that is, both of them characterize NRE [25]. Theorem 3.4. NOP4(char3, (3), (4)) =NRE. Proof. It is known that a register machine with three registers is universal [7,25], so we assume that the simulated register machine M=(m, H, l0, lh, I)has m =3. We construct a CPPMR that simulates M. =(,H,μ,E,M1,M2,M3,M4,R,1), where ={l,l,l |l∈H}∪{a,a}, H={1,2,3,4}, μ=[[ ]0 1[] 0 2[] 0 3]0 4, E={a}, M1=M2=M3=∅,M4={l0}, and the set Rof rules is defined as follows (each register r=1, 2, 3of Mcorresponds to a membrane labeled with r, the value of register ris represented as the number of copies of object ain membrane r. When object liappears in membrane 4, the system starts to simulate the instruction li. The number of copies of object ain membrane 1 is considered the result of a computation). •We construct the following rules to simulate an ADD instruction li:(ADD(r), lj, lk)of M: r1:li[] 0 r→[li]0 r, r2:[li]0 r→l i[] + r, r3:[l i]0 4→l i[] + 4, r4:a[] + 4→[a]0 4, r5:a[] + r→[a]0 r, r6:l i[] 0 4→[lj]0 4, r7:l i[] 0 4→[lk]0 4. 6 At the first two steps, object lievolves to l iand the polarization of membrane ris changed from neutral to positive. With the polarization of membrane 4 changes to positive, one copy of ais sent into membrane 4, returning the polarization of membrane 4 to neutral. At step 5, object ais sent into the membrane rchanging the polarization back to neutral (the number of copies of ain membrane ris increased by one, which simulates that the number stored in register ris increased by one); in parallel, object ljor lkappears in membrane 4 non-deterministically by using rule r6or r7. Therefore, the next instruction with label ljor lkwill be simulated at the next step. •We construct the following rules to simulate a SUB instruction li:(SUB(r), lj, lk)of M: r8:li[] 0 r→[li]0 r, r9:[li]0 r→l i[] − r, r10 :[a]− r→a[] + r, r11 :[l i]0 4→l i[] 0 4, r12 :l i[] 0 4→[l i]0 4, r13 :l i[] + r→[l i]+ r, r14 :l i[] − r→[l i]− r, r15 :[l i]+ r→lj[] 0 r, r16 :[l i]− r→lk[] 0 r. The simulation of a SUB instruction liworks as follows. At the first two steps, object lievolves to l iand the polarization of membrane ris changed to negative. In what follows, the system will check whether membrane rcontains object a. •Membrane rcontains at least one copy of object a(that is, the number stored in register ris greater than 0). One copy of object aevolves to a, which is sent out of membrane r, and the polarization of such membrane is changed to positive; in membrane 4, object l ievolves to l iin two steps. By using rules r13 and r15, object l ievolves to lj, returning the polarization of membrane rto neutral. Hence one copy of object ais consumed in membrane r(simulating that the number stored in register ris decreased by one), and the next instruction ljwill be simulated at the next step. •Membrane rhas no object a(that is, the number stored in register ris 0). Object l iwill be evolved to l iby using rules r11, r12. At the next two steps, object l ievolves to lk, and the polarization of membrane ris returned neutral. Hence, the next instruction lkwill be simulated at the next step. Hence, system simulates the SUB instruction of Mcorrectly. The computation can stop only when object lhappears in membrane 4 at some step. The number of copies of object a in membrane 1 is the result of the system, hence N(M) =N(), which concludes the proof. 2 Theorem 3.5. NOP4(char3, (1), (2), (4)) =NRE. Proof. For a register machine M=(3, H, l0, lh, I)with three registers, we construct the CPPMR, , to simulate M. =(,H,μ,E,M1,M2,M3,M4,R,1), where • ={l, l, l |l ∈H} ∪{a, a}, •H={1, 2, 3, 4}, •μ =[ [ ]0 1[ ]0 2[ ]0 3]0 4, •E={a}, •M1=M2=M3=∅, M4={l0}, and the rule set Ris defined as follows (each register r=1, 2, 3of Mcorresponds to a membrane labeled with r, the value of register ris represented as the number of copies of ain membrane r. The system starts to simulate the instruction li when object liappears in membrane 4. The result of the computation is encoded as the number of copies of object ain membrane 1). •The following rules are used to simulate an ADD instruction li:(ADD(r), lj, lk)of M: r1:li[] 0 r→l i[] + r, 7 r2:[l i]0 4→[l i]+ 4, r3:a[] + 4→[a]0 4, r4:a[] + r→[a]0 r, r5:[l i]0 4→[lj]0 4, r6:[l i]0 4→[lk]0 4. At the first two steps, object lievolves to l iin membrane 4, and the polarizations of membrane rand membrane 4 are changed to positive. At the next two steps, one copy of object ais sent into membrane rfrom the environment (simulating that the value of register ris increased by one) and the polarizations of membrane rand membrane 4 are returned to neutral by using rules r3, r4. In parallel, at step 4, object ljor lkappears in membrane 4 non-deterministically by using rule r5or r6. Therefore, the next instruction with label ljor lkwill be simulated at the next step. •We construct the following rules to simulate a SUB instruction li:(SUB(r), lj, lk)of M: r7:li[] 0 r→l i[] − r, r8:[a]− r→[a]+ r, r9:[l i]0 4→[l i]0 4, r10 :l i[] + r→lj[] 0 r, r11 :l i[] − r→lk[] 0 r. At the first step, object lievolves to l i, changing the polarization of membrane rto negative by using rule r7. In what follows, the system will check whether membrane rcontains object a. •Membrane rcontains at least one copy of object a(that is, the number stored in register ris greater than 0). With membrane rhaving negative polarization, one copy of object aevolves to ain membrane r, and the polarization of membrane ris changed to positive; in addition, object l iin membrane 4 evolves to ljat the next two steps by using rules r9, r10, and the polarization of membrane ris returned to neutral. Hence one copy of object ais consumed in membrane r(simulating that the value of register ris decreased by one), and the next instruction ljwill be simulated at the next step. •Membrane rhas no object a(that is, the number stored in register ris 0). At the next two steps, rules r9, r11 are used one by one, object l ievolves to lkin membrane 4, returning the polarization of membrane rto neutral. Hence, the next instruction lkwill be simulated at the next step. Hence, system correctly simulates the SUB instruction of M. The computation can stop only when object lhappears in membrane 4 at some step. The number of copies of object a in membrane 1 is the result of the system, hence N(M) =N(), which concludes the proof. 2 Theorem 3.6. NOP2(char2, (4), (5)) =NRE. Proof. For a register machine M=(3, H, l0, lh, I)with three registers, we construct a CPPMR, , to simulate M. =(,H,μ,E,M1,M2,R,2), where • ={ai, a i|1 ≤i ≤3} ∪{l, l, l, l, liv |l ∈H}, •H={1, 2}, •μ =[ [ ]0 2]0 1, •E={ai|1 ≤i ≤3} ∪{liv |l ∈H}, •M1={l0}, M2=∅, and the set Rof rules is defined as follows (the result of the computation is encoded as the number of copies of object a1 in membrane 2. When object liappears in membrane 1, the system starts to simulate the instruction li). •We construct the following rules to simulate an ADD instruction li:(ADD(r), lj, lk)of M: r1:ar[li]0 1→l i[ar]0 1, 8 r2:ar[] 0 2→[ar]0 2, r3:l i[] 0 1→[lj]0 1, r4:l i[] 0 1→[lk]0 1. An ADD instruction liis simulated in two steps. First, object liin membrane 1 is exchanged with object arfrom the environment, then object lievolves to l i. At step 2, object aris sent into membrane 2 (simulating that the number stored in register ris increased by one); in parallel, object ljor lkappears in membrane 1 non-deterministically by using rule r3 or r4. Therefore, the next instruction with label ljor lkwill be simulated at the next step. •We construct the following rules to simulate each SUB instruction li:(SUB(r), lj, lk)of M: r5:liv i[li]0 1→l i[liv i]0 1, r6:liv i[ar]0 2→a r[liv i]− 2, r7:l i[] 0 1→[l i]0 1, r8:l i[] − 2→[l i]0 2, r9:l i[] 0 2→[l i]0 2, r10 :a r[l i]0 2→lj[a r]0 2, r11 :liv i[l i]0 2→lk[liv i]0 2. The simulation of a SUB instruction liworks as follows. At the first step, object liin membrane 1 is exchanged with object liv i, then object lievolves to l i. In what follows, the system will check whether membrane 2 contains object ar. •Membrane 2 contains at least one copy of object ar(that is, the value stored in register ris greater than 0). With object liv ipresent in membrane 1, rule r6is applied, one copy of object arevolves to a r, and object liv iis sent into membrane 2; in parallel, object l ievolves to l i, which is sent into membrane 2 by applying rules r7, r8, returning the polarization of membrane 2 to neutral. At step 4, object l ievolves to lj, which is sent out of membrane 2. Hence one copy of object aris consumed in membrane 2 (it simulates that the number stored in register ris decreased by one), and the next instruction ljwill be simulated at the next step. •Membrane 2 has no object ar(that is, the value stored in register ris 0). At the next two steps, object l ievolves to l i, which is sent into membrane 2. At step 4, by applying rule r11, object l ievolves to lk, which is sent out of membrane 2. Hence, the next instruction lkwill be simulated at the next step. Hence, system correctly simulates the SUB instruction of M. The computation can stop only when object lhappears in membrane 4 at some step. The number of copies of object a1 in membrane 2 is the result of the computation, hence N(M) =N().2 4. CPMRs characterize PSPACE In this section, we first construct a family of recognizer CPMRs to solve the QSAT problem, then we will show that recognizer CPMRs can be simulated by a Turing machine working in a polynomial space. 4.1. Solving the QSAT problem by CPMRs 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 Qnis ∀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 ∧ i odd}such that each extension, σ∗(an extension of SAT models for QBF), of σover {1, ..., n}verifies σ∗(ϕ(x1, ..., xn)) =1. For further detailed description of the QSAT problem, one can refer to [1,33,50,57]. We encode the instance ϕas follows, which will be applied as input to the CPMR: cod(ϕ)=α1,1...α1,mα2,1...α2,m......αn,1...αn,m, where mis the number of clauses, and for 1 ≤i ≤n, 1 ≤j ≤m. αi,j=⎧ ⎪ ⎨ ⎪ ⎩ di,jif clause Cjcontains variable xi; d i,jif clause Cjcontains variable ¬xi; d i,jif clause Cjdoes not contain variable xiand variable ¬xi. 9 Consider the primitive recursive and bijective function from N2onto Ndefined by n, m =((n +m)(n +m +1)/2) +n. For each t=n, m, we define the recognizer CPMR ((t) =(, H, μ, E, , M1, ..., Mn+2, R, iin, iout)as follows: • = ∪{ai, ti,m+1, fi,m+1|1 ≤i ≤n} ∪{ti,j, fi,j|1 ≤i ≤n, 1 ≤j ≤m} ∪{cj, ej, e j|1 ≤j ≤m} ∪{αi|0 ≤i ≤n2+2nm + n +m +4} ∪{d, em+1, e m+1, g, g, p, s, t, t, yes, no}, •H={1, 2, ..., n +2}, •μ =[ [ [ ...[ [ ]n+1]n... ]2]1]n+2, • ={di,j, d i,j, d i,j|1 ≤i ≤n, 1 ≤j ≤m}, •E=∅, •M1={a1, g, p}, Mi={g}, 2 ≤i ≤n −1, Mn=Mn+1=∅, Mn+2={α1, g}, •iin =n +1is the input membrane, •iout =0is the environment, •the set Rconsists of the following rules: r1,i:[ai]i→[ti,1]i[fi,1]i,1≤i≤n, r2,i,j:ti,1[] j→[ti,1]j,1≤i≤n−1,i<j≤n, r3,i,j:fi,1[] j→[ fi,1]j,1≤i≤n−1,i<j≤n, r4,i,j:ti,j[di,j]n+1→cj[ti,j+1]n+1,1≤i≤n,1≤j≤m, r5,i,j:ti,j[d i,j]n+1→d[ti,j+1]n+1,1≤i≤n,1≤j≤m, r6,i,j:ti,j[d i,j]n+1→d[ti,j+1]n+1,1≤i≤n,1≤j≤m, r7,i,j:fi,j[di,j]n+1→d[fi,j+1]n+1,1≤i≤n,1≤j≤m, r8,i,j:fi,j[d i,j]n+1→cj[fi,j+1]n+1,1≤i≤n,1≤j≤m, r9,i,j:fi,j[d i,j]n+1→d[fi,j+1]n+1,1≤i≤n,1≤j≤m, r10,i,j:[ti,j+1]n+1→ti,j+1[] n+1,1≤i≤n,1≤j≤m−1, r11,i,j:[ fi,j+1]n+1→fi,j+1[] n+1,1≤i≤n,1≤j≤m−1, r12,i:[ti,m+1]n+1→ai+1[] n+1,1≤i≤n−1, r13,i:[ fi,m+1]n+1→ai+1[] n+1,1≤i≤n−1, r14,i,j:[ai]j→ai[] j,2≤i≤n−1,i<j≤n, r15 :[tn,m+1]n+1→[e1]n+1, r16 :[ fn,m+1]n+1→[e1]n+1, r17,j:cj[ej]n+1→e j+1[ej+1]n+1,1≤j≤m, r18 :[em+1]n+1→t[] n+1, {r19,i:g[t]i→s[g]i, r20,i:s[t]i→t[s]i|Qi=∀,1≤i≤n}, {r21,i:g[t]i→t[g]i|Qi=∃,1≤i≤n}, r22 :t[p]1→yes[t]1, r23 :[yes ]n+2→yes[] n+2, r24,i:[αi]n+2→[αi+1]n+2,1≤i≤n2+2nm +n+m+3, r25 :αn2+2nm+n+m+4[p]1→no[α0]1, r26 :[no ]n+2→no[] n+2. The computation of the P system (ϕ∗)that solves the QSAT problem can be divided into four phases: generation phase, checking phase, quantifier phase, and output phase. In what follows, we explain how the system works in each phase. Generation phase. A binary tree structure is produced by dividing non-elementary membranes with labels 1, 2, ..., n; in this way the system produces all truth assignments for the variables x1, ..., xn. In addition, the system checks the clauses that are satisfied by the corresponding truth assignment. Therefore, some of the objects c1, c2, ..., cmappear in a 16 C(t,k)≤max{S(t−1,i)|k<i≤d}+O(d2t+dbt), 0≤k≤d,t≥0.(8) From (2) and (8), formula (5)can be rewritten as follows: S(t,k)≤max{S(t−1)+O(d2t+dbt)}+O(bt+kt),t≥1,1≤k≤d.(9) By substituting S(t, i)(0 ≤i ≤k −1) with formula (9), we can obtain S(t,k)≤max{S(t,k−1), S(t−1)+O(d2t+dbt)}+2O(bt+kt) ≤max{S(t,k−2), S(t−1)+O(d2t+dbt)}+3O(bt+kt) ... ≤max{S(t,0), S(t−1)+O(d2t+dbt)}+(k+1)O(bt+kt) ≤max{C(t,0)+4bt+c,S(t−1)+O(d2t+dbt)}+O(kbt+k2t) ≤S(t−1)+O(d2t+dbt). Therefore, according to (2), the recurrence (3)-(5)can be rewritten as follows: S(0)=b0;(10) S(t)≤S(t−1)+O(d2t+dbt). (11) From (11), we can obtain S(t)=O(d2t2+tdbt). (12) Recall that d =nO(1)(nis the original instance size). From (1), we obtain S(t) =(nt)O(1). Finally, we assume that the computation of the CPMR is polynomial time bounded, denoted by t(n), then we obtain S(t(n)) =(nt(n))O(1)=t(n)O(1)(by assumption t(n) ≥n). 2 So, the following result is obtained. Corollary 4.3. PMCCPMR ⊆PSPACE. From Corollaries 4.1 and 4.3, we obtain the following result: Theorem 4.4. PMCCPMR =PSPACE. 5. Conclusions and further works In this work, we considered a normal form for P systems with active membranes, called cell-like P systems with polarizations and minimal rules (CPPMRs, for short). The computation power of CPPMRs has been investigated. We have shown that CPPMRs with arbitrarily many membranes, with three polarizations, using rules of types (1), (2) or using rules of types (3), (5) or using only rules of type (4) are able to compute only finite sets of non-negative integers. Besides, we proved that CPPMRs with four membranes, with three polarizations, using rules of types (1), (2), (4) or using rules of types (3), (4) are Turing universal; the result about universality can also be obtained by CPPMRs with two membranes, two polarizations and using rules of types (4), (5). Moreover, we have shown that the class of problems that can be solved in polynomial time by P systems with minimal rules and without polarizations is equal to the class of problems PSPACE. The environment plays an important role for the computation power in CPPMRs, since the number of objects in the systems can be increased (using rules of type (4)) if and only if the objects sent into the systems are initially placed in the environment. Obviously, if the alphabet of the environment of CPPMRs is empty, then CPPMRs can only generate finite sets of natural numbers. In the area of membrane computing, there exist three methods to produce new membranes, all of which are inspired by living cells: membrane division (mitosis) [37], membrane separation (membrane fission) [29], and membrane creation (autopoiesis) [26]. The computation model CPPMR considered in this work has the rule of membrane division. It is of interest to investigate cell-like P systems with polarizations and minimal rules where membrane division is replaced with membrane separation or membrane creation. The Pversus NP problem is a major unsolved problem in theoretical computer science. In computational complexity theory, the methods to tackle Pversus NP problem were presented in terms of syntactical or semantical ingredients of the models, and many interesting characterizations of the P = NP conjecture arise in membrane computing [13,20,31,53]. It is interesting to investigate the Pversus NP problem in the framework of CPPMRs. 17 Declaration of competing interest The authors declare that they have no conflicts of interest. Acknowledgements The work was supported by National Natural Science Foundation of China (61972138, 61602192, 61320106005 and 61772214), the Fundamental Research Funds for the Central Universities (531118010355). The work of the second and fourth authors are also supported by the research project TIN2017-89842-P, cofinanced by Ministerio de Economía, Industria y Competitividad (MINECO) of Spain, through the Agencia Estatal de Investigación (AEI), and by Fondo Europeo de Desarrollo Regional (FEDER) of the European Union. References [1] A. Alhazov, C. Martín-Vide, L. Pan, Solving a PSPACE-complete problem by recognizing P systems with restricted active membranes, Fundam. Inform. 58 (2003) 67–77. [2] A. Alhazov, L. Pan, Polarizationless P systems with active membranes, Grammars 7 (2004) 141–159. [3] A. Alhazov, M.J. Pérez-Jiménez, Uniform solution of QSAT using polarizationless active membranes, Lect. Notes Comput. Sci. 4664 (2007) 122–133. [4] M. Cavaliere, D. Sburlan, Time–independent P systems, Lect. Notes Comput. Sci. 3365 (2005) 239–258. [5] G. Ciobanu, L. Pan, Gh. P˘ aun, M.J. Pérez-Jiménez, P systems with minimal parallelism, Theor. Comput. Sci. 378 (2007) 117–130. [6] J. Cooper, R. Nicolescu, Alternative representations of P systems solutions to the graph colouring problem, J. Membr. Comput. 1(2) (2019) 112–126. [7] R. Freund, M. Oswald, GP systems with forbidding context, Fundam. Inform. 49 (1) (2002) 81–102. [8] R. Freund, A. P˘ aun, P systems with active membranes and without polarizations, Soft Comput. 9 (2005) 657–663. [9] R. Freund, S. Verlan, (Tissue) P systems working in the k-restricted minimally or maximally parallel transition mode, Nat. Comput. 10 (2) (2010) 821–833. [10] P. Frisco, G. Govan, P systems with active membranes operating under minimal parallelism, Lect. Notes Comput. Sci. 7184 (2012) 165–181. [11] P. Frisco, G. Govan, A. Leporati, Asynchronous P systems with active membranes, Theor. Comput. Sci. 429 (2012) 74–86. [12] P. Frisco, H.J. Hoogeboom, P systems with symport/antiport simulating counter automata, Acta Inform. 41 (2) (2004) 145–170. [13] M.A. Gutiérrez-Naranjo, M.J. Pérez-Jiménez, A. Riscos-Núñez, F.J. Romero-Campero, Computational efficiency of dissolution rules in membrane systems, Int. J. Comput. Math. 83 (7) (2006) 593–611. [14] M. Ionescu, Gh. P˘ aun, T. Yokomori, Spiking neural P systems, Fundam. Inform. 71 (2–3) (2006) 279–308. [15] S.N. Krishna, R. Rama, A variant of P systems with active membranes: solving NP–complete problems, Rom. J. Inf. Sci. Technol. 2 (1999) 357–367. [16] A. Leporati, L. Manzoni, G. Mauri, A.E. Porreca, C. Zandron, Constant-space P systems with active membranes, Fundam. Inform. 134 (1–2) (2014) 111–128. [17] A. Leporati, L. Manzoni, G. Mauri, A.E. Porreca, C. Zandron, A survey on space complexity of P systems with active membranes, Int. J. Adv. Eng. Sci. Appl. Math. 10 (3) (2018) 221–229. [18] A. Leporati, L. Manzoni, G. Mauri, A.E. Porreca, C. Zandron, Subroutines in P systems and closure properties of their complexity classes, Theor. Comput. Sci. (2019), https://doi .org /10 .1016 /j .tcs .2018 .06 .012, in press. [19] A. Leporati, L. Manzoni, G. Mauri, A.E. Porreca, C. Zandron, Characterizing PSPACE with shallow non-confluent P systems, J. Membr. Comput. 1(2) (2019) 75–84. [20] L.F. Macías-Ramos, B. Song, L. Valencia-Cabrera, L. Pan, M.J. Pérez-Jiménez, Membrane fission: a computational complexity perspective, Complexity 21 (6) (2016) 321–334. [21] L.F. Macías-Ramos, L. Valencia-Cabrera, B. Song, L. Pan, M.J. Pérez-Jiménez, A P-Lingua based simulator for P systems with symport/antiport rules, Fundam. Inform. 139 (2) (2015) 211–277. [22] A. Maroosi, R.C. Muniyandi, Accelerated execution of P systems with active membranes to solve the N-queens problem, Theor. Comput. Sci. 551 (2014) 39–54. [23] C. Martín-Vide, J. Pazos, Gh. P˘ aun, A. Rodríguez-Patón, Theor. Comput. Sci. 296 (2) (2003) 295–326. [24] M.A. Martínez-del-Amor, M. García-Quismondo, L.F. Macías-Ramos, L. Valencia-Cabrera, A. Riscos-Núñez, M.J. Pérez-Jiménez, Simulating P systems on GPU devices: a survey, Fundam. Inform. 136 (3) (2015) 269–284. [25] M.L. Minsky, Computation: Finite and Infinite Machines, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1967. [26] M. Mutyam, K. Krithivasan, P systems with membrane creation: universality and efficiency, Lect. Notes Comput. Sci. 2055 (2001) 276–287. [27] D. Orellana-Martín, M.A. Martínez-del-Amor, I. Pérez-Hurtado, A. Riscos-Núñez, L. Valencia-Cabrera, M.J. Pérez-Jiménez, When object production tunes the efficiency of membrane systems, Theor. Comput. Sci. (2018), https://doi .org /10 .1016 /j .tcs .2018 .04 .013, in press. [28] D. Orellana-Martín, L. Valencia-Cabrera, A. Riscos-Núñez, M.J. Pérez-Jiménez, Minimal cooperation as a way to achieve the efficiency in cell-like membrane systems, J. Membr. Comput. 1(2) (2019) 85–92. [29] L. Pan, T.-O. Ishdorj, P systems with active membranes and separation rules, J. Univers. Comput. Sci. 10 (5) (2004) 630–649. [30] L. Pan, Gh. P˘ aun, B. Song, Flat maximal parallelism in P systems with promoters, Theor. Comput. Sci. 623 (2016) 83–91. [31] L. Pan, M.J. Pérez-Jiménez, Computational complexity of tissue-like P systems, J. Complex. 26 (3) (2010) 296–315. [32] L. Pan, B. Song, L. Valencia-Cabrera, M.J. Pérez-Jiménez, The computational complexity of tissue P systems with evolutional symport/antiport rules, Complexity (2018) 3745210, 21 pages. [33] C.H. Papadimitriou, Computational Complexity, Addison–Wesley, Reading, Mass, 1994. [34] A. P˘ aun, On P systems with active membranes, in: Proceedings of the Second International Conference on Unconventional Models of Computation, (UMC’2K), 2000, pp. 187–201. [35] A. P˘ aun, Gh. P˘ aun, The power of communication: P systems with symport/antiport, New Gener. Comput. 20 (3) (2002) 295–305. [36] Gh. P˘ aun, Computing with membranes, J. Comput. Syst. Sci. 61 (1) (2000) 108–143. [37] Gh. P˘ aun, P systems with active membranes: attacking NP-complete problems, J. Autom. Lang. Comb. 6(1) (2001) 75–90. [38] Gh. P˘ aun, Computing with Membranes: An Introduction, Springer-Verlag, Berlin, 2002. [39] Gh. P˘ aun, G. Rozenberg, A. Salomaa (Eds.), The Oxford Handbook of Membrane Computing, Oxford University Press, New York, 2010. [40] H. Peng, J. Wang, M.J. Pérez-Jiménez, A. Riscos-Núñez, An unsupervised learning algorithm for membrane computing, Inf. Sci. 304 (2015) 80–91. [41] H. Peng, J. Wang, M.J. Pérez-Jiménez, H. Wang, J. Shao, T. Wang, Fuzzy reasoning spiking neural P system for fault diagnosis, Inf. Sci. 235 (2013) 106–116. 18 [42] M.J. Pérez-Jiménez, An approach to computational complexity in membrane computing, Lect. Notes Comput. Sci. 3365 (2005) 89–109. [43] M.J. Pérez-Jiménez, A. Riscos-Núñez, Solving the Subset-Sum problem by active membranes, New Gener. Comput. 23 (2005) 367–384. [44] M.J. Pérez-Jiménez, P. Sosík, An optimal frontier of the efficiency of tissue P systems with cell separation, Fundam. Inform. 138 (1–2) (2015) 45–60. [45] G. Rozenberg, A. Salomaa (Eds.), Handbook of Formal Languages, 3 vols, Springer, Berlin, 1997. [46] T. Song, L. Pan, Spiking neural P systems with rules on synapses working in maximum spikes consumption strategy, IEEE Trans. Nanobiosci. 14 (2015) 38–44. [47] T. Song, L. Pan, Spiking neural P systems with rules on synapses working in maximum spiking strategy, IEEE Trans. Nanobiosci. 14 (4) (2015) 465–477. [48] T. Song, L. Pan, Spiking neural P systems with request rules, Neurocomputing 193 (2016) 193–200. [49] B. Song, Y. Kong, Solution to PSPACE-complete problem using P systems with active membranes with time-freeness, Math. Probl. Eng. (2019) 5793234. [50] B. Song, M.J. Pérez-Jiménez, L. Pan, Efficient solutions to hard computational problems by P systems with symport/antiport rules and membrane division, Biosystems 130 (2015) 51–58. [51] B. Song, M.J. Pérez-Jiménez, Gh. P˘ aun, L. Pan, Tissue P systems with channel states working in the flat maximally parallel way, IEEE Trans. Nanobiosci. 15 (7) (2016) 645–656. [52] B. Song, T. Song, L. Pan, A time-free uniform solution to subset sum problem by tissue P systems with cell division, Math. Struct. Comput. Sci. 27 (1) (2017) 17–32. [53] B. Song, C. Zhang, L. Pan, Tissue-like P systems with evolutional symport/antiport rules, Inf. Sci. 378 (2017) 177–193. [54] P. Sosík, The computational power of cell division in P systems: beating down parallel computers?, Nat. Comput. 2(3) (2003) 287–298. [55] P. Sosík, L. Cienciala, Computational power of cell separation in tissue P systems, Inf. Sci. 279 (2014) 805–815. [56] P. Sosík, L. Cienciala, A limitation of cell division in tissue P systems by PSPACE, J. Comput. Syst. Sci. 81 (2015) 473–484. [57] P. Sosík, A. P˘ aun, A. Rodríguez-Patón, P systems with proteins on membranes characterize PSPACE, Theor. Comput. Sci. 488 (2013) 78–95. [58] P. Sosík, A. Rodríguez-Patón, Membrane computing and complexity theory: a characterization of PSPACE, J. Comput. Syst. Sci. 73 (2007) 137–152. [59] L. Valencia-Cabrera, D. Orellana-Martín, M.A. Martínez-del-Amor, A. Riscos-Núñez, M.J. Pérez–Jiménez, Cooperation in transport of chemical substances: a complexity approach within membrane computing, Fundam. Inform. 154 (2017) 373–385. [60] L. Valencia-Cabrera, D. Orellana-Martín, M.A. Martínez-del-Amor, A. Riscos-Núñez, M.J. Pérez–Jiménez, Reaching efficiency through collaboration in membrane systems: Dissolution, polarization and cooperation, Theor. Comput. Sci. 701 (2017) 226–234. [61] S. Verlan, J. Quirós, Fast hardware implementations of P systems, Lect. Notes Comput. Sci. 7762 (2013) 404–423. [62] T. Wu, Z. Zhang, Gh. P˘ aun, L. Pan, Cell-like spiking neural P systems, Theor. Comput. Sci. 623 (2016) 180–189. [63] C. Zandron, A. Leporati, C. Ferretti, G. Mauri, M.J. Pérez–Jiménez, On the computational efficiency of polarizationless recognizer P systems with strong division and dissolution, Fundam. Inform. 87 (1) (2008) 79–91. [64] G. Zhang, M. Gheorghe, L. Pan, M.J. Pérez-Jiménez, Evolutionary membrane computing: a comprehensive survey and new results, Inf. Sci. 279 (2014) 528–551.