Restricted Polarizationless P Systems with Active Membranes: Minimal Cooperation Only Outwards

Restricted Polarizationless P Systems with Active Membranes: Minimal Cooperation Only Outwards Luis Valencia-Cabrera, David Orellana-Mart´ın, Miguel ´ A. Mart´ınez-del-Amor, Agust´ın Riscos-N´u˜nez, Mario J. P´erez-Jim´enez Research Group on Natural Computing Department of Computer Science and Artificial Intelligence Universidad de Sevilla Avda. Reina Mercedes s/n, 41012 Sevilla, Spain E-mail: {lvalencia, dorellana, mdelamor, ariscosn, marper}@us.es Summary. Membrane computing is a computing paradigm providing a class of distributed parallel computing devices of a biochemical type whose process units represent biological membranes. In the cell-like basic model, a hierarchical membrane structure formally described by a rooted tree is considered. It is well known that families of such systems where the number of membranes can only decrease during a computation (for instance by dissolving membranes), can only solve in polynomial time problems in class P.P systems with active membranes is a variant where membranes play a central role in their dynamics. In the seminal version, membranes have an electrical polarization (positive, negative, or neutral) associated in any instant, and besides being dissolved, they can also replicate by using division rules. These systems are computationally universal, that is, equivalent in power to deterministic Turing machines, and computationally efficient, that is, able to solve computationally hard problems in polynomial time. If polarizations in membranes are removed and dissolution rules are forbidden, then only problems in class Pcan be solved in polynomial time by these systems (even in the case when division rules for non-elementary membranes are permitted). In that framework it has been shown that by considering minimal cooperation (left-hand side of such rules consists of at most two symbols) and minimal production (only one object is produced by the application of such rules) in object evolution rules, such systems provide efficient solutions to NP–complete problems. In this paper, minimal cooperation and minimal production in communication rules instead of object evolution rules is studied, and the computational efficiency of these systems is obtained in the case where division rules for non-elementary membranes are permitted. Key words: Membrane Computing, polarizationless P systems with active membranes, cooperative rules, the Pversus NP problem, SAT problem. 254 L. Valencia-Cabrera et al. 1 Introduction Membrane Computing is an emergent branch of Natural Computing providing distributed parallel and non-deterministic computing models whose computational devices are called membrane systems having units processor called compartments. This computing paradigm is inspired by some basic biological features, by the structure and functioning of the living cells, as well as from the cooperation of cells in tissues, organs, and organisms. Celllike membrane systems use the biological membranes arranged hierarchically, inspired from the structure of the cell. In Membrane Computing, some variants capture the fact that membranes are not at all passive from a biochemistry view, for instance, the passing of a chemical compound through a membrane is often done by a direct interaction with the membrane itself. Some variants of P systems where the central role in their dynamics is played by the membranes have been considered. In these models, the membranes not only directly mediate the evolution and the communication of objects, but they can replicate themselves by means of a division process. Inspired by these features, P systems with active membranes [6] were introduced, based on processing multisets by means of non-cooperative rewriting rules, that is, rules where its left-hand side has at most only one object. Specifically, objects evolve inside membranes which can communicate between each other, can dissolve, and moreover (inspired by cellular mitosis process) can replicate by means of division rules. It is assumed that each membrane has associated an electrical polarization in any instant, one of the three possible: positive, negative, or neutral. P systems with active membranes are computationally complete, that is, any recursively enumerable set of vectors of natural numbers (in particular, each recursively enumerable set of natural numbers) can be generated by such a system [6]. Hence, they are equivalent in power to deterministic Turing machines. What about the computational efficiency of P systems with active membranes? The key is certainly in the use of division rules, as we can deduce from the socalled Milano theorem [13]: A deterministic P system with active membranes but without membrane division can be simulated by a deterministic Turing machine with a polynomial slowdown. However, P systems with active membranes which make use of division rules have the ability to provide efficient solutions to computationally hard problems, by making use of an exponential workspace created in a polynomial time. Specifically, NP-complete problems can be solved in polynomial time by families of P systems with active membranes, without dissolution rules and which use division rules only for elementary membranes [6]. Moreover, the class of decision problems which can be solved by families of P systems with active membranes with dissolution rules and which use division for elementary and non-elementary membranes is equal to PSPACE [8]. Consequently, the usual framework of P systems with active membranes and electrical polarizations for solving decision problems seems to be too powerful from the computational complexity point of view. With respect to the computational efficiency, in the classical framework of P system with active membranes, dissolution rules play an “innocent” role as well as P Systems with Active Membranes: Minimal Cooperation Only Outwards 255 division for non-elementary membranes. However, if electrical charges are removed then these kind of rules come to play a relevant role. Specifically, P systems with active membranes and without electrical charges were initially studied in [1, 2] by replacing electrical charges by the ability to change the label of the membranes. In this paper, polarizationless P systems with active membranes where labels of membranes keep unchanged by the application of rules, are considered. In this new framework, if dissolution rules are forbidden then only problems in class P can be solved in an efficient way, even in the case that division for non-elementary membranes are permitted [5]. Is the class of polarizationless P systems with active membranes, with dissolution but using only division rules for elementary membranes computationally efficient? If P6=NP, which is at all expected, then it is an open question, so-called P˘aun’s conjecture. In the seminal paper where P systems with active membranes were introduced, Gh. P˘aun says that “working with non-cooperative rules is natural from a mathematical point of view but from a biochemical point of view this is not only non-necessary, but also non-realistic: most of the chemical reactions involve two or more than two chemical compounds (and also produce two or more than two compounds)”. In this context, a restricted cooperation has been considered in the classical framework of polarizationless P systems with active membranes. Specifically, minimal cooperation (the left-hand side and the right-hand side of any rules have, at most, two objects) in object evolution rules, has been previously studied from a computational complexity point of view. A polynomial-time solution to the SAT problem by means of families of polarizationless P systems with active membranes, with minimal cooperation in object evolution rules, has been provided [9]. Recently, this result has been improved by considering minimal cooperation in object evolution rules with and additional restriction: the right-hand side of any rules has only one object (called minimal cooperation and minimal production) [11]. A relevant fact in these results is the following: dissolution rules and division rules for non-elementary membranes are not necessary to reach the computational efficiency. In this paper the role of minimal cooperation and minimal production in communication rules instead of object evolution rules, is studied from a complexity point of view. Specifically, by using families of membrane systems which use these syntactical ingredients, a polynomial-time solution to the SAT problem is provided but allowing division rules for non-elementary membranes. The paper is structured as follows. First, some basic notions are recalled and the terminology and notation to be used in the paper is presented. Then, Section 3 introduces the model that will be investigated in this paper: polarizationless P systems with active membranes, with minimal cooperation and minimal production in their communication rules. Section 4 contains the main result of this paper, showing that these systems are capable of solving an NP-complete problem in an efficient way. Finally, the paper concludes with some final remarks and ideas for future work. 256 L. Valencia-Cabrera et al. 2 Preliminaries An alphabet Γis a non-empty set and their elements are called symbols. A string u over Γis an ordered finite sequence of symbols, that is, a mapping from a natural number n∈Nonto Γ. The number nis called the length of the string uand it is denoted by |u|. The empty string (with length 0) is denoted by λ. The set of all strings over an alphabet Γis denoted by Γ∗. A language over Γis a subset of Γ∗. Amultiset 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}. A multiset is finite (respectively, empty) if its support is a finite (respectively, empty) set. We denote by ∅the empty multiset. Let m1= (Γ, f1), m2= (Γ, f2) be multisets over Γ, then the union of m1 and m2, denoted by m1+m2, is the multiset (Γ, g), where g(x) = f1(x) + f2(x) for each x∈Γ. We denote by Mf(Γ) the set of all multisets over Γ. 2.1 Graphs and trees Let us recall some notions related with graph theory (see [3] for details). An undirected graph is an ordered pair (V, E) where Vis a set whose elements are called nodes or vertices and E={{x, y} | x∈V, y ∈V, x 6=y}whose elements are called edges. A path of length k≥1 from a node uto a node vin a graph (V, E) is a finite sequence (x0, x1, . . . , xk) of nodes such that x0=u,xk=vand {xi, xi+1} ∈ E. If k≥2 and x0=xkthen we say that the path is a cycle of the graph. A graph with no cycle is said to be acyclic. An undirected graph is connected if there exist paths between every pair of nodes. Arooted tree is a a connected, acyclic, undirected graph in which one of the vertices (called the root of the tree) is distinguished from the others. Given a node x(different from the root), if the last edge on the (unique) path from the root of the tree to the node xis {x, y}(in this case, x6=y), then yis the parent of node xand xis achild of node y. The root is the only node in the tree with no parent. A node with no children is called a leaf. 2.2 The Cantor pairing function The Cantor pairing function encodes pairs of natural numbers by single natural numbers, and it is defined as follows: for each n, p ∈N hn, pi=(n+p)(n+p+ 1) 2+n The Cantor pairing function is a primitive recursive function and bijective from N×Nonto N. Then, for each t∈Nthere exist unique natural numbers n, p ∈N such that t=hn, pi. P Systems with Active Membranes: Minimal Cooperation Only Outwards 257 2.3 Decision problems and languages A decision problem Xis an ordered pair (IX, θX), where IXis a language over a finite alphabet ΣXand θXis a total Boolean function over IX. The elements of IXare called instances of the problem X. Each decision problem Xhas associated a language LXover the alphabet ΣXas follows: LX={u∈ΣX ∗|θX(u)=1}. Conversely, every language Lover an alphabet Σhas associated a decision problem XL= (IXL, θXL) as follows: IXL=Σ∗and θXL(u) = 1 if and only if u∈L. Therefore, given a decision problem Xwe have XLX=X, and given a language Lover an alphabet Σwe have LXL=L. Then, solving a decision problem can be expressed equivalently as the task of recognizing the language associated with it. 2.4 Recognizer membrane systems Recognizer membrane systems were introduced in [7] and they provide a natural framework to solve decision problems. This kind of systems are characterized by the following features: (a) the working alphabet Γhas two distinguished objects yes and no; (b) there exists an input membrane and an input alphabet Σstrictly contained in Γ; (c) the initial contents of the membranes are multisets over Γ\Σ; (d) all computations halt; and (e) for each computation, 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. Given a recognizer membrane system, Π, for each multiset mover the input alphabet Σwe denote by Π+mthe membrane system Πwith input multiset m, that is in the initial configuration of that system, the multiset mis added to the initial content of the input membrane. Thus, in a recognizer membrane system, Π, there exists an initial configuration associated with each multiset m∈Mf(Σ). 3 Minimal cooperation and minimal production in communication rules Definition 1. A polarizationless P system with active membranes, with simple object evolution rules, without dissolution, with division rules for elementary and non-elementary membranes, and which makes use of minimal cooperation and minimal production in send-out communication rules, is a tuple Π= (Γ, Σ, H, µ, M1,...,Mq,R, iin, iout) where: •Γis a finite alphabet whose elements are called objects and contains two distinguished objects yes and no. •Σ(Γis the input alphabet. 258 L. Valencia-Cabrera et al. •His a finite alphabet such that H∩Γ=∅whose elements are called labels. •q≥1is the degree of the system. •µis a labelled rooted tree (called membrane structure)consisting of qnodes injectively labelled by elements of H(the root of µis labelled by rµ). • M1,...,Mqare multisets over Γ\Σ. • R is a finite set of rules, of the following forms: (a0) [ a→b]h, where h∈H,a, b ∈Γ,u∈Mf(Γ) (simple object evolution rules). (b0)a[ ]h→[b]h, where h∈H\ {rµ},a, b, c ∈Γ(send–in communication rules). (c0) [ a b ]h→c[ ]h, where h∈H,a, b ∈Γ(send–out communication rules with minimal cooperation and minimal production). (d0) [ a]h→b, where h∈H\ {iout, rµ},a, b ∈Γ(dissolution rules). (e0) [ a]h→[b]h[c]h, where h∈H\ {iout, rµ},a, b, c ∈Γand his the label of an elementary membrane µ(division rules for elementary membranes). (f0) [ [ ]h1[ ]h2]h0→[ [ ]h1]h0[ [ ]h2]h0, where h0, h1, h2∈Hand h06=rµ(division rules for non-elementary membranes). •iin ∈H,iout ∈H∪ {env}(if iout ∈Hthen iout is the label of a leaf of µ). In a similar way is defined the concept of “polarizationless P system with active membranes, with simple object evolution rules, without dissolution, with division rules for elementary and non-elementary membranes, and which makes use of minimal cooperation and minimal production in send-in communication rules ”. The only difference concerns rules of type (b0) and (c0). In this case are, respectively: (b0 0)a b [ ]h→[c]hfor h∈H\ {rµ},a, b ∈Γ(send–in communication rules with minimal cooperation and minimal production). (c0 0) [ a]h→b[ ]hfor h∈H,a, b, c ∈Γ(send–out communication rules). The semantics of this kind of P systems follows the usual principles of P systems with active membranes [6]. We denote by DAM0(+es, mcmpout,−d, +n) (respectively, DAM0(+es, mcmpin,−d, +n)) the class of all recognizer polarizationless P system with active membranes, with simple object evolution rules, without dissolution, with division rules for elementary and non-elementary membranes, which make use of minimal cooperation and minimal production in send-out (respectively, send-in) communication rules. 4 Solving SAT in DAM0(+es, mcmpout,−d, +n) In this section, a polynomial-time solution to SAT problem, is explicitly given in the framework of recognizer polarizationless P systems with active membranes P Systems with Active Membranes: Minimal Cooperation Only Outwards 259 with simple object evolution rules, without dissolution and with division rules for elementary and non-elementary membranes which make use of minimal cooperation and minimal production in send-in communication rules. For that, a family Π={Π(t)|t∈N}of recognizer P systems from DAM0(+es, mcmpout,−d, +n) will be presented. 4.1 Description of a solution to SAT problem in DAM0(+es, mcmpout,−d, +n) For each n, p ∈N, we consider the recognizer P system Π(hn, pi)=(Γ, Σ, H, µ, M0,M1,M2,R, iin, iout) from DAM0(+es, mcmpout,−d, +n), defined as follows: (1)Working alphabet: Γ=Σ∪ {yes ,no ,#}∪{ai,k |1≤i≤n∧1≤k≤2i−1} ∪ {αk|0≤k≤4np +n+ 2p} ∪ {βk|0≤k≤4np +n+ 2p+ 1} ∪ {γk|0≤k≤4np +n} ∪ {ti,k, fi,k |1≤i≤n∧2i−1≤k≤2n+ 2p−1} ∪ {Ti, Fi|1≤i≤n} ∪ {cj|1≤j≤p} ∪ {cj,k |1≤j≤p∧0≤k≤np −1}∪{dj|1≤j≤p} ∪ {xi,j,k, xi,j,k, x∗ i,j,k |1≤i≤n∧1≤j≤p∧ 1≤k≤n+ 2np +n(j−1) + (i−1)} where the input alphabet is Σ={xi,j,0, xi,j,0, x∗ i,j,0|1≤i≤n∧1≤j≤p}; (2)H={0,1,2}; (3)Membrane structure: µ= [ [ [ ]2]1]0, that is, µ= (V, E) where V={0,1,2} and E={(0,1)(1,2)} (4)Initial multisets: M0={α0, β0},M1=∅,M2={γ0} ∪ {ai,1, T p i, Fp i|1≤i≤ n}. (5)The set of rules Rconsists of the following rules: 5.1Counters for synchronize the answer of the system. [αk−→ αk+1 ]0,for 0 ≤k≤4np +n+ 2p−1 [βk−→ βk+1 ]0,for 0 ≤k≤4np +n+ 2p [γk−→ γk+1 ]2,for 0 ≤k≤4np +n−1 5.2Rules to generate 2nmembranes labelled by 1 and 2nmembranes labelled by 2 (these encoding all possible truth assignment of nvariables of the input formula). [ai,2i−1]2−→ [ti,i ]2[fi,i ]2,for 1 ≤i≤n [ai,j −→ ai,j+1 ]2,for 2 ≤i≤n, 1≤j≤2i−2 [ [ ]2[ ]2]1−→ [ [ ]2]1[ [ ]2]1 [ti,j −→ ti,j+1 ]2 [fi,j −→ fi,j+1 ]2,for 1 ≤i≤n, i ≤j≤2n−1 260 L. Valencia-Cabrera et al. 5.3Rules to produce exactly pcopies of each truth assignment encoded by membranes labelled by 2. [ti,2jn Fi]2−→ ti,2jn+1 [ ]2 [fi,2jn Ti]2−→ fi,2jn+1 [ ]2 ti,(2j+1)n[ ]2−→ [ti,(2j+1)n+1 ]2 fi,(2j+1)n[ ]2−→ [fi,(2j+1)n+1 ]2        ,for 1 ≤i≤n, 1≤j≤p−1 [ti,2np Fi]2−→ # [ ]2 [fi,2np Ti]2−→ # [ ]2,for 1 ≤i≤n [ti,(2j+1)n+k−→ ti,(2j+1)n+k+1 ]2 [fi,(2j+1)n+k−→ fi,(2j+1)n+k+1 ]2 [ti,2jn+k−→ ti,2jn+k+1 ]1 [fi,2jn+k−→ fi,2jn+k+1 ]1        ,for 1≤i≤n, 1≤j≤p−1, 1≤k≤n−1 5.4Rules 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   ,for 1≤i≤n, 1≤j≤p, 0≤k≤2np +n+n(j−1) + (i−1) −1 5.5Rules implementing the first checking stage. [Tixi,j,2np+n+n(j−1)+(i−1)]2−→ cj,0[ ]2 [Tixi,j,2np+n+n(j−1)+(i−1)]2−→ #[ ]2 [Tix∗ i,j,2np+n+n(j−1)+(i−1)]2−→ #[ ]2 [Fixi,j,2np+n+n(j−1)+(i−1)]2−→ #[ ]2 [Fixi,j,2np+n+n(j−1)+(i−1)]2−→ cj,0[ ]2 [Fix∗ i,j,2np+n+n(j−1)+(i−1)]2−→ #[ ]2                ,for 1≤i≤n, 1≤j≤p 5.6Rules implementing the second checking stage. [cj,k −→ cj,k+1 ]1,for 1 ≤j≤p, 0≤k≤np −2 cj,np−1[ ]2−→ [cj]2,for 1 ≤j≤p [γ4np+nc1]2−→ d1[ ]2 [djcj+1 ]2−→ dj+1[ ]2 dj[ ]2−→ [dj]2,for 1 ≤j≤p−1 5.7Rules to provide the correct answer of the system. [dp]1−→ dp[ ]1 [α4np+n+2pdp]0−→ yes [ ]0 [α4np+n+2pβ4np+n+2p+1 ]0−→ no [ ]0 (6)the input membrane is the membrane labelled by 2 (iin = 2) and the output region is the environment (iout =env). 5 A formal verification Let ϕ=C1∧. . . ∧Cpan instance of SAT problem consisting of pclauses Cj=lj,1∨. . . ∨lj,rj, 1 ≤j≤p, where V ar(ϕ) = {x1, . . . , xn}, and lj,k ∈ P Systems with Active Membranes: Minimal Cooperation Only Outwards 261 {xi,¬xi|1≤i≤n}, 1 ≤j≤p, 1 ≤k≤rj. Let us asume that the number of variables, n, and the number of clauses, p, of ϕ, are greater or equal to 2. We consider the polynomial encoding (cod, s) from SAT in Πdefined as follows: For each ϕ∈ISAT with nvariables and pclauses, s(ϕ) = hn, piand cod(ϕ) = {xi,j,0|xi∈Cj}∪{xi,j,0|¬xi∈Cj}∪{x∗ i,j,0|xi6∈ Cj,¬xi6∈ Cj} 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   That is, j-th row (1 ≤j≤p) represents the j-th clause Cjof ϕ. We denote (cod(ϕ))p jthe code of the clauses Cj, . . . , Cp, that is, the expression containing from j-th row to p-th row. For instance, cod(ϕ)p 2=x∗ 1,2,0x2,2,0x∗ 3,2,0x4,2,0 x∗ 1,3,0x2,3,0x3,3,0x4,3,0 We denote (codk(ϕ))p j) the code cod(ϕ)p jwhen the third index of the variables equal 3. For instance: row to p-th row. For instance, cod3(ϕ)p 2=x∗ 1,2,3x2,2,3x∗ 3,2,3x4,2,3 x∗ 1,3,3x2,3,3x3,3,3x4,3,3 We denote (cod0 k(ϕ))p j) the code cod(ϕ)p jwhen the third index of the variables equal 3. For instance: row to p-th row. For instance, cod0 3(ϕ)p 2=x∗0 1,2,3x0 2,2,3x∗0 3,2,3x0 4,2,3 x∗0 1,3,3x0 2,3,3x0 3,3,3x0 4,3,3 We denote (cod∗(ϕ))p j) the code cod(ϕ)p jwhen the third index does not exist. For instance: row to p-th row. For instance, cod∗(ϕ)p 2=x∗1,2x2,2x∗ 3,2x4,2 x∗1,3x2,3x3,3x4,3 The Boolean formula ϕwill be processed by the system Π(s(ϕ)) + 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 in object evolution rules and division rules only for elementary membranes, and it consists of the following stages: •Generation stage: using separation rules, beside other rules that make a “simulation” of division rules, we get all truth assignments for the variables {x1, . . . , xn}associated with ϕare produced. Specifically, 2nmembranes labelled by 1 and 2nlabelled by 2 are generated. Each of the former ones encodes a truth assignment. This stage takes exactly n+2np steps, being nthe number of variables of ϕ. 268 L. Valencia-Cabrera et al. - at configuration C3nwe have C3n(0) = {α3n, β3n}and there exist 2n membranes labelled by 1 containing and a different subset of objects ri,3n+1−i, 1 ≤i≤n, being r∈ {t, f}, that is, the corresponding truth assignment of the branch; and 2nmembranes labelled by 2 containing the input multiset cod3n(ϕ), an object γ3n,pcopies of Tiand Fi, being 1≤i≤nif the truth assignment associated to the branch contains its corresponding object tior fi,p−1 objects otherwise. Then, configuration C3nyields configuration C3n+1 by applying the rules: t1,3n[ ]2→[t1,3n+1 ]2 f1,3n[ ]2→[f1,3n+1 ]2 [ti,3n−i+1 →ti,3n−i+2 ]1 [fi,3n−i+1 →fi,3n−i+2 ]1for 2 ≤i≤n [α3n→α3n+1 ]0 [β3n→β3n+1 ]0 [γ3n→γ3n+1 ]2 [xi,j,3n→xi,j,3n+1 ]2 [xi,j,3n→xi,j,3n+1 ]2 [x∗ i,j,3n→x∗ i,j,3n+1 ]2   for 1 ≤i≤n, 1≤j≤p Thus, C3n+1(0) = {α3n+1, β3n+1}, and there exist 2nmembranes labelled by 1 containing a different subset of objects ri,3n−i+2, 2 ≤i≤n, being r∈ {t, f}; and 2nmembranes labelled by 2 containing the input multiset cod3n+1(ϕ), an object γ3n+1,pcopies of Tiand Fi, being 1≤i≤nif the truth assignment associated to the branch contains its corresponding object tior fi,p−1 objects otherwise and an object r1,3n+1, being r∈ {t, f}. - Supposing, by induction, result is true for k(1 ≤k≤n) -C3n+k(0) = {α3n+k, β3n+k} - In C3n+kthere are 2nmembranes labelled by 1 such that each of them contains objects ri,3n+k−i+1,k+ 1 ≤i≤n, being r∈ {t, f}. - In C3n+kthere are 2nmembranes labelled by 2 such that each of them contains ?the input multiset cod3n+k(ϕ); ?an object γ3n+k; ? p copies of every Tiand Fifor 1 ≤i≤nor their corresponding ti or fiis assigned to that branch, p−lcopies otherwise; and ?a different subset of objects ri,3n+k−i+1, 1 ≤i≤k, being r∈ {t, f}. Then, configuration C3n+kyields configuration C3n+k+1 by applying the rules: tk+1,3n[ ]2→[tk+1,3n+1 ]2 fk+1,3n[ ]2→[fk+1,3n+1 ]2 [ti,3n+k−i+1 →ti,3n+k−i+2 ]1 [fi,3n+k−i+1 →fi,3n+k−i+2 ]1for k+ 2 ≤i≤n [ti,3n+k−i+1 →ti,3n+k−i+2 ]2 [fi,3n+k−i+1 →fi,3n+k−i+2 ]2for 1 ≤i≤k P Systems with Active Membranes: Minimal Cooperation Only Outwards 269 [α3n+k→α3n+k+1 ]0 [β3n+k→β3n+k+1 ]0 [γ3n+k→γ3n+k+1 ]2 [xi,j,3n+k→xi,j,3n+k+1 ]2 [xi,j,3n+k→xi,j,3n+k+1 ]2 [x∗ i,j,3n+k→x∗ i,j,3n+k+1 ]2   for 1 ≤i≤n, 1≤j≤p Therefore, the following holds -C3n+k+1(0) = {α3n+k+1, β3n+k+1} - In C3n+k+1 there are 2nmembranes labelled by 1 such that each of them contains objects ri,3n+k−i+2,k+ 2 ≤i≤n, being r∈ {t, f}. - In C3n+k+1 there are 2nmembranes labelled by 2 such that each of them contains ?the input multiset cod3n+k+1(ϕ); ?an object γ3n+k+1; ? p copies of every Tiand Fifor 1 ≤i≤nor the corresponding tior fiis assigned to that branch, p−lcopies otherwise; and ?a different subset of objects ri,3n+k−i+2, 1 ≤i≤k+ 1, being r∈ {t, f}. - Supposing, by induction, result is true for l(0 ≤l≤p−1) (a0) The base case k= 1 is trivial because: - at configuration C2n+(l+1)n1we have: C2n+(l+1)n(0) = {α2n+(l+1)n, β2n+(l+1)n}and there exist 2nempty membranes labelled by 1; and 2n membranes labelled by 2 containing the input multiset cod2n+(l+1)n(ϕ), an object γ2n+(l+1)n,pcopies of Tiand Fi, being 1 ≤i≤n, and p−l copies for Ti(resp. Fi) objects that are in a branch with an object fi (resp. ti) and a different subset of objects ri,2n+(l+1)n−i+1, 1 ≤i≤n, being r∈ {t, f}, the corresponding truth assignment of the branch. Then, configuration C2n+(l+1)nyields configuration C2n+(l+1)n+1 by applying the rules: [ti,2n+(l+1)nFi]2→ti,2n+(l+1)n+1[ ]2 [fi,2n+(l+1)nTi]2→fi,2n+(l+1)n+1[ ]2 [ti,2n+(l+1)n+1−i→ti,2n+(l+1)n+2−i]2 [fi,2n+(l+1)n+1−i→fi,2n+(l+1)n+2−i]2for 2 ≤i≤n [α2n+(l+1)n→α2n+(l+1)n+1 ]0 [β2n+(l+1)n→β2n+(l+1)n+1 ]0 [γ2n+(l+1)n→γ2n+(l+1)n+1 ]2 [xi,j,2n+(l+1)n→xi,j,2n+(l+1)n+1 ]2 [xi,j,2n+(l+1)n→xi,j,2n+(l+1)n+1 ]2 [x∗ i,j,2n+(l+1)n→x∗ i,j,2n+(l+1)n+1 ]2   for 1 ≤i≤n, 1≤j≤p Thus, C2n+(l+1)n+1(0) = {α2n+(l+1)n+1, β2n+(l+1)n+1}, and there exist 2nmembranes labelled by 1 containing and an object r1,2n+(l+1)n+1, 1Note that (l+ 1)n=ln +n, and it has been demonstrated in the first step of the induction that it is correct. 270 L. Valencia-Cabrera et al. being r∈ {t, f}; and 2nmembranes labelled by 2 containing the input multiset cod2n+(l+1)n+1(ϕ), an object γ2n+(l+1)n+1,pcopies of Ti(resp. Fi) being 1 ≤i≤nif the corresponding ti(resp. fi) object exists in that branch, otherwise p−lcopies of Fi(resp. Ti) if 2 ≤i≤n,p−l−1 otherwise and a different subset of objects ri,2n+(l+1)n−i+2, 2 ≤i≤n, being r∈ {t, f}. - Supposing, by induction, result is true for k(1 ≤k≤n) -C2n+(l+1)n+k(0) = {α2n+(l+1)n+k, β2n+(l+1)n+k} - In C2n+(l+1)n+kthere are 2nmembranes labelled by 1 such that each of them contains objects ri,2n+(l+1)n+k−i+1, 1 ≤i≤k, being r∈ {t, f}. - In C2n+(l+1)n+kthere are 2nmembranes labelled by 2 such that each of them contains ?the input multiset cod2n+(l+1)n+k(ϕ); ?an object γ2n+(l+1)n+k; ? p copies of Ti(resp. Fi) being 1 ≤i≤nif the corresponding ti (resp. fi) object exists in that branch, otherwise p−lcopies of Fi (resp. Ti) if k+ 1 ≤i≤n,p−l−1 otherwise; and ?a different subset of objects ri,2n+(l+1)n+k−i+1,k+ 1 ≤i≤n, being r∈ {t, f}. Then, configuration C2n+kyields configuration C2n+(l+1)n+k+1 by applying the rules: [tk+1,2n+(l+1)nFk+1 ]2→tk+1,2n+(l+1)n+1[ ]2 [fk+1,2n+(l+1)nTk+1 ]2→fk+1,2n+(l+1)n+1[ ]2 [ti,2n+(l+1)n+k−i+1 →ti,2n+k−i+2 ]2 [fi,2n+(l+1)n+k−i+1 →fi,2n+k−i+2 ]2for k+ 2 ≤i≤n [ti,2n+(l+1)n+k−i+1 →ti,2n+(l+1)n+k−i+2 ]1 [fi,2n+(l+1)n+k−i+1 →fi,2n+(l+1)n+k−i+2 ]1for 1 ≤i≤k [α2n+(l+1)n+k→α2n+(l+1)n+k+1 ]0 [β2n+(l+1)n+k→β2n+(l+1)n+k+1 ]0 [γ2n+(l+1)n+k→γ2n+(l+1)n+k+1 ]2 [xi,j,2n+(l+1)n+k→xi,j,2n+(l+1)n+k+1 ]2 [xi,j,2n+(l+1)n+k→xi,j,2n+(l+1)n+k+1 ]2 [x∗ i,j,2n+(l+1)n+k→x∗ i,j,2n+(l+1)n+k+1 ]2   for 1 ≤i≤n, 1≤j≤p Therefore, the following holds -C2n+(l+1)n+k+1(0) = {α2n+(l+1)n+k+1, β2n+(l+1)n+k+1} - In C2n+(l+1)n+k+1 there are 2nmembranes labelled by 1 such that each of them contains objects ri,2n+(l+1)n+k−i+2, 1 ≤i≤k+1, being r∈ {t, f}. - In C2n+(l+1)n+k+1 there are 2nmembranes labelled by 2 such that each of them contains ?the input multiset cod2n+(l+1)n+k+1(ϕ); ?an object γ2n+(l+1)n+k+1; P Systems with Active Membranes: Minimal Cooperation Only Outwards 271 ? p copies of Ti(resp. Fi) being 1 ≤i≤nif the corresponding ti (resp. fi) object exists in that branch, otherwise p−lcopies of Fi (resp. Ti) if k+ 2 ≤i≤n,p−l−1 otherwise; and ?a different subset of objects ri,2n+(l+1)n+k−i+2,k+ 2 ≤i≤n, being r∈ {t, f}. (a1) The base case k= 1 is trivial because: - at configuration C3n+(l+1)nwe have C3n+(l+1)n(0) = {α3n+(l+1)n, β3n+(l+1)n}and there exist 2nmembranes labelled by 1 containing a different subset of objects ri,3n+(l+1)n−i+1, 1 ≤i≤n, being r∈ {t, f}, that is, the corresponding truth assignment of the branch; and 2nmembranes labelled by 2 containing the input multiset cod3n+(l+1)n(ϕ), an object γ3n+(l+1)nand pcopies of Ti(resp. Fi) being 1 ≤i≤nif the corresponding ti(resp. fi) object exists in that branch, and p−l copies of Fi(resp. Ti). Then, configuration C3n+(l+1)nyields configuration C3n+(l+1)n+1 by applying the rules: t1,3n+(l+1)n[ ]2→[t1,3n+(l+1)n+1 ]2 f1,3n+(l+1)n[ ]2→[f1,3n+(l+1)n+1 ]2 [ti,3n+(l+1)n−i+1 →ti,3n+(l+1)n−i+2 ]1 [fi,3n+(l+1)n−i+1 →fi,3n+(l+1)n−i+2 ]1for 2 ≤i≤n [α3n+(l+1)n→α3n+(l+1)n+1 ]0 [β3n+(l+1)n→β3n+(l+1)n+1 ]0 [γ3n+(l+1)n→γ3n+(l+1)n+1 ]2 [xi,j,3n+(l+1)n→xi,j,3n+(l+1)n+1 ]2 [xi,j,3n+(l+1)n→xi,j,3n+(l+1)n+1 ]2 [x∗ i,j,3n+(l+1)n→x∗ i,j,3n+(l+1)n+1 ]2   for 1 ≤i≤n, 1≤j≤p Thus, C3n+(l+1)n+1(0) = {α3n+(l+1)n+1, β3n+(l+1)n+1}, and there exist 2nmembranes labelled by 1 containing a different subset of objects ri,3n+(l+1)n−i+2, 2 ≤i≤n, being r∈ {t, f}; and 2nmembranes labelled by 2 containing the input multiset cod3n+(l+1)n+1(ϕ), an object γ3n+(l+1)n+1,pcopies of Ti(resp. Fi) being 1 ≤i≤nif the corresponding ti(resp. fi) object exists in that branch, and p−lcopies of Fi(resp. Ti) and an object r1,3n+(l+1)n+1, being r∈ {t, f}. - Supposing, by induction, result is true for k(1 ≤k≤n) -C3n+(l+1)n+k(0) = {α3n+(l+1)n+k, β3n+(l+1)n+k} - In C3n+(l+1)n+kthere are 2nmembranes labelled by 1 such that each of them contains objects ri,3n+k−i+1,k+ 1 ≤i≤n, being r∈ {t, f}. - In C3n+(l+1)n+kthere are 2nmembranes labelled by 2 such that each of them contains ?the input multiset cod3n+(l+1)n+k(ϕ); ?an object γ3n+(l+1)n+k; ? p copies of Ti(resp. Fi) being 1 ≤i≤nif the corresponding ti (resp. fi) object exists in that branch, and p−lcopies of Fi(resp. Ti) 272 L. Valencia-Cabrera et al. ?a different subset of objects ri,3n+(l+1)n−i+1, 1 ≤i≤k, being r∈ {t, f}. Then, configuration C3n+(l+1)n+kyields configuration C3n+(l+1)n+k+1 by applying the rules: tk+1,3n+(l+1)n[ ]2→[tk+1,3n+(l+1)n+1 ]2 fk+1,3n+(l+1)n[ ]2→[fk+1,3n+(l+1)n+1 ]2 [ti,3n+(l+1)n+k−i+1 →ti,3n+(l+1)n+k−i+2 ]1 [fi,3n+(l+1)n+k−i+1 →fi,3n+(l+1)n+k−i+2 ]1for k+ 2 ≤i≤n [ti,3n+(l+1)n+k−i+1 →ti,3n+(l+1)n+k−i+2 ]2 [fi,3n+(l+1)n+k−i+1 →fi,3n+(l+1)n+k−i+2 ]2for 1 ≤i≤k [α3n+(l+1)n+k→α3n+(l+1)n+k+1 ]0 [β3n+(l+1)n+k→β3n+(l+1)n+k+1 ]0 [γ3n+(l+1)n+k→γ3n+(l+1)n+k+1 ]2 [xi,j,3n+(l+1)n+k→xi,j,3n+(l+1)n+k+1 ]2 [xi,j,3n+(l+1)n+k→xi,j,3n+(l+1)n+k+1 ]2 [x∗ i,j,3n+(l+1)n+k→x∗ i,j,3n+(l+1)n+k+1 ]2   for 1 ≤i≤n, 1≤j≤p Therefore, the following holds -C3n+(l+1)n+k+1(0) = {α3n+(l+1)n+k+1, β3n+(l+1)n+k+1} - In C3n+(l+1)n+k+1 there are 2nmembranes labelled by 1 such that each of them contains objects ri,3n+(l+1)n+k−i+2,k+2 ≤i≤n, being r∈ {t, f}. - In C3n+(l+1)n+k+1 there are 2nmembranes labelled by 2 such that each of them contains ?the input multiset cod3n+(l+1)n+k+1(ϕ); ?an object γ3n+(l+1)n+k+1; ? p copies of Ti(resp. Fi) being 1 ≤i≤nif the corresponding ti (resp. fi) object exists in that branch, and p−lcopies of Fi(resp. Ti) ?a different subset of objects ri,3n+(l+1)n+k−i+2, 1 ≤i≤k+ 1, being r∈ {t, f}. - In order to prove (b) it is enough to notice that, on the one hand, from (a) configuration C2np−12holds: -C2np−1(0) = {α2np−1, β2np−1} - In C2np−1there are 2nmembranes labelled by 1 such that each of them contains an object rn,2np, being r∈ {t, f}. - In Cn+2np−1there are 2nmembranes labelled by 2 such that each of them contains ?the input multiset cod2np−1(ϕ); ?an object γ2np−1; ? p copies of Ti(resp. Fi) being 1 ≤i≤nif the corresponding ti(resp. fi) object exists in that branch, and 1 copy otherwise; and ?a different subset of objects ri,2np−i, 1 ≤i≤n−1. 2Note that 2np −1 = n+ 2n(p−1) + (n−1) P Systems with Active Membranes: Minimal Cooperation Only Outwards 273 Then, configuration Cn+2np−1yields Cn+2np by applying the rules: tn,2np[ ]2→[tn,2np+1 ]2 fn,2np[ ]2→[fn,2np+1 ]2 [ti,n+2np−i→ti,n+2np−i+1 ]2 [fi,n+2np−i→fi,n+2np−i]2for 1 ≤i≤n−1 [αn+2np−1→αn+2np ]0 [βn+2np−1→βn+2np ]0 [γn+2np−1→γn+2np ]2 [xi,j,n+2np−1→xi,j,n+2np ]2 [xi,j,n+2np−1→xi,j,n+2np ]2 [x∗ i,j,n+2np−1→x∗ i,j,n+2np ]2   for 1 ≤i≤n, 1≤j≤p Then, we have C2np(0) = {α2np, β2np}, and there exist 2nempty membranes labelled by 1; and 2nmembranes labelled by 2 containing containing the input multiset cod2np(ϕ), an object γ2np,pcopies of Ti(resp. Fi) being 1≤i≤nif the corresponding ti(resp. fi) object exists in that branch, and 1 copy otherwise and a different multiset of objects ri,2np−i+1, 1 ≤i≤n, being r∈ {t, f}, that is, the truth assignment associated with the branch.  Proposition 3. 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 C2np+kwe have the following: -C2np+k(0) = {α2np+k, β2np+k} - There are 2nmembranes labelled by 1 such that each of them contains k objects #. - there are 2nmembranes labelled by 2 such that each of them contains ?the input multiset cod2np+k(ϕ); ?an object γ2np+k; ? p copies of Ti(resp. Fi) being 1≤i≤nif the corresponding ti(resp. fi) object exists in that branch, and 1 copy of Fi(resp. Ti) if k+1 ≤i≤n; and ?objects ri,2np+k−i+1,k+ 1 ≤i≤n. (b)Cn+2np(0) = {αn+2np, βn+2np}, and in Cn+2np there are 2nmembranes labelled by 1, such that each of them contains nobjects #; and 2nmembranes labelled by 2, such that each of them contains the input multiset codn+2np(ϕ), an object γn+2np,pcopies of every Tiand Fi,1≤i≤nif the truth assignment associated to the branch contains its corresponding tior fiobject. Proof. (a) is going to be demonstrated by induction on k - the base case k= 1 is trivial because: - at C2np we have C2np(0) = {α2np, β2np}and there exist 2nempty membranes labelled by 1; and 2nmembranes labelled by 2 containing the input multiset cod2np(ϕ), an object γ2np pcopies of Ti(resp. Fi) being 1 ≤i≤nif 274 L. Valencia-Cabrera et al. the corresponding ti(resp. fi) object exists in that branch, and 1 copy otherwise and a different multiset of objects ri,2np−i+1, 1 ≤i≤n, being r∈ {t, f}, that is, the truth assignment associated with the branch. Then, configuration C2np yields C2np+1 by applying the rules. [t1,2np F1]2→#[ ]2 [f1,2np T1]2→#[ ]2 [ti,2np−i+1 →ti,2np−i+2 ]2 [fi,2np−i+1 →fi,2np−i+2 ]2for 2 ≤i≤n [α2np →α2np+1 ]0 [β2np →β2np+1 ]0 [γ2np →γ2np+1 ]2 [xi,j,2np →xi,j,2np+1 ]2 [xi,j,2np →xi,j,2np+1 ]2 [x∗ i,j,2np →x∗ i,j,2np+1 ]2   for 1 ≤i≤n, 1≤j≤p Thus, C2np+1(0) = {α2np+1, β2np+1}, and there exist 2nmembranes labelled by 1 containing an object #; and 2nmembranes labelled by 2 containing the input multiset cod2np+1(ϕ), an object γ2np+1,pcopies of Ti(resp. Fi) being 1 ≤i≤nif their corresponding ti(resp. fi) object exists in that branch, and 1 copy of Fi(resp. Ti) if k+ 2 ≤i≤nand objects ri,2np−i+2, k+ 2 ≤i≤n, being r∈ {t, f}. - Supposing, by induction, result is true for k(1 ≤k≤n−1) -C2np+k(0) = {α2np+k, β2np+k} - In C2np+kthere are 2nmembranes labelled by 1 such that each of them contains kobjects #. - In C2np+kthere are 2nmembranes labelled by 2 such that each of them contains ?the input multiset cod2np+k(ϕ); ?an object γ2np+k; ? p copies of Ti(resp. Fi) being 1 ≤i≤nif their corresponding ti (resp. fi) object exists in that branch, and 1 copy of Fi(resp. Ti) if k+ 1 ≤i≤n; and ?objects ri,2np+k−i+1,k+ 1 ≤i≤n, being r∈ {t, f}. Then, configuration C2np+kyields configuration C2np+k+1 by applying the rules: [tk+1,2np F1]2→#[ ]2 [fk+1,2np T1]2→#[ ]2 [ti,2np+k−i+1 →ti,2np+k−i+2 ]2 [fi,2np+k−i+1 →fi,2np+k−i+2 ]2for 2 ≤i≤n [α2np+k→α2np+k+1 ]0 [β2np+k→β2np+k+1 ]0 [γ2np+k→γ2np+k+1 ]2 [xi,j,2np+k→xi,j,2np+k+1 ]2 [xi,j,2np+k→xi,j,2np+k+1 ]2 [x∗ i,j,2np+k→x∗ i,j,2np+k+1 ]2   for 1 ≤i≤n, 1≤j≤p P Systems with Active Membranes: Minimal Cooperation Only Outwards 275 Therefore, the following holds -C2np+k+1(0) = {α2np+k+1, β2np+k+1} - In C2np+k+1 there are 2nmembranes labelled by 1 such that each of them contains k+ 1 objects #. - In C2np+k+1 there are 2nmembranes labelled by 2 such that each of them contains ?the input multiset cod2np+k+1(ϕ); ?an object γ2np+k+1; ? p copies of Ti(resp. Fi) being 1 ≤i≤nif their corresponding ti (resp. fi) object exists in that branch, and 1 copy of Fi(resp. Ti) if k+ 2 ≤i≤n; and ?objects ri,2np+k−i+2,k+ 2 ≤i≤n, being r∈ {t, f}. - In order to prove (b) it is enough to notice that, on the one hand, from (a) configuration Cn+2np−13holds: -Cn+2np−1(0) = {αn+2np−1, βn+2np−1} - In Cn+2np−1there are 2nmembranes labelled by 1 such that each of them contains n−1 objects #. - In Cn+2np−1there are 2nmembranes labelled by 2 such that each of them contains ?the input multiset codn+2np−1(ϕ); ?an object γn+2np−1; ? p copies of Ti(resp. Fi) being 1 ≤i≤nif the corresponding ti(resp. fi) object exists in that branch, and 1 copy of Fn(resp. Tn); and ?an object rn,2np, being r∈ {t, f}. Then, configuration Cn+2np−1yields configuration Cn+2np by applying the rules: [tn,2np F1]2→#[ ]2 [fn,2np T1]2→#[ ]2 [αn+2np−1→αn+2np ]0 [βn+2np−1→βn+2np ]0 [γn+2np−1→γn+2np ]2 [xi,j,n+2np−1→xi,j,n+2np ]2 [xi,j,n+2np−1→xi,j,n+2np ]2 [x∗ i,j,n+2np−1→x∗ i,j,n+2np ]2   for 1 ≤i≤n, 1≤j≤p Therefore, the following holds -Cn+2np(0) = {αn+2np, βn+2np} - In Cn+2np there are 2nmembranes labelled by 1 such that each of them contains nobjects #. - In Cn+2np there are 2nmembranes labelled by 2 such that each of them contains ?the input multiset codn+2np(ϕ); ?an object γn+2np; and 3Note that n+ 2np −1 = 2np + (n−1) 276 L. Valencia-Cabrera et al. ? p copies of Ti(resp. Fi) being 1 ≤i≤nif their corresponding ti(resp. fi) object exists in that branch.  5.2 First checking stage At this stage, we try to determine the clauses satisfied for the truth assignment encoded by each branch. For that, rules from 5.5 will be applied in such manner that in the m-th step, being m=ln+k(1 ≤k≤n, 0 ≤l≤p−1), clause Cl+1 will be evaluated with the k-th variable of the formula. This stage will take exactly np 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≤n) and l(0≤l≤p−1) at configuration Cn+2np+ln+kwe have the following: -Cn+2np+ln+k(0) ={αn+2np+ln+k, βn+2np+ln+k} - There are 2nmembranes labelled by 1 such that each of them contains ? m objects cj,t (1≤j≤l+ 1,0≤t≤ln +k−1), that is, clauses that have been satisfied by any variable; and ? n +ln +k−mobjects #. - There are 2nmembranes labelled by 2 such that each of them contains ?the (n−k)-th last elements of codn+2np+ln+k(ϕ)l+1 l+1; ?the input multiset codn+2np+ln+k(ϕ)p l+2; ?an object γn+2np+ln+k; and ? p−lcopies of objects Tior Fi,k+1 ≤i≤n,p−l−1copies otherwise, corresponding to the truth assignment assigned to the branch. (b)Cn+3np(0) = {αn+3np, βn+3np}, and in Cn+3np there are 2nmembranes labelled by 1, such that each of them contains mobjects cj,t (1≤j≤p,0≤t≤np−1), that is, the clauses satisfied by any variable and n+np −mobjects #; and 2n membranes labelled by 2 such that each of them contains an object γn+3np. Proof. (a) is going to be demonstrated by induction on l - The base case l= 0 is goig to be demonstrated by induction on k - The base case k= 1 is trivial because: - at configuration Cn+2np we have: Cn+2np(0) = {αn+2np, βn+2np}and there exist 2nmembranes labelled by 1, such that each of them contains; and 2nmembranes labelled by 2 such that each of them contains nobjects # the input multiset codn+2np(ϕ), an object γn+2np and p copies of objects Tiand Fi, 1 ≤i≤n, representing the correspondent truth assignment to the branch. Then, configuration Cn+2np yields configuration Cn+2np+1 by applying the rules: P Systems with Active Membranes: Minimal Cooperation Only Outwards 277 [T1x1,1,n+2np ]2−→ c1,0[ ]2 [T1x1,1,n+2np ]2−→ #[ ]2 [T1x∗ 1,1,n+2np ]2−→ #[ ]2 [F1x1,1,n+2np ]2−→ #[ ]2 [F1x1,1,n+2np ]2−→ c1,0[ ]2 [F1x∗ 1,1,n+2np ]2−→ #[ ]2 4 [αn+2np →αn+2np+1 ]0 [βn+2np →βn+2np+1 ]0 [γn+2np →γn+2np+1 ]2 [xi,j,n+2np →xi,j,n+2np+1 ]2 [xi,j,n+2np →xi,j,n+2np+1 ]2 [x∗ i,j,n+2np →x∗ i,j,n+2np+1 ]2   for 1 ≤i≤n, 1≤j≤p Thus, Cn+2np+1(0) = {αn+2np+1, βn+2np+1}, and there exist 2nmembranes labelled by 1 containing nobjects # and an object c1,0if the corresponding truth assignment makes true clause 1 with variable 1, another object # otherwise; and 2nmembranes labelled by 2 containing the last n−1 elements of codn+2np+1(ϕ)1 1, the input multiset codn+2np+1(ϕ)p 2,pcopies of Tior Fi, being 2 ≤i≤n, and p−1 copies of T1or F1. - Supposing, by induction, result is true for k(1 ≤k≤n) -Cn+2np+k(0) = {αn+2np+k, βn+2np+k} - In Cn+2np+kthere are 2nmembranes labelled by 1 such that each of them contains ? m objects c1,t (0 ≤t≤k−1), that is, the number of variables with the corresponding truth assignment that makes true the input formula ϕ; and ? n +k−mobjects #. - In Cn+2np+kthere are 2nmembranes labelled by 2 such that each of them contains ?the (n−k)-th last elements of codn+2np+k(ϕ)1 1; ?the input multiset codn+2np+k(ϕ)p 2; ?an object γn+2np+k; and ? p copies of objects Tior Fi,k+ 1 ≤i≤n,p−1 copies if 1 ≤i≤k, corresponding to the truth assignment assigned to the branch. Then, configuration Cn+2np+kyields configuration Cn+2np+k+1 by applying the rules: [Tkx1,1,n+2np+k]2−→ c1,0[ ]2 [Tkx1,1,n+2np+k]2−→ #[ ]2 [Tkx∗ 1,1,n+2np+k]2−→ #[ ]2 [Fkx1,1,n+2np+k]2−→ #[ ]2 [Fkx1,1,n+2np+k]2−→ c1,0[ ]2 [Fkx∗ 1,1,n+2np+k]2−→ #[ ]2 5 4If k= 1, l = 0, then i= 1, j = 1, so 2np +n+n(j−1) + (i−1) = n+ 2np 5If l= 0, then i=k+ 1, j = 1, so 2np + 2n+n(j−1) + (i−1) = 2n+ 2np +k 284 L. Valencia-Cabrera et al. ?an object γn+4np or de j−1(respectively, an object dk) if the corresponding truth assignment does not make true (resp., makes true) the clause C1 or Cj(2≤j≤p) (resp., the first kclauses); and ? mj−1objects cjfor 1≤j≤min(e j, k + 1) and mjobjects cjfor min(e j, k + 2) ≤j≤p. (a1)For each 2k(1≤k≤p−2) at configuration Cn+4np+2kwe have the following: -Cn+4np+2k(0) = {αn+4np+2k, βn+4np+2k} - There are 2nempty membranes labelled by 1. - There are 2nempty membranes labelled by 2 such that each of them contains ?an object γn+4np or de j−1if the corresponding truth assignment does not make true the clause C1or Cj(2≤j≤p); and ? mj−1objects cjfor 1≤j≤min(e j, k)and mjobjects cjfor min(e j, k+ 1) ≤j≤p. (b)Cn+4np+2p−1(0) = {αn+4np+2p−1, βn+4np+2p−1}, and in Cn+4np+2p−1there are 2nmembranes labelled by 1, such that each of them contains an object dpif and only if the corresponding truth assignment makes true the input formula ϕ(de j−1otherwise); and 2nmembranes labelled by 2, such that each of them contains mj−1objects cjfor 1≤j≤min(e j, p+1),mjobjects cjfor min(e j, p+ 1) ≤j≤pand an object γn+4np (respectively, de j) if clause C1(resp., Cj) is not satisfied by the corresponding truth assignment. Proof. (a) is going to be demonstrated by induction on k - The base case k= 1 is trivial because: (a0) at configuration Cn+4np we have: Cn+4np(0) = {αn+4np, βn+4np}and there exist 2nempty membranes labelled by 1; and there exist 2nmembranes labelled by 2 containing an object γn+4np and mobjects cj(1 ≤j≤p). Then, configuration Cn+4np yields configuration Cn+4np+1 by applying the rules: [αn+4np →αn+4np+1 ]0 [βn+4np →βn+4np+1 ]0 [γ4np+2nc1]2−→ d1[ ]2 (a1) at Cn+4np+1(0) = {αn+4np+1, βn+4np+1}and there exist 2nmembranes labelled by 1 containing an object d1if and only if there was at least one object c1within membrane labelled by 1 at configuration Cn+4np; and 2n membranes labelled by 2 containing an object γn+4np if and only if there were no objects c1at configuration Cn+4np,m1−1 (respectively, m1) objects c1if there was any object cjin this membrane in the previous configuration (resp., m1) and mjobjects cjfor 2 ≤j≤p. Then, the configuration Cn+4np+1 yields configuration Cn+4np+2 by applying the rules: [αn+4np+1 →αn+4np+2 ]0 [βn+4np+1 →βn+4np+2 ]0 d1[ ]2−→ [d1]2 Thus, Cn+4np+2(0) = {αn+4np+2, βn+4np+2}, and there exist 2nempty membranes labelled by 1; and there exist 2nmembranes labelled by 2 P Systems with Active Membranes: Minimal Cooperation Only Outwards 285 containing an object d1(respectively, γn+4np) if the corresponding truth assignment makes true (resp., doesn’t make true) clause C1,m1−1 (resp., m1) objects c1and mjobjects cjfor 1 ≤j≤p. Hence, the result holds for k= 1. - Supposing, by induction, result is true for k(0 ≤k≤p−1) -Cn+4np+2k(0) = {αn+4np+2k, βn+4np+2k} - In Cn+4np+2kthere are 2nempty membranes labelled by 1. - In Cn+4np+2kthere are 2nmembranes labelled by 2 such that each of them contains ?an object γn+4np or de j−1(respectively, an object dk) if the corresponding truth assignment does not make true (resp., makes true) the clause C1 or Cj(2 ≤j≤p) (resp., the first kclauses); and ? mj−1 objects cjfor 1 ≤j≤min(e j, k + 1) and mjobjects cjfor min(e j, k + 2) ≤j≤p. Then, configuration Cn+4np+2kyields configuration Cn+4np+2k+1 by applying the rules: [αn+4np+2k→αn+4np+2k+1 ]0 [βn+4np+2k→βn+4np+2k+1 ]0 [dkck+1 ]2−→ dk+1[ ]2 Therefore, the following holds -Cn+4np+2k+1(0) = {αn+4np+2k+1, βn+4np+2k+1} - In Cn+4np+2k+1 there are 2nmembranes labelled by 1 such that each of them contains an object dk+1 if and only if the corresponding truth assignment makes true the first k+ 1 clauses. - In Cn+4np+2k+1 there are 2nmembranes labelled by 2 such that each of them contains ?an object γn+4np or de j−1if the corresponding truth assignment does not make true the clause C1or Cj(2 ≤j≤p); and ? mj−1 objects cjfor 1 ≤j≤min(e j, k) and mjobjects cjfor min(e j, k + 1) ≤j≤p. Then, configuration Cn+4np+2k+1 yields Cn+4np+2k+2 by applying the rules: [αn+4np+2k+1 →αn+4np+2k+2 ]0 [βn+4np+2k+1 →βn+4np+2k+2 ]0 dk+1[ ]2−→ [dk+1 ]2 Therefore, the following holds -Cn+4np+2k+2(0) = {αn+4np+2k+2, βn+4np+2k+2} - In Cn+4np+2k+2 there are 2nempty membranes labelled by 1. - In Cn+4np+2k+2 there are 2nmembranes labelled by 2 such that each of them contains ?an object γn+4np or de j−1(respectively, an object dk+1) if the corresponding truth assignment does not make true (resp., makes true) the clause C1or Cj(2 ≤j≤p) (resp., the first k+ 1 clauses); and 286 L. Valencia-Cabrera et al. ? mj−1 objects cjfor 1 ≤j≤min(e j, k + 2) and mjobjects cjfor min(e j, k + 3) ≤j≤p. Hence, the result holds for k+ 1. - In order to prove (b) it is enough to notice that, on the one han, from (a) configuration Cn+4np+2p−2holds: -Cn+4np+2p−2(0) = {αn+4np+2p−2, βn+4np+2p−2} - In Cn+4np+2p−2there are 2nempty membranes labelled by 1. - In Cn+4np+2p−2there are 2nmembranes labelled by 2 such that each of them contains - an object γn+4np or de j−1(respectively, dp−1) if the corresponding truth assignment does not make true the clause C1or Cj(2 ≤j≤p−1) (resp., makes true clauses Cj(1 ≤j≤p−1)); and -mj−1 objects cjfor 1 ≤j≤min(e j, p −1) and mjobjects cjfor min(e j, p)≤j≤p Then, configuration Cn+4np+2p−2yields configuration Cn+4np+2p−1by applying the rules: [αn+4np+2p−2→αn+4np+2p−1]0 [βn+4np+2p−2→βn+4np+2p−1]0 [dp−1cp]2−→ dp[ ]2 Then, we have Cn+4np+2p−1(0) = {αn+4np+2p−1, βn+4np+2p−1}, and in Cn+4np+2p−1there are 2nmembranes labelled by 1, such that each of them contains an object dpif and only if the corresponding truth assignment makes true the input formula ϕ(de j−1otherwise); and 2nmembranes labelled by 2, such that each of them contains mj−1 objects cjfor 1≤j≤min(e j, p + 1), mjobjects cjfor min(e j, p + 1) ≤j≤pand an object γn+4np (respectively, de j) if clause C1(resp., Cj) is not satisfied by the corresponding truth assignment.  5.4 Output stage The output phase starts at configuration Cn+4np+2p−1, and takes exactly two steps when there is an affirmative answer and three steps when there is a negative one. Rules from 5.7 are devoted to compute this stage. -Affirmative answer: In this case, at configuration Cn+4np+2p−1, in some membrane 1 there is an object dp. By applying the rule [ dp]1−→ dp[ ]1(at the same time that [ αn+4np+2p−1→αn+4np+2p]0and [ βn+4np+2p−1→ βn+4np+2p]0are executed), an object dpis produced in membrane 0. Then by applying the rules [ α4np+n+2pdp]0−→ yes[ ]0and [ βn+4np+2p→ βn+4np+2p+1 ]0, an object yes is released to environment and the computation halts. P Systems with Active Membranes: Minimal Cooperation Only Outwards 287 -Negative answer: In this case, at configuration Cn+4np+2p−1, there are no membranes labelled by 1 that contains an object dp, so the only rules executed are [ αn+4np+2p−1→αn+4np+2p]0and [ βn+4np+2p−1→βn+4np+2p]0. Rule [βn+4np+2p→βn+4np+2p+1 ]0is executed in the next step. Thus, at configuration Cn+4np+2p+1 in membrane labelled by 0 we execute have a copy of object αn+4np+2pand a copy of object βn+4np+2p+1. By applying the rule [α4np+n+2pβ4np+n+2p+1]0−→ no[ ]0an object no is released to the environment and then the computation halts. 5.5 Result Theorem 1. SAT ∈PMCDAM0(+es,mcmpout,−d,+n). Proof. The family Πof P systems previously constructed verifies the following: (a) The family Πis polynomially uniform by Turing machines because for each n, p ∈N, the rules of Π(hn, pi) of the family are recursively defined from n, p ∈N, and the amount of resources needed to build an element of the family is of a polynomial order in nand p, as shown below: – Size of the alphabet: 15n2p2 2+3n2p+3n2+np2+35np 2+5n+6p+6 ∈Θ(n2p2). – Initial number of membranes: 3 ∈Θ(1). – Initial number of objects in membranes: 3np +n+ 3 ∈Θ(np). – Number of rules: 15n2p2 2+ 7n2p+np2+33np 2+ 4n+ 6p+ 4 ∈Θ(n2p2). – Maximal number of objects involved in any rule: 3 ∈Θ(1). (b) The family Πis polynomially bounded with regard to (SAT,cod, s): indeed for each instance ϕof the SAT problem, any computation of the system Π(s(ϕ)) with input multiset cod(ϕ) takes at most 2n+ 4np + 2p+5 computation steps. (e) The family Πis sound with regard to (SAT,cod, s): indeed for each instance ϕof the SAT problem, if the computation of Π(s(ϕ)) + cod(ϕ) is an accepting computation, then ϕis satisfiable. (f) The family Πis complete with regard to (SAT,cod, s): indeed, for each instance ϕof the SAT problem such that ϕis satisfiable, any computation of Π(s(ϕ)) + cod(ϕ) is an accepting computation. Therefore, the family Πof P systems previously constructed solves the SAT problem in polynomial time and in a uniform way. Corollary 1. NP ∪co −NP ⊆PMCDAM0(+es,mcmpout,−d,+n). Proof. It suffices to notice that SAT problem is a NP-complete problem, SAT ∈PMCDAM0(+es,mcmpout,−d,+n), and the complexity class PMCDAM0(+es,mcmpout,−d,+n)is closed under polynomial-time reduction and under complement. 288 L. Valencia-Cabrera et al. 6 Conclusions From a computational complexity point of view and assuming that P6=NP, dissolution rules play a crucial role in classical polarizationless P systems with active membranes where there is no cooperation, no changing labels neither priorities. In that framework, PSPACE-complete problems can be solved in polynomial time when dissolution rules and division for elementary and non-elementary membranes are permitted. However, dissolution rules and division rules for non-elementary membranes can be replaced by minimal cooperation (the left-hand side of the rules has at most two objects) and minimal production (the right-hand side of the rules has at most two objects) in object evolution rules in order to obtain the computational efficiency [11]. In this paper, the ingredient of minimal cooperation and minimal production in object evolution rules is replaced by minimal cooperation and minimal production in send-out communication rules but we have need to use division for non-elementary membranes. The new systems considered are able to efficiently solve computational hard problems even by considering simple object evolution rules, that is, these kind of rules only produce one object. An analogous result can be obtained if minimal cooperation and minimal production are considered only for send-in rules, instead of send-out rules ([12]). The case where only elementary division is allowed, while keeping the restriction that minimal cooperation and minimal production are used in communication rules of the same direction (only out or only in) remains as future work, as well as the case where division rules are replaced by separation rules. What about the class SAM0(+es, mcmpout,−d, +n)? That is, what happens if we revisit the framework studied in this paper but replacing division rules by separation rules? We can adapt the reasoning used in the proof of P=PMCSAM0 bmc(−d,−n)(see [10]), and we can prove that by using families of recognizer membrane systems belonging to this class, only problems in class P can be solved in polynomial time. 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 Informaticae,41, 2-3 (2004), 111-144. P Systems with Active Membranes: Minimal Cooperation Only Outwards 289 3. T.H. Cormen, C.E. Leiserson, R.L. Rivest. An Introduction to Algorithms. The MIT Press, Cambridge, Massachusetts, 1994. 4. M.R. Garey, D.S. Johnson. Computers and Intractability A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, 1979. 5. M.A. Guti´errez–Naranjo, M.J. P´erez–Jim´enez, A. Riscos–N´u˜nez, F.J. Romero– Campero. On the power of dissolution in P systems with active membranes. In R. Freund, Gh. P˘aun, Gr. Rozenberg, A. Salomaa (eds.). Membrane Computing, 6th International Workshop, WMC 2005, Vienna, Austria, July 18-21, 2005, Revised Selected and Invited Papers, Lecture Notes in Computer Science,3850 (2006), 224– 240. 6. Gh. P˘aun. P systems with active membranes: Attacking NP–complete problems, Journal of Automata, Languages and Combinatorics,6(2001), 75–90. A preliminary version in Centre for Discrete Mathematics and Theoretical Computer Science Research Reports Series, CDMTCS-102, May 1999. 7. M.J. P´erez-Jim´enez, A. Romero-Jim´enez, F. Sancho-Caparrini. Complexity classes in models of cellular computing with membranes. Natural Computing,2, 3 (2003), 265–285. 8. P. Sos´ık, A. Rodr´ıguez-Pat´on. Membrane computing and complexity theory: A characterization of PSPACE. Journal of Computer and System Sciences,73 (2007), 137152. 9. L. Valencia-Cabrera, D. Orellana-Mart´ın, M.A. Mart´ınez-del-Amor, A. Riscos-N´u˜nez, M.J. P´erez-Jim´enez. Polarizationless P systems with active membranes: Computational complexity aspects. Journal of Automata, Languages and Combinatorics,21, 1-2 (2016), 107123 10. L. Valencia-Cabrera, D. Orellana-Mart´ın, A. Riscos-N´u˜nez, M.J. P´erez-Jim´enez. Minimal cooperation in polarizationless P systems with active membranes. In C. Graciani, Gh. P˘aun, D. Orellana-Martn, A. Riscos-Nez, L. Valencia-Cabrera (eds.) Proceedings of the Fourteenth Brainstorming Week on Membrane Computing, 1-5 February, 2016, Sevilla, Spain, F´enix Editora, pp. 327-356. 11. L. Valencia-Cabrera, D. Orellana-Mart´ın, M.A. Mart´ınez-del-Amor, A. Riscos-N´u˜nez, M.J. P´erez-Jim´enez. Reaching efficiency through collaboration in membrane systems: dissolution, polarization and cooperation. Theoretical Computer Science, in press, 2017. 12. L. Valencia-Cabrera, D. Orellana-Mart´ın, M.A. Mart´ınez-del-Amor, A. Riscos-N´u˜nez, M.J. P´erez-Jim´enez. Restricted polarizationless P systems with active membranes: minimal cooperation only inwards. In this volume, 2017 (manuscript). 13. C. Zandron, C. Ferretti, G. Mauri. Solving NP-complete problems using P systems. In I. Antoniou, C.S. Calude, M.J. Dinneen (eds.) Unconventional Models of Computation, UMC’2K, Springer, London, 2000, pp. 153-164.