Reaching efficiency through collaboration in membrane systems: Dissolution, polarization and cooperation

Reaching efficiency through collaboration in membrane systems: Dissolution, polarization and cooperation Luis Valencia-Cabrera, David Orellana-Martín, Miguel A. Martínez-del-Amor, Agustín Riscos-Núñez, Mario J. Pérez-Jiménez Research Group of Natural Computing, Department of Computer Science and Artificial Intelligence, Universidad de Sevilla, Sevilla, 41012, Spain a b s t r a c t Keywords: Membrane computing Active membranes Cooperative rules Minimal cooperation Computational complexity The P versus NP problem From a computational complexity point of view, some syntactical ingredients play different roles depending on the kind of combination considered. Inspired by the fact that the passing of a chemical substance through a biological membrane is often done by an interaction with the membrane itself, systems with active membranes were considered. Several combinations of different ingredients have been used in order to know which kind of problems could they solve efficiently In this paper, minimal cooperation with a minimal expression (the left-hand side of every object evolution rule has at most two objects and its right-hand side contains only one object) in object evolution rules is considered and a polynomial-time uniform solution to the SAT problem is presented. Consequently, a new way to tackle the Pversus NP problem is provided. 1. Introduction The first models in Membrane Computing were designed in such a manner that the number of membranes could not increase during a computation. They could only decrease by dissolving membranes as a result of applying some rules to the objects present in the system. However, in these systems an exponential workspace (expressed in terms of the number of objects) can be constructed in linear time, e.g. via evolution rules of the type a →(a2, here). Nevertheless, such a capability is not enough to efficiently solve NP-complete problems, unless P=NP (see [6] for details). It is well known that in ideal circumstances, a cell produces two identical copies by the processes of interphase and mitosis. First, the cell grows and makes a copy of its DNA (replication) and, finally, the cell separates its DNA into two sets and divides its cytoplasm, forming two new cells. Inspired from this mechanism, a new kind of rules was introduced in Membrane Computing allowing the proliferation of membranes by means of division rules. A membrane without any other membrane inside it (elementary membrane) can be divided by means of an interaction with an object from that membrane. In [12], cell-like P systems with active membranes are defined incorporating this ingredient. In such systems, each membrane has an electrical charge (positive, negative or neutral) associated with it, but the rules are non-cooperative and there are no priorities among rules. Besides, a non-elementary membrane (that is, a membrane with one or more membranes within it) with at least two inner membranes can also be divided. The skin cannot be divided. In the classical version of these systems, each membrane is identified by a label and has an electrical polarization (positive, negative or neutral) associated with it. They can be dissolved or their objects can be replicated (respectively distributed) by a mechanism abstracting the cell division (membrane fission) process. In each membrane, objects can evolve according to given evolution rules, or can be sent outside the current membrane or to an inner membrane. This framework is too powerful with respect to efficiency, so that PSPACE-complete problems can be solved in polynomial time with respect to the input size by avoiding cooperative rules, dissolution and division for non-elementary membranes. The class of all problems solvable in polynomial time with respect to the input size and in a uniform way1by means of families of P systems with active membranes using division for elementary and non-elementary membranes contains class PSPACE and it is contained in class EXP [15]. Thus, in order to provide efficient solutions to computationally hard problems, this framework seems to be too powerful from the computational complexity point of view. If polarizations are removed, then dissolution rules become essential, in the sense that, without their presence, only problems in class Pcan be efficiently solved by families of these kind of systems. P systems with active membranes and without electrical charges were initially studied in [1,2]. Polarizations were replaced by the possibility to change the label of the membranes by means of some rules. However, in order to obtain polynomial-time solutions to computationally hard problems, two polarizations suffice (see [3] for details). In [14] bi-stable catalysts are used to compensate the loss of computational efficiency represented by avoiding polarizations. Recognizer polarizationless P systems with active membranes were introduced in [7] as systems such that: (a) the working alphabet has two distinguished objects yes and no; (b) there is an input alphabet strictly contained in the working alphabet; (c) the initial multisets do not contain any object from the input alphabet; (d) there is a distinguished membrane (the input membrane); (e) the output region is the environment; (f) all computations halt; and (g) either object yes or object no (but not both) must have been released into the environment for any computation, and only at the last step. In [7] the first polynomial-time semi-uniform solution to SUBSET-SUM problem was given in the framework of polarizationless P systems with active membranes using division rules for elementary and non-elementary membranes and without dissolution. In [4] a polynomial-time uniform solution to the satisfiability of a quantified Boolean formula (QSAT) problem (a well known PSPACE-complete problem) was given in that framework by using division for elementary and nonelementary membranes. In [7] was highlighted the surprising role of (up to then) an apparently “innocent” type of rules: dissolution. Thus, in the framework of polarizationless P systems with active membranes using division for elementary and non-elementary membranes, passing from allowing dissolution rules to forbidding them amounts to passing from efficiency to non-efficiency. Let us recall that in P systems with active membranes, division rules provide a mechanism to produce an exponential number of membranes in linear time. This mechanism can be replaced by other one, inspired by the membrane fission process, by which a biological membrane splits into two new ones in such a manner that the contents of the initial membrane is distributed between the new membranes. Membrane separation rules have been introduced in the framework of P systems with active membranes instead of division rules, and their efficiency have been shown [8–10]. Rules involving the evolution of several objects at the same time are called cooperative rules. It is the case of cooperation by means of objects. An object aneeds additional objects in order to evolve, and the application of the rules “consumes” the additional objects used. An interesting particular case of cooperative rules is the ones involving certain special objects (called catalysts), specified in advance. In these rules, regular objects only evolve in evolution rules in conjunction with these catalyst objects, which remain unmodified [11]. It is worth noting that polarization in P systems with active membranes also provides a certain kind of “cooperation”. In these systems, a rule associated with the label of a membrane can be triggered at a moment of time twhen a certain object is present in the membrane. However, additionally, it needs to “cooperate” with a specific polarization associated with the membrane at instant t. In this case, the polarization is not “consumed” by the application of the rule, in the sense that many different objects of the current contents can evolve at instant t“by using” the same polarization. The paper is organized as follows. In Section 2, polarizationless P systems with active membranes by using minimal cooperation in object evolution rules are considered. The computational efficiency of such P systems using minimal cooperation with minimal production (only a single object is produced by the application of any rule) is established in Section 3 by providing a uniform polynomial-time solution to the SAT problem. A formal verification of this result is presented in Section 4. Next, the main results of the paper are presented in Section 5. Finally, the paper ends with some conclusions and open problems. 2. Polarizationless P systems with active membranes and minimal cooperation in object evolution rules We assume the reader is familiar with basic notions and terminology of membrane computing [13]. However, before going on let us briefly overview some notations that will be used throughout the paper. An alphabet is a non-empty set whose elements are called symbols. A multiset over an alphabet is an ordered pair (, f), where fis a mapping from  onto the set of natural numbers N. The support of a multiset m =(, f)is defined as supp(m) ={x ∈| f(x) >0}, and its 1For more details about the uniformity of a solution, see [4]. size is |m| =x∈supp(m)f(x). We denote by M() the set of all multisets over . If m1=(, 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 ∈. Next, minimal cooperation in object evolution rules is introduced in the framework of polarizationless P systems with active membranes. The term “minimal cooperation” is used in the following sense: the left-hand side of such rules consists of two symbols. Definition 2.1. In the context of polarizationless P system with active membranes, several types of minimal cooperation in object evolution rules are defined as follows. –Minimal cooperation (mc): object evolution rules are of the form [ u →v ]h, where u, v ∈M() such that |u| ≤2, but at least one object evolution rule verifies |u| =2. –Primary minimal cooperation (pmc): object evolution rules are of the form [ u →v ]h, where u, v ∈M() and 1 ≤ |u|, |v| ≤2, but at least one object evolution rule verifies |u| =2. –Bounded minimal cooperation (bmc): object evolution rules are of the form [ u →v ]h, where u, v ∈M() and 1 ≤|v| ≤ |u| ≤2, but at least one object evolution rule verifies |u| =2. –Minimal cooperation and minimal production (mcmp): object evolution rules are of the forms [ a →b ]hor [ a b →c]h, where a, b, c∈, but at least one object evolution rule is of the second type. In these systems, send-in communication rules, send-out communication rules, dissolution rules and division rules are non-cooperative rules. In polarizationless P systems with active membranes and minimal cooperation in object evolution rules, the rules are applied according to the same principles than in the “classical” P systems with active membranes (see [12], for details). We denote by DAM0(α, β, γ, δ) the class of all recognizer polarizationless P systems with active membranes and division rules, where α, β, γand δare parameters associated with object evolution rules, communication rules, dissolution rules and division rules, respectively. The meaning of the parameters α, β, γ, δis the following: •If α=−e(resp. α=+e), object evolution rules are forbidden (resp. permitted). •If α=mc (resp. α=pmc, α=bmc or α=mcmp), then minimal cooperation (primary minimal cooperation, bounded minimal cooperation or minimal cooperation and minimal production, respectively) in object evolution rules are permitted. •If β=−c(resp. β=+c) then communication rules are forbidden (resp. permitted). •If γ=−d(resp. γ=+d) then dissolution rules are forbidden (resp. permitted). •If δ=−n(resp. δ=+n) then division rules for only elementary membranes are permitted (resp. division rules for elementary and non-elementary membranes are permitted). If separation rules are considered instead of division rules, the corresponding classes of recognizer membrane systems are denoted by SAM0(α, β, γ, δ). Let us recall some interesting results expressed in these notations. 1. Families of systems from DAM0(+e,+c,+d,+n)can solve PSPACE-complete problems in polynomial time and in a uniform way, that is, PSPACE ⊆PMCDAM0(+e,+c,+d,+n)(see [4] for details). Moreover, in [17] and [16] the reverse inclusion was proved, so a stronger result is obtained in this framework: PSPACE =PMCDAM0(+e,+c,+d,+n). 2. Families of systems from DAM0(+e,+c,−d,+n)can efficiently solve only problems in class P, that is, PMCDAM0(+e,+c,−d,+n)=P(see [7] for details). 3. Families of systems from SAM0(+e,+c,−d,+n)can efficiently solve only problems in class P, that is, PMCSAM0(+e,+c,−d,+n)=P(see [19] for details). 4. Families of systems from DAM0(bmc,+c,−d,−n)can solve NP-complete problems in polynomial time and in a uniform way, that is, NP ∪co-NP ⊆PMCDAM0(bmc,+c,−d,−n)(see [18] for details). 5. Families of systems from SAM0(bmc,+c,−d,−n)can efficiently solve only problems in class P, that is, PMCSAM0(bmc,+c,+d,+n)=P(see [20] for details). 6. Families of systems from SAM0(pmc,+c,−d,−n)can solve NP-complete problems in polynomial time and in a uniform way, that is, NP ∪co-NP ⊆PMCSAM0(pmc,+c,−d,−n)(see [18] for details). P˘ aun’s conjecture can be expressed as follows: PMCDAM0(+e,+c,+d,−n)=P. It is a relevant open question. From results 4 and 5, a new frontier of efficiency is deduced. In the framework of polarizationless P systems with active membranes not using dissolution rules, a new frontier of the efficiency is obtained. Specifically, when bounded minimal cooperation in object evolution rules is allowed in the previous computing framework, passing from separation rules to division rules amounts to passing from non-efficiency to efficiency. Next, we try to find narrower frontiers of efficiency by showing that bounded minimal cooperation can be replaced by minimal cooperation and minimal production in object evolution rules. Let us recall that the application of this kind of rules implies that only a single object can be produced by the application of a rule. 3. On the efficiency of systems from DAM0(mcmp,+c,−d,−n) In this section, we analyze what happens, from a computational complexity point of view, when minimal cooperation and minimal production in object evolution rules are considered instead of dissolution rules. The first work in this direction was addressed in [18]. The efficiency of such systems was proven when only object evolution rules such that the of length their left-hand sides are greater than or equal to the length of the corresponding right-hand side, and both lengths are at most two. Specifically, we show that the syntactical ingredient of minimal cooperation and minimal production in polarizationless P systems with active membranes (without dissolution and allowing only division for elementary membranes) is enough to solve computationally hard problems in an efficient way. 3.1. A uniform polynomial-time solution to the SAT problem Next, a polynomial-time uniform solution to the SAT problem, a well known NP-complete problem [5] is provided by a family ={(t) |t∈N}of recognizer P systems from DAM0(mcmp,+c,−d,−n). Let us recall that the polynomial-time computable function (the Cantor pair function) n, p =((n +p)(n +p +1)/2) +n is a primitive recursive and bijective function from N ×Nto N. The family ={(t) |t∈N}is defined in such a manner that system (t)will process any Boolean formula ϕin conjunctive normal form (CNF) with nvariables and pclauses, where t=n, p, provided that the appropriate input multiset cod(ϕ)is supplied to the system (through the corresponding input membrane), and will answer if there exists at least one truth assignment that makes true the input formula ϕ, that is, (t)will solve an instance of the SAT problem. For each n, p ∈N, we consider the recognizer P system (n, p) =(, , H, μ, M1, M2, R, iin, iout)from DAM0(mcmp, +c, −d, −n), defined as follows: (1) Working alphabet : {yes ,no ,α,β ,β  ,γ,γ,γ ,#}∪{ai,k|1≤i≤n,1≤k≤i}∪ {ti,k,fi,k|1≤i≤n,i≤k≤n+p−1}∪ {βk|0≤k≤n+2p+1}∪{cj|1≤j≤p}∪{dj|2≤j≤p}∪ {Ti,k,Fi,k|1≤i≤n,0≤k≤n−1}∪{Ti,Fi|1≤i≤n}∪ {xi,j,k,xi,j,k,x∗ i,j,k|0≤i≤n,1≤j≤p,1≤k≤n+p} (2) Input alphabet : {xi,j,0, xi,j,0, x∗ i,j,0|1 ≤i ≤n, 1 ≤j ≤p}. (3) H={1, 2}. (4) Membrane structure: μ =[ [ ]2]1, that is, μ =(V, E)where V={1, 2}and E={(1, 2)}. (5) Initial multisets: M1={ α, β0}, M2={ ai,1, Tp i,0, Fp i,0|1 ≤i ≤n }. (6) The set of rules Rconsists of the following rules: 1.1 Rules for a general counter. [ βk−→ βk+1]1, for 0 ≤k ≤n +2p [ βn+2p+1−→ β]1 1.2 Rules for an affirmative answer. [ αγ −→ γ]1 [ γ−→ γ ]1 [ γ ]1−→ yes [ ]1 1.3 Rules for a negative answer. [ αβ−→ β ]1 [ β ]1−→ no [ ]1 2.1 Rules to generate all truth assignments. [ ai,i]2−→ [ ti,i]2[ fi,i]2, for 1 ≤i ≤n [ai,k−→ ai,k+1]2, for 2 ≤i ≤n ∧1 ≤k ≤i −1 2.2 Rules to produce exactly pcopies of each truth assignment. [ti,k−→ ti,k+1]2 [fi,k−→ fi,k+1]21 ≤i ≤n −1 ∧i ≤k ≤n −1 [Ti,k−→ Ti,k+1]2 [Fi,k−→ Fi,k+1]21 ≤i ≤n, 0 ≤k ≤n −2 [Ti,n−1−→ Ti]2 [Fi,n−1−→ Fi]21 ≤i ≤n [ti,kFi−→ ti,k+1]2 [fi,kTi−→ fi,k+1]21 ≤i ≤n ∧n ≤k ≤n +p −2 [ti,n+p−1Fi−→ #]2 [fi,n+p−1Ti−→ #]21 ≤i ≤n 2.3 Rules to prepare the input formula for check clauses: [xi,j,k−→ xi,j,k+1]2 [xi,j,k−→ xi,j,k+1]2 [x∗ i,j,k−→ x∗ i,j,k+1]2 ⎫ ⎬ ⎭ 1 ≤i ≤n, 1 ≤j ≤p, 0 ≤k ≤n +p −1 2.4 Rules for the first checking stage. [Tixi,j,n+p−→ cj]2 [Tixi,j,n+p−→ #]2 [Tix∗ i,j,n+p−→ #]2 [Fixi,j,n+p−→ #]2 [Fixi,j,n+p−→ cj]2 [Fix∗ i,j,n+p−→ #]2 ⎫ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎬ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎭ 1 ≤i ≤n ∧1 ≤j ≤p 2.5 Rules for the second checking stage. [c1c2−→ d2]2 [djcj+1−→ dj+1]2, for 2 ≤j ≤p −1 2.6 Rule to prepare an affirmative answer. [ dp]2−→ γ[ ]2 (7) The input membrane is the membrane labelled by 2 (iin =2) and the output region is the environment (iout =env). 4. A formal verification of the solution We consider the polynomial encoding (cod, s)from SAT in defined as follows: let ϕbe a Boolean formula in conjunctive normal form (a conjunction of clauses such that each clause is the disjunction of one or more literals) and simplified (in each clause, literals are not repeated, and also none of the clauses contains both a literal and its negation). Let Var(ϕ) ={x1, ··· , xn}be the set of propositional variables and {C1, ··· , Cp}the set of clauses of ϕ. Let us assume that the number of variables and the number of clauses of the input formula ϕ, are greater than or equal to 2. Then, we define s(ϕ) =n, pand cod(ϕ)={xi,j,0|xi∈Cj}∪{xi,j,0|¬xi∈Cj}∪{x∗ i,j,0|xi/∈Cj,¬xi/∈Cj} Notice that we can represent this multiset as a matrix, in such a way that the j-th row (1 ≤j ≤p) encodes the j-th clause Cjof ϕ. For instance, the formula ϕ=(x1+x2+¬x3)(¬x2+x4)(¬x2+x3+¬x4)is encoded as follows: cod(ϕ)=⎛ ⎜ ⎝ x1,1,0x2,1,0x3,1,0x∗ 4,1,0 x∗ 1,2,0x2,2,0x∗ 3,2,0x4,2,0 x∗ 1,3,0x2,3,0x3,3,0x4,3,0 ⎞ ⎟ ⎠ We denote by codk(ϕ)the multiset cod(ϕ)when the third index of all objects is equal to k. For instance: cod3(ϕ)=⎛ ⎜ ⎝ x1,1,3x2,1,3x3,1,3x∗4,1,3 x∗1,2,3x2,2,3x∗3,2,3x4,2,3 x∗1,3,3x2,3,3x3,3,3x4,3,3 ⎞ ⎟ ⎠ The Boolean formula ϕwill be processed by the system (s(ϕ)) with input multiset cod(ϕ). Next, we informally describe how that system works. The solution proposed follows a brute force algorithm in the framework of recognizer P systems with active membranes, minimal cooperation and minimal production in object evolution rules. It consists of the following stages: •Generation stage: using division rules, all truth assignments for the variables {x1, ..., xn}associated with ϕare produced. Specifically, 2nmembranes labelled by 2 are generated, each of them encoding a truth assignment. This stage takes exactly ncomputation steps, nbeing the number of variables in ϕ. •Production of enough copies for each truth assignment: in this stage pcopies of each truth assignment are produced to allow the checking of the literal associated with each variable in each clause. This stage takes exactly pcomputation steps. •First Checking stage: checking whether or not each clause of the input formula ϕis satisfied by the truth assignments generated in the previous stage, encoded by each membrane labelled by 2. This stage takes exactly one computation step. •Second Checking stage: checking whether or not all clauses of the input formula ϕare satisfied by some truth assignment encoded by a membrane labelled by 2. This stage takes exactly p −1steps, pbeing the number of clauses of ϕ. •Output stage: the system sends to the environment the right answer according to the results of the previous stage. This stage takes exactly 4 steps. 4.1. Generation stage At this stage, all the truth assignments for the variables associated with the Boolean formula ϕare generated, by applying division rules from 2.1 in membranes labelled by 2. In such manner at the i-th step, 1 ≤i ≤n, of this stage, division rule is triggered by object ai,i, producing two new membranes with all its remaining contents replicated in the new membranes labelled by 2. This stage ends when objects ti,n, fi,n, 1 ≤i ≤n, have been generated. Proposition 1. Let C=(C0, C1, ..., Cq)be a computation of the system (s(ϕ)) with input multiset cod(ϕ). (a) For each k, 1 ≤k ≤n −1, at configuration Ckwe have Ck(1) ={α, βk}(being Ct(i)the contents of membrane iat the moment t) and there are 2kmembranes labelled by 2 such that each of them contains: the set {ai,k+1|k +1 ≤i ≤n}and the set codk(ϕ); the multiset {Tp i,k, Fp i,k|1 ≤i ≤n}; and a different subset {r1,k, ..., rk,k}, being r∈{t, f}. (b) At configuration Cnwe have Cn(1) ={α, βn}and there are 2nmembranes labelled by 2 such that each of them contains: the set codn(ϕ); the multiset {Tp i, Fp i|1 ≤i ≤n}; and a different subset {r1,n, ..., rn,n}, being r∈{t, f}. Proof. (a) By induction on k. The base case k =1 follows bearing in mind that configuration C1is obtained from configuration C0 by applying the rules [β0→β1]1, [a1,1]2→[t1,1]2[f1,1]2, [Ti,0→Ti,1]2, [Fi,0→Fi,1]2, for 1 ≤i ≤n, [xi,j,0→xi,j,1]2, [xi,j,0→xi,j,1]2, [x∗ i,j,0→x∗ i,j,1]2, for 1 ≤i ≤n, 1 ≤j ≤p. Let us assume that the result holds for k, 1 ≤k <n −1. Let us see that the result also holds for k +1. On the one hand, at configuration Ckwe have Ck(1) ={α, βk}and there are 2kmembranes labelled by 2 each of them containing the set {ai,k+1|k +1 ≤i ≤n}and the set codk(ϕ); the multiset {Tp i,k, Fp i,k|1 ≤i ≤n}; and a different subset {r1,k, ..., rk,k}, being r∈{t, f}. On the other hand, configuration Ck+1is obtained from configuration Ckby applying the rules: [βk→βk+1]1, [ak+1,k+1]2→[tk+1,k+1]2[fk+1,k+1]2, [ti,k→ti,k+1]2, [fi,k→fi,k+1]2, for 1 ≤i ≤k, [ai,k+1→ai,k+2]2, for k +2 ≤i ≤n, [Ti,k→Ti,k+1]2, [Fi,k→Fi,k+1]2, for 1 ≤i ≤n, [xi,j,k→xi,j,k+1]2, [xi,j,k→xi,j,k+1]2, [x∗ i,j,k→x∗ i,j,k+1]2, for 1 ≤i ≤ n, 1 ≤j ≤p. Hence, the result holds for k +1. (b) By applying (a) to k =n −1at configuration Cn−1we have Cn−1(1) ={α, βn−1}and there are 2n−1membranes labelled by 2 each of them containing: the object an,nand the set codn−1(ϕ); the multiset {Tp i,k, Fp i,k|1 ≤i ≤n}; and a different subset {r1,n−1, ..., rn−1,n−1}, being r∈{t, f}. Then, (b) follows noting that configuration Cnis obtained from configuration Cn−1by applying the rules: [βn−1→ βn]1, [an,n]2→[tn,n]2[fn,n]2, [ti,n−1→ti,n]2, [fi,n−1→fi,n]2, for 1 ≤i ≤n −1, [xi,j,n−1→xi,j,n]2, [xi,j,n−1→xi,j,n]2, [x∗ i,j,n−1→x∗ i,j,n]2, for 1 ≤i ≤n, 1 ≤j ≤p.2 4.2. Producing enough copies for each truth assignment At this stage, in each membrane labelled by 2, a sufficient number of copies from each truth assignment will be generated. Specifically, pcopies of each of them will be produced, where pis the number of clauses of the input formula. Let us recall that in the initial configuration there are pcopies of T1, F1, ...Tn, Fn. These copies are replicated in the 2n membranes labelled by 2 produced by applying division rules where a copy of each truth assignment is produced. By using cooperation we use the values tiand fiof the truth assignment associated with each membrane labelled by 2 to remove a copy of the opposite value Fior Ti, respectively. This stage takes exactly psteps. Proposition 2. Let C=(C0, C1, ..., Cq)be a computation of the system (s(ϕ)) with input multiset cod(ϕ). (a) For each k, 1 ≤k ≤p −1, at configuration Cn+kwe have Cn+k(1) ={α, βn+k}and there are 2nmembranes labelled by 2 such that each of them contains: the set codn+k(ϕ); a different subset {r1,n+k, ..., rn,n+k}, being r∈{t, f}; and the corresponding multiset {Rp 1, Rp−k 1, ..., Rp n, Rp−k n}verifying the following: for each k, 1 ≤i ≤n, if ri,n+k=ti,n+kthen Ri=Tiand Ri=Fi; if ri,n+k=fi,n+kthen Ri=Fiand Ri=Ti; (b) At configuration Cn+pwe have Cn+p(1) ={α, βn+p}and there are 2nmembranes labelled by 2 such that each of them contains: n copies of object #; the set codn+p(ϕ); and a different subset {Rp 1, ..., Rp n}being R ∈{T, F}. Proof. (a) By induction on k. The base case k =1 follows bearing in mind that configuration Cn+1is obtained from configuration Cnby applying the rules: [βn→βn+1]1, [ti,nFi→ti,n+1]2, [fi,nTi→fi,n+1]2, for 1 ≤i ≤n, [xi,j,n→xi,j,n+1]2, [xi,j,n→ xi,j,n+1]2, [x∗ i,j,n→x∗ i,j,n+1]2, for 1 ≤i ≤n, 1 ≤j ≤p. Let us assume that the result holds for k, 1 ≤k <p −1. Let us see that the result also holds for k +1. On the one hand, at configuration Cn+kwe have Cn+k(1) ={α, βn+k}and there are 2nmembranes labelled by 2 each of them containing the set codn+k(ϕ); a different subset {r1,n+k, ..., rn,n+k}, being r∈{t, f}; and the corresponding multiset {Rp 1, Rp−k 1, ..., Rp n, Rp−k n}verifying the following: for each k, 1 ≤i ≤n, if ri,n+k=ti,n+kthen Ri=Tiand Ri=Fi; if ri,n+k=fi,n+kthen Ri=Fiand Ri=Ti; On the other hand, configuration Cn+k+1is obtained from configuration Cn+kby applying the rules: [βn+k→βn+k+1]1, [ti,n+kFi→ti,n+k+1]2, [fi,n+kTi→fi,n+k+1]2, for 1 ≤i ≤n, [xi,j,n+k→xi,j,n+k+1]2, [xi,j,n+k→xi,j,n+k+1]2, [x∗ i,j,n+k→ x∗ i,j,n+k+1]2, for 1 ≤i ≤n, 1 ≤j ≤p. Hence, the result holds for k +1. (b) By applying (a) to k =p −1, at configuration Cn+p−1we have Cn+p−1(1) ={α, βn+p−1}and there are 2nmembranes labelled by 2 each of them containing the set codn+p−1(ϕ); a different subset {r1,n+p−1, ..., rn,n+p−1}, being r∈{t, f}; and the corresponding multiset {Rp 1, R1 1, ..., Rp n, R1 n}verifying the following: for each i, 1 ≤i ≤n, if ri,n+p−1=ti,n+p−1 then Ri=Ti, Ri=Fiand if ri,n+p−1=fi,n+p−1then Ri=Fi, Ri=Ti. Then, (b) follows noting that configuration Cn+pis obtained from configuration Cn+p−1by applying the rules: [βn+p−1→βn+p]1, [ti,n+p−1Fi→#]2, [fi,n+p−1Ti→#]2, for 1 ≤i ≤n, [xi,j,n+p−1→xi,j,n+p]2, [xi,j,n+p−1→xi,j,n+p]2, [x∗ i,j,n+p−1→x∗ i,j,n+p]2, for 1 ≤i ≤n, 1 ≤j ≤p.2 4.3. First checking stage At this stage, we try to determine the clauses satisfied by the truth assignments encoded by each membrane labelled by 2. For that, rules from 2.4 will be applied in such a manner that an object cjis produced if and only if the truth assignment encoded by that membrane makes true clause Cj. This stage takes exactly one step. Proposition 3. Let C=(C0, C1, ..., Cq)be a computation of the system (s(ϕ)) with input multiset cod(ϕ). At configuration Cn+p+1 we have Cn+p+1(1) ={α, βn+p+1}and there are 2nmembranes labelled by 2such that each of them contains tjcopies of object c j, for 1 ≤j ≤p, if and only if the truth assignment encoded by that membrane makes true exactly tjliterals of clause Cj, and np −(t1+ ···+tp)copies of object #. Proof. It suffices to note that configuration Cn+p+1is obtained from configuration Cn+pby applying the rules: [βn+p→ βn+p+1]1, [Tixi,j,n+p→cj]2, [Tixi,j,n+p→#]2, [Tix∗ i,j,n+p→#]2, [Fixi,j,n+p→#]2, [Fixi,j,n+p→cj]2, [Fix∗ i,j,n+p→#]2, for 1 ≤i ≤n, 1 ≤j ≤p.2 4.4. Second checking stage At this stage, we try to determine whether some truth assignment encoded by a membrane labelled by 2 satisfies all clauses of the input formula. To that end, rules from 2.5 will be applied in such a manner that object dj(2 ≤j ≤p) is produced in a membrane labelled by 2 if and only if the truth assignment encoded by that membrane makes true the clauses C1, ..., Cj. Then, the input formula will be satisfied by the truth assignment encoded by a membrane labelled by 2 if and only if object dpappears in that membrane. This stage takes exactly p −1 computation steps. Proposition 4. Let C=(C0, C1, ..., Cq)be a computation of the system (s(ϕ)) with input multiset cod(ϕ). (a) For each k, 1 ≤k ≤p −1, at configuration C(n+p+1)+kwe have C(n+p+1)+k(1) ={α, β(n+p+1)+k}and there are 2nmembranes labelled by 2such that each of them contains an object dk+1if and only if the truth assignment encoded in that membrane, makes true clauses C1, ..., Ck+1. (b) ϕis satisfiable if and only if at configuration Cn+2pthere exists some membrane labelled by 2 which contains an object dp. Proof. (a) By induction on k. For the base case k =1it suffices to note that configuration Cn+p+2is obtained from configuration Cn+p+1by applying the rules [βn+p+1→βn+p+2]1and [c1c2→d2]2. Let us assume that the result holds for k, 1 ≤k <p −1. Then, at configuration C(n+p+1)+kwe have C(n+p+1)+k(1) = {α, β(n+p+1)+k}and there are 2nmembranes labelled by 2each of them containing an object dk+1if and only if the truth assignment encoded in that membrane, makes true clauses C1, ..., Ck+1. Bearing in mind that configuration C(n+p+1)+k+1is obtained from configuration C(n+p+1)+kby applying the rules [β(n+p+1)+k→β(n+p+1)+k+1]1and [dk+1ck+2→dk+2]2, we deduce that the result holds for k +1. (b) In order to prove (b), let us note that the input formula ϕis satisfiable if and only if there exists a truth assignment σmaking true ϕ, that is, making true the clauses C1, ..., Cp. From (a) we deduce that ϕis satisfiable if and only at configuration Cn+2pthere exists some membrane labelled by 2 which contains an object dp.2 4.5. Output stage The output phase starts at the (n +2p +1)-th step, and takes exactly four steps. –Affirmative answer: if the input formula ϕis satisfiable then at least one of the truth assignments from a membrane with label 2 makes true all clauses. Thus, a copy of object dpwill appear in that membrane at configuration Cn+2p. Then, by applying the rules [dp]2→γ[ ]2and [ βn+2p−→ βn+2p+1]1, objects γand βn+2p+1are produced in the skin membrane. At the next step, by applying rules [ αγ −→ γ]1and [ βn+2p+1−→ β]1, objects γand βare produced in the skin membrane. At the step n +2p +3, by applying rule [ γ−→ γ ]1, object γ is produced in the skin membrane (let us notice that object βcannot interact with α). Finally, at the next step, by applying rule [ γ ]1−→ yes [ ]1, object yes is sent out to the environment. Hence, the computation halts and the answer of the computation is yes. –Negative answer: if the input formula ϕis not satisfiable then none of the truth assignments encoded by a membrane with label 2 makes the formula ϕtrue. Thus, object dpdoes not appear in any membrane labelled by 2 in configuration Cn+2p. At the step n +2p +1, only rule [ βn+2p−→ βn+2p+1]1is applicable to Cn+2p. Then, Cn+2p+1(1) ={α, βn+2p+1}. At the next step, by applying rule [ βn+2p+1−→ β]1we have Cn+2p+2(1) ={α, β}. At the step n +2p +3, rule [ αβ−→ β ]1produces an object β in the skin membrane. Finally, at the last step, by applying rule [ β ]1−→ no [ ]1 an object no is released to the environment. Consequently, the computation halts and the answer of the computation is no. 5. Main results Theorem 1. SAT ∈PMCDAM0(mcmp,+c,−d,−n). Proof. The family of P systems previously constructed verifies the following: (a) Every system of the family belongs to DAM0(mcmp, +c, −d, −n). (b) The family is polynomially uniform by Turing machines because for each n, p ∈N, the amount of resources needed to build (n, p)is of a polynomial order in nand p: –Size of the alphabet: 3np2+3n2p +5np +7n2 2+5n 2+4p +10 ∈(max{np2, n2p}). – Initial number of membranes: 2 ∈(1). – Initial number of objects in membranes: 2np +n +2 ∈(np). –Number of rules: 3np2+3n2p +8np +7n2 2+n 2+3p +7 ∈(max{np2, n2p}). – Maximal number of objects involved in any rule: 3 ∈(1). (c) The pair (cod, s)of polynomial-time computable functions defined fulfil the following: for each input formula ϕof the SAT problem, s(ϕ)is a natural number, cod(ϕ)is an input multiset of the system (s(ϕ)), and for each n ∈N, s−1(n) is a finite set. (d) The family is polynomially bounded: indeed, for each input formula ϕof the SAT problem, the deterministic P system (s(ϕ)) +cod(ϕ)takes exactly n +2p +4steps, nbeing the number of variables of ϕand pthe number of clauses. (e) The family is sound with regard to (X, cod, s): indeed, for each input formula ϕ, if the computation of (s(ϕ)) + cod(ϕ)is an accepting computation, then ϕis satisfiable. (f) The family is complete with regard to (X, cod, s): indeed, for each input formula ϕsuch that it is satisfiable, the computation of (s(ϕ)) +cod(ϕ)is an accepting computation. Therefore, the family of P systems previously constructed solves the SAT problem in polynomial time in a uniform way. 2 Corollary 1. NP ∪co −NP ⊆PMCDAM0(mcmp,+c,−d,−n). Proof. It suffices to note that the SAT problem is an NP-complete problem, SAT ∈PMCDAM0(mcmp,+c,−d,−n), and class PMCDAM0(mcmp,+c,−d,−n)is closed under polynomial-time reduction and under complement. 2 Corollary 2. P =PMCSAM0(mcmp,+c,−d,−n). Proof. It suffices to notice that P =PMCSAM0(bmc,+c,−d,−n)and each rule using minimal cooperation and minimal production is also a rule using bounded minimal cooperation, and realizing that the class is closed under polynomial-time reduction. For the reverse inclusion, we only need to keep in mind the Sevilla theorem to see that we can simulate any Deterministic Turing Machine with this kind of membrane systems. 2 6. Conclusions Limitations of polarizationless P systems with active membranes not using dissolution rules, with respect to efficiency, are well known. In this paper, the computational efficiency of such kind of P systems using only division rules for elementary membranes is studied in the case that a very restrictive cooperation in object evolution rules is considered. Specifically, the left-hand side of the rules consists of at most two objects and each such rule only can produce a single object. The efficiency of these systems is shown, improving a result concerning object evolution rules with minimal cooperation, where the length of their right-hand side is less than or equal to the corresponding left-hand side. It is worth pointing out that the situation is completely different when division rules is replaced by separation rules; that is, when in the mechanism of producing an exponential number of membranes in linear time, distribution of objects is considered instead of the replication of objects. In this case, only problems in class Pcan be efficiently solved by families of polarizationless P systems with active membranes which use minimal cooperation and minimal production in object evolution rules. Consequently, new frontiers of efficiency are obtained. These results confirm the strength of the replication with respect to the distribution of objects, from an efficiency point of view, and the irrelevant role played by dissolution when minimal cooperation is considered. As future work, we propose to study polarizationless P systems with active membranes when cooperation in communication rules is considered instead of cooperation in object evolution rules. It seems that, in this case, division rules for non-elementary membranes can play a relevant role from a computational complexity point of view. Acknowledgements This work was partially supported by Grant numbers 61472328 and 61320106005 of the National Natural Science Foundation of China. References [1] A. Alhazov, L. Pan, Polarizationless P systems with active membranes, Grammars 7 (2004) 141–159. [2] A. Alhazov, L. Pan, Gh. P˘ aun, Trading polarizations for labels in P systems with active membranes, Acta Inform. 41 (2–3) (2004) 111–144. [3] A. Alhazov, R. Freund, Gh. P˘ aun, P systems with active membranes and two polarizations, in: Gh. P˘ aun, A. Riscos-Núñez, A. Romero-Jiménez, F. Sancho- Caparrini (Eds.), Proceedings of the Second Brainstorming Week on Membrane Computing, Sevilla, 2–7 February 2004, Research Group on Natural Computing, TR 01/2004, Universidad de Sevilla, Fénix Editora, 2004, pp. 20–35. [4] A. Alhazov, M.J. Pérez-Jiménez, Uniform solution of QSAT using polarizationless active membranes, in: Lecture Notes in Computer Science, vol. 4664, 2007, pp. 122–133. [5] M.R. Garey, D.S. Johnson, Computers and Intractability: AGuide to the Theory of NP-Completeness, W.H. Freeman and Company, 1979. [6] M.A. Gutiérrez-Naranjo, M.J. Pérez-Jiménez, A. Riscos-Núñez, F.J. Romero-Campero, A. Romero-Jiménez, Characterizing tractability by cell–like membrane systems, in: K.G. Subramanian, K. Rangarajan, M. Mukund (Eds.), Formal Models, Languages and Applications, World Scientific, Singapore, 2006, pp. 137–154. [7] M.A. Gutiérrez-Naranjo, M.J. Pérez-Jiménez, A. Riscos-Núñez, F.J. Romero-Campero, On the power of dissolution in P systems with active membranes, in: Lecture Notes in Computer Science, vol. 3850, 2006, pp. 224–240. [8] L. Pan, T.-O. Ishdorj, P systems with active membranes and separation rules, J.UCS 10 (5) (2004) 630–649. [9] L. Pan, A. Alhazov, Solving HPP and SAT by P systems with active membranes and separation rules, Acta Inform. 43 (2006) 131–145. [10] L. Pan, A. Alhazov, T.-O. Ishdorj, Further remarks on P systems with active membranes, separation, merging, and release rules, Soft Comput. 8 (2004) 1–5. [11] Gh. P˘ aun, Computing with membranes, J. Comput. System Sci. 61 (1) (2000) 108–143. [12] Gh. P˘ aun, Attacking NP-complete problems, in: I. Antoniou, C. Calude, M.J. Dinneen (Eds.), Unconventional Models of Computation, UMC’2K, Springer- Verlag, 2000, pp. 94–115. [13] Gh. P˘ aun, G. Rozenberg, A. Salomaa, The Oxford Handbook of Membrane Computing, Oxford University Press, 2010. [14] M.J. Pérez-Jiménez, F.J. Romero-Campero, Trading polarizations for bi-stable catalysts in P systems with active membranes, in: Lecture Notes in Computer Science, vol. 3365, 2005, pp. 373–388. [15] A.E. Porreca, G. Mauri, C. Zandron, Complexity classes for membrane systems, RAIRO Theor. Inform. Appl. 40 (2) (2006) 141–162. [16] P. Sosík, PSPACE limits the power of P systems with active membranes, J. Autom. Lang. Comb. 19 (1–4) (2014) 291–304. [17] P. Sosík, A. Rodríguez-Patón, Membrane computing and complexity theory: a characterization of PSPACE, J. Comput. System Sci. 73 (1) (2007) 137–152. [18] L. Valencia-Cabrera, D. Orellana-Martín, M.A. Martínez-del-Amor, A. Riscos-Núñez, M.J. Pérez-Jiménez, Polarizationless P systems with active membranes: computational complexity aspects, J. Autom. Lang. Comb. 21 (1–2) (2016) 101–117. [19] L. Valencia-Cabrera, D. Orellana-Martín, M.A. Martínez-del-Amor, A. Riscos-Núñez, M.J. Pérez-Jiménez, Computational efficiency of minimal cooperation and distribution in polarizationless P systems with active membranes, Fund. Inform. 153 (1–2) (2017) 147–172, http://dx.doi.org/10.3233/FI-2017-1535. [20] L. Valencia-Cabrera, D. Orellana-Martín, A. Riscos-Núñez, M.J. Pérez-Jiménez, Minimal cooperation in polarizationless P systems with active membranes, in: C. Graciani, et al. (Eds.), Proceedings of the Fourteenth Brainstorming Week on Membrane Computing, Sevilla, 1–5 February 2016, Research Group on Natural Computing, TR 01/2016, Universidad de Sevilla, Fénix Editora, 2016, pp. 327–356.