On the efficiency of cell-like and tissue-like recognizing membrane systems

On the Efficiency of Cell-Like and Tissue-Like Recognizing Membrane Systems Miguel A. Guti´errez-Naranjo, Mario J. P´erez-Jim´enez, Agust´ın Riscos-N´u˜nez, Francisco J. Romero-Campero Research Group on Natural Computing, Department of Computer Science and Artificial Intelligence, ETS Ingenier´ıa Inform´atica, University of Sevilla, Avda. Reina Mercedes s/n, Sevilla, Spain Cell-like recognizing membrane systems are computational devices in the framework of membrane computing inspired from the structure of living cells, where biological membranes are arranged hierarchically. In this paper tissue-like recognizing membrane systems are presented. The idea is to consider that membranes are placed in the nodes of a graph, mimicking the cell intercommunication in tissues. In this context, polynomial complexity classes associated with recognizing membrane systems can be defined. We recall the definition for cell-like systems, and we introduce the corresponding complexity classes for the tissue-like case. Moreover, in this paper two efficient solutions to the satisfiability problem are analyzed and compared from a complexity point of view. 1. INTRODUCTION Membrane computing is a young branch of natural computing providing distributed parallel computational devices called membrane systems, which are inspired from some basic biological features of living cells, as well as from the cooperation of cells in tissues, organs, and organisms. In this area, there are basically two ways to consider computational devices: celllike membrane systems and tissue-like membrane systems. The first one uses membranes arranged hierarchically, inspired from the structure of the cell, and the second one uses membranes placed in the nodes of a graph, inspired from the cell intercommunication in tissues. In the past years, several computing models using powerful tools from nature have been developed (because of this, they are known as bioinspired models) and several solutions in polynomial time to NP-complete problems have been presented, making use of nondeterminism and/or of an exponential amount of space. This is the reason why a practical implementation of such models (in biological, electronic, or other media) could provide a significant advance in the resolution of computationally hard problems. In this paper, we present recognizing membrane systems (both cell-like and tissue-like variants) as a framework to address ways to efficiently solve computationally hard problems, capturing the true concept of algorithm instead of providing a (classical) nondeterministic solution. Also, we present a solution to the satisfiability problem in both variants. The paper is structured as follows. First, in Section 2, cell-like recognizing membrane systems are defined, together with the complexity classes associated with them. In this context, Section 3 discusses the Pversus NP problem, and Section 4 shows how membrane division rules in the active membranes model allow for polynomial-time solutions to NP-complete problems. We conclude the cell-like approach by solving the satisfiability problem in a linear time, using polarizationless active membranes. Then, in Section 5 we introduce polarizationless tissue-like recognizing membrane systems with active membranes (adapting the general definition of recognizing systems), and we also introduce the corresponding complexity classes (analogously as for the cell-like case). We also present a quadratic solution to the satisfiability problem in this framework. Finally, conclusions are presented in the last section. 2. CELL-LIKE RECOGNIZING MEMBRANE SYSTEMS In the structure and functioning of a cell, biological membranes play an essential role. The cell is separated from its environment by means of a skin membrane, and it is internally compartmentalized by means of internal membranes. The main syntactic components of a cell-like membrane system (also called P system, see Ref. 1 for details) are a membrane structure,multisets, and evolution rules.Amembrane structure consists of several membranes arranged in a hierarchical structure inside a main membrane (the skin), and delimiting regions (the space in-between a membrane and the immediately inner membranes, if any). Each membrane identifies a region inside the system. A membrane structure can be considered as a rooted tree. Regions defined by a membrane structure contain objects corresponding to chemical substances present in the compartments of a cell. The objects can be described by symbols or by strings of symbols, in such a way that multiset of objects are placed in regions of the membrane structure. The objects can evolve according to given evolution rules, associated with the regions (hence, with the membranes). The semantics of the cell-like membrane systems is defined through a nondeterministic and synchronous model (in the sense that a global clock is assumed) as follows: A configuration of a cell-like membrane system consists of a membrane structure and a family of multisets of objects associated with each region of the structure. At the beginning, there is a configuration called the initial configuration of the system. In each time unit, we can transform a given configuration in another configuration by applying the evolution rules to the objects placed inside the regions of the configurations, in a nondeterministic and maximally parallel manner (the rules are chosen in a nondeterministic way, and in each region all objects that can evolve must do it). In this way, we get transitions from one configuration of the system to the next one. A computation of the system is a (finite or infinite) sequence of configurations such that each one is obtained from the previous one by a transition, and shows how the system is evolving. A computation that reaches a configuration where no more rules can be applied to the existing objects is called a halting computation. The result of a halting computation is usually defined through the multiset associated with a specific output membrane (or the environment) in the final configuration. In the basic definition, cell-like membrane systems can be seen as generative devices, working in a nondeterministic and maximally parallel manner, with output membrane, and without input membrane. However, as we are interested in using celllike membrane systems for solving decision problems, we can adapt the definition as follows: DEFINITION 2.1. A cell-like membrane system with external output is said to be a recognizing system if: (a) The working alphabet contains two distinguished elements yes and no; (b) all computations halt, and if Cis a computation of the system, then either some object yes or some object no (but not both) must have been released into the environment in the last step of the computation. A computation of a recognizing system is said to be an accepting computation (respectively, rejecting computation) if the object yes (respectively, no) appears in the environment associated with the corresponding halting configuration. We want these kinds of systems (which are nondeterministic devices) to properly solved decision problems according to the true algorithmic concept. With this aim, instead of using classical nondeterministic acceptance (it is enough that one computation gives an affirmative answer), it is necessary to require a condition of confluence; that is, the system processing an instance of the problem must always give the same answer in all computations. This idea leads us to the concepts of soundness and completeness. 2.1. Soundness and Completeness A family of cell-like recognizing P systems will provide a solution to a decision problem if for each instance of the problem: (a) if there exists an accepting computation of the membrane system processing it, then the instance of the problem has an affirmative answer (soundness); and (b) if the instance of the problem has an affirmative answer, then any computation of the system processing that instance is an accepting computation (completeness). Next, we formalize these ideas in the following definition: DEFINITION 2.2. Let X=(IX,θ X)be a decision problem. Let =((w))w∈IXbe a family of recognizing membrane systems without input. •The family is sound with regard to Xif for each instance w∈IXsuch that there exists an accepting computation of (w), we have θX(w)=1. •The family is complete with regard to Xif for each instance w∈IXsuch that θX(w)=1, we have every computation of (w)is an accepting computation. These concepts can be extended to families of cell-like recognizing membranes with input membrane in a natural way, but in this case a P system belonging to the family can process several instances of the problem, provided that an appropriate input is supplied to the system. DEFINITION 2.3. AP system with input is a tuple (, , i), where. (a) is a P system with working alphabet , with pmembranes labeled by 1,...,p, and initial multisets M1,...,Mpassociated with them; (b) is an (input) alphabet strictly contained in , and the initial multisets are over −; and (c) iis the label of a distinguished (input) membrane. If mis a multiset over , then the initial configuration of (, , i)with input mis (μ, M1,...,Mi∪m,...,Mp). DEFINITION 2.4. Let X=(IX,θ X)be a decision problem. Let =((n))n∈Nbe a family of cell-like recognizing P systems with input.Apolynomial encoding of Xin is a pair (cod, s)of polynomial time computable functions over IXsuch that for each instance w∈IX,s(w)is a natural number and cod(w)is an input multiset of the system (s(w)). DEFINITION 2.5. Let X=(IX,θ X)be a decision problem. Let =((n))n∈Nbe a family of cell-like recognizing membrane systems with input.Let(cod, s)be a polynomial encoding of Xin . •The family is sound with regard to (X, cod, s)if for each instance w∈IXsuch that there exists an accepting computation of (s(w)) with input cod(w), we have θX(w)=1. •The family is complete with regard to (X, cod, s)if for each instance w∈IXsuch that θX(w)=1, we have every computation of (s(w)) with input cod(w)is an accepting computation. Next, we consider different complexity classes in the framework of cell-like recognizing membrane systems. 2.2. Polynomial Semiuniform Solutions The first results about solvability of NP-complete problems in polynomial time by membrane systems were given by P˘ aun,2Zandron et al.,3Krishna and Rama,4and Obtulowicz,5in the framework of membrane systems that lack an input membrane. Thus, the constructive proofs of such results design one system for each instance of the problem. In this context, let us define polynomial complexity classes in cell-like recognizing P systems without input. To solve a decision problem we need, then, to associate with each instance of the problem a system which decides the instance. DEFINITION 2.6. Let Rbe a class of cell-like recognizing P systems without input membrane. A decision problem X=(IX,θ X)is solvable in polynomial time by a family =((w))w∈IX, of P systems of R, and we denote it by X∈PMC∗ R, if the following holds: •The family is polynomially uniform by Turing machines; that is, there exists a deterministic Turing machine working in polynomial time which constructs the system (w) from the instance w∈IX. •The family is polynomially bounded; that is, there exists a polynomial function p(n) such that for each w∈IX, every computation of (w)halt in, at most, p(|w|)steps. •The family is sound and complete with regard to X. We say that the family is a semiuniform solution to the problem X. As a direct consequence of working with recognizing membrane systems we have these complexity classes are closed under complement. Moreover, they are closed under polynomial time reduction. 2.3. Polynomial Uniform Solutions Next, we deal with cell-like recognizing P systems with input membrane and we propose to solve problems in an uniform way in the following sense: All instances of a decision problem that have the same size (according to a prefixed polynomial time computable criterion) are processed by the same system, on which an appropriate input is supplied. Let us formalize these ideas in the following definition: DEFINITION 2.7. A decision problem X=(IX,θ X)is solvable in polynomial time by a family of cell-like recognizing P systems with input =((n))n∈N, and we denote it by X∈PMCR, if the following holds: •The family is polynomially uniform by Turing machines; that is, there exists a deterministic Turing machine that constructs in polynomial time the system (n)from n∈N. •There exists a polynomial encoding (cod, s)of Xin such that –The family is polynomially bounded with regard to (X, cod, s); that is, there exists a polynomial function p(n)such that for each w∈IX, every computation of the system (s(w)) with input cod(w)is halting and, moreover, it performs at most p(|w|)steps. –The family is sound and complete with regard (X, cod, s). These complexity classes are closed under complement. Moreover, they are closed under polynomial time reduction. 3. P VERSUS NP PROBLEM IN THE CONTEXT OF CELL-LIKE RECOGNIZING MEMBRANE SYSTEMS We consider deterministic Turing machines as language recognizing devices. Then, we can associate with each deterministic Turing machine a decision problem, which will allow us to define when such a machine is simulated by a family of P systems (this issue was also addressed, e.g., in Refs. 6 and 7). DEFINITION 3.1. Let Mbe a Turing machine with input alphabet M.Thedecision problem associated with Mis the problem XM=(I,θ), where I=∗ M, and for every w∈∗ M,θ(w)=1if and only if Maccepts w. Obviously, the decision problem XMis solvable by the Turing machine M. DEFINITION 3.2. We say that a Turing machine, M, is simulated in polynomial time by a family of cell-like recognizing P systems of the class R,ifXM∈PMCR. In cell-like membrane systems, evolution rules, communication rules, and rules involving dissolution are called basic rules. Note that by applying this kind of rules the size of the membrane structure does not increase. Hence, it is not possible to construct an exponential number of membranes in polynomial time using only basic rules in a cell-like membrane system. We recall here a result from Chapter 9 of Ref. 8. PROPOSITION 3.1. Let Mbe a deterministic Turing machine working in polynomial time. Then Mcan be simulated in polynomial time by a family of cell-like recognizing P systems using only basic rules. Reciprocally, in Ref. 7 the following result was proved: PROPOSITION 3.2. For every decision problem solvable in polynomial time by a family of cell-like recognizing P systems using only basic rules, there exists a Turing machine solving it in polynomial time. Under the hypothesis P= NP, Zandron et al.3established the limitations of cell-like membrane systems, which use only basic rules concerning the efficient solution to NP-complete problems. This result was generalized by P´ erez-Jim´ enez et al.7obtaining the following two characterizations of the P= NP relation by means of unsolvability results in polynomial time for NP-complete problems by families of cell-like recognizing membrane systems using only basic rules. THEOREM 3.1. The following assertions are equivalent: 1. P= NP. 2. There exists an NP-complete decision problem unsolvable in polynomial time by a family cell-like recognizing membrane systems using only basic rules. 3. Each NP-complete decision problem is unsolvable in polynomial time by a family of cell-like recognizing membrane systems using only basic rules. Let us denote by RB the class of cell-like recognizing membrane systems using only basic rules. In Ref. 9 the complexity class Phas been characterized in terms of cell-like recognizing P systems, by proving the following theorem. THEOREM 3.2. P=PMCRB. 4. RECOGNIZING CELL-LIKE P SYSTEMS WITH ACTIVE MEMBRANES A particularly interesting class of cell-like membrane systems is the systems with active membranes, where the membrane division can be used to solve computationally hard problems, e.g., NP-complete problems, in polynomial or even linear time, by a space-time trade-off. DEFINITION 4.1. A recognizing cell-like P system (, , i)is called with active membranes, if the rules of are of the following forms (being the working alphabet, and Hthe set of labels of ): (a) [ a→ω]α hfor h∈H,α∈{+,−,0},a∈,ω∈∗: An object awithin a membrane labeled with hand polarity αevolves to a multiset ω. (b) a[] α1 h→[b]α2 hfor h∈H,α1,α 2∈{+,−,0},a,b ∈: An object from the region immediately outside a membrane labeled with his introduced in this membrane, possibly transformed into another object, and simultaneously, the polarity of the membrane can be changed. (c) [ a]α1 h→b[] α2 hfor h∈H,α1,α 2∈{+,−,0},a,b ∈: An object is sent out from membrane labeled with hto the region immediately outside, possibly transformed into another object, and simultaneously, the polarity of the membrane can be changed. (d) [ a]α h→bfor h∈H,α∈{+,−,0},a,b ∈: A membrane labeled with his dissolved in reaction with an object. The skin is never dissolved. (e) [ a]α1 h→[b]α2 h[c]α3 hfor h∈H,α1,α 2,α 3∈{+,−,0},a,b,c ∈: A membrane can be divided into two membranes with the same label, possibly transforming some objects and their polarities. These rules are applied according to the following principles: •All the rules are applied in parallel and in a maximal manner. In one step, one object of a membrane can be used by only one rule (chosen in a nondeterministic way), but any object which can evolve by one rule of any form, must evolve. •If a membrane is dissolved, its content (multiset and internal membranes) is left free in the surrounding region. •If at the same time a membrane labeled by his divided by a rule of type (e) and there are objects in this membrane which evolve by means of rules of type (a), then we suppose that first the evolution rules of type (a) are used, and then the division is produced. Of course, this process takes only one step. •The rules associated with membranes labeled by hare used for all copies of this membrane. At one step, a membrane can be the subject of only one rule of types (b)–(e). Let us denote by AM the class of recognizing P systems with active membranes using 2-division. Different polynomial time solutions to NP-complete problems have been obtained using this class of cell-like recognizing membrane systems: Knapsack,10 SAT,11 Clique,12 and Bin Packing.13 Hence, the following proposition holds: PROPOSITION 4.1. NP ⊆PMCAM, and co-NP ⊆PMCAM. Moreover, Sos´ ık14 proved that PSPACE ⊆PMC∗ AM0(+d,+ne), where AM0(+d,+ne) is the class of recognizing P systems with active membranes allowing division for nonelementary membranes. Therefore, the complexity class PMCAM does not seem precise enough to describe classical complexity classes below NP. Consequently, it is challenging to investigate weaker models of cell-like membrane systems able to characterize classical complexity classes. Following this line, several efficient solutions to NP-complete problems have been obtained within the following variants of cell-like P systems with active membranes: •P systems with active membranes but using only two electrical charges (Alhazov,15 Riscos16; •P systems with active membranes without polarizations, but using bistable catalysts (P´ erez and Romero17); •P systems without polarizations, without cooperation, without priorities, without label changing, without division, but using three types of membrane rules: separation, merging, and release (Pan et al.18); •P systems with separation rules instead of division rules, in two different cases: in the first, using polarizations and separation rules; and in the second one, without polarizations but using separation rules that can change membrane labels (Pan and Ishdorj19). We can define polarizationless cell-like P systems with active membranes in a similar manner by removing electrical charges, that is, considering only rules of the following types: (a) [ a→u]hfor h∈H,a∈,u∈∗. (b) a[] h→[b]hfor h∈H,a,b ∈. (c) [ a]h→b[] hfor h∈H,a,b ∈. (d) [ a]h→bfor h∈H,a, b ∈. (e) [ a]h→[b]h[c]hfor h∈H,a, b,c ∈. We denote by AM0the class of polarizationless cell-like recognizing P systems with active membranes. At the beginning of 2005, P˘ aun (problem Ffrom Ref. 20) wrote: “My favorite question (related to complexity aspects in P systems with active membranes and with electrical charges) is that about the number of polarizations. Can the polarizations be completely avoided? The feeling is that this is not possible—and such a result would be rather sound: passing from no polarization to two polarizations amounts to passing from non-efficiency to efficiency.” That is, formally we can formulate the so-called P˘ aun’s conjecture as follows: “The class of decision problems solvable in polynomial time by families of cell-like recognizing P systems belonging to AM0is the standard complexity class P.” We denote by AM0(α, β), where α∈{−d,+d}and β∈{−ne, +ne}, the class of all polarizationless cell-like recognizing P systems with active membranes such that (a) if α=+d(resp. α=−d) then dissolution rules are permitted (resp. forbidden); and (b) if β=+ne (resp. β=−ne) then division rules for elementary and non-elementary (resp. only division rules for elementary) membranes are permitted. In the framework of polarizationless cell-like recognizing P systems with active membranes, it turns out that dissolution rules play a surprising role, as they make the difference between efficiency and nonefficiency. More precisely, the following result is presented in Ref. 21: THEOREM 4.1. We have the following: (1) P=PMCAM0(−d,β)=PMC∗ AM0(−d,β), for each β∈{−ne, +ne}. (2) NP ∪co −NP ⊆PMC∗ AM0(+d,+ne). That is, P˘ aun’s conjecture has a negative answer if dissolution rules are allowed (assuming that P= NP), and an affirmative answer otherwise. The inclusion shown in (2) was improved in Ref. 22, where PSPACE ⊆ PMCAM0(+d,+ne)is proved. The inclusion relations between complexity classes can be summarized graphically in Figure 1. 4.1. Solving the SAT Problem by Using Polarizationless Cell-Like P Systems with Active Membranes The first efficient semiuniform solution to SAT (satisfiability problem) was given by P˘ aun,2using division for nonelementary membranes. This result was improved by P˘ aun et al. in Ref. 23 using only division for elementary membranes (in that paper a semiuniform solution to the Hamiltonian path problem using membrane creation is also presented). In this section, we present a semiuniform solution to the SAT problem in linear time by using polarizationless cell-like recognizing P systems with active membranes. THEOREM 4.2. The satisfiability of any propositional formula in the conjunctive normal form, using nvariables and mclauses, can be decided in a linear time with respect to nby a polarizationless cell-like recognizing P system with active membranes, constructed in linear time with respect to nand m. 5.1.1. An Overview of the Computations Membrane 2 is repeatedly divided, each time expanding one object ai, corresponding to a variable xi, into Ti,1and Fi,1, corresponding to the values true and false which this variable may assume. In this way, in nsteps, we get 2ncells with label 2, each one containing one of the 2npossible truth assignments for the nvariables. The objects f, g are duplicated, hence a copy of each of them will appear in each cell. In parallel with the operation of dividing cell 2, the counters bi,c i,d i,e ifrom cell 1 grow their subscripts. In each step, the number of copies of objects of the first three types is doubled, hence after nsteps we get 2ncopies of bn+1,c n+1, and dn+1. Objects biwill check which clauses are satisfied by a given truth assignment, objects ciare used to multiply the number of copies of ti,f ias we will see immediately, di are used to check whether there is at least one truth assignment which satisfies all clauses, and if such an assignment does not exist, then eiwill be used in order to produce the object no at the end of the computation. In step n+1, the counters bn+1,c n+1,d n+1are brought in cells with label 2, in exchange of fand g. Because we have 2ncopies of each object of these types and 2ncells 2, each one containing exactly one copy of fand one of g, due to the maximal parallel use of the rules, each cell 2 gets precisely one copy of each of bn+1,c n+1,d n+1. Note that cells 2 cannot divide anymore, because the objects ai were exhausted. In the presence of cn+1, the objects Ti,1,F i,1get primed, which initiates the possibility of introducing mcopies of each tiand fiin each cell 2. As we have m clauses, then to check their values for a given truth assignment, we need for each clause one set of objects encoding the values of all variables. Note that this phase needs 2nsteps for priming the objects Ti,1,F i,1—for each object we need one step, because we have only one copy of cn+1available—then mfurther steps for each T i,1,F i,1; all these steps are done in parallel, but for the last primed Ti,1,F i,1we have to continue msteps after the 2nnecessary for priming. Thus, the total number of steps performed in this process is 2n+m. In parallel with the previous operations, the counters biand diincrease their subscripts, until reaching the value 3n+m+1. This is done in all cells 2 at the same time. Simultaneously, eiincreases its subscript in cell 1. In the presence of b3n+m+1—and not before—we check the values assumed by clauses for the truth assignments from each cell 2. We have only one copy of b3n+m+1in each cell, hence we need at most nm steps for this: each clause contains at most nliterals, and we have mclauses. In parallel, dincreases the subscript, until reaching the value 3n+nm +m+1. In each cell with label 2 we check whether or not all clauses are satisfied by the corresponding truth assignment. For each clause which is satisfied, we increase by one the subscript of d, hence the subscript reaches the value 3n+nm +2m+1 if and only if all clauses are satisfied. If one of the truth assignments from a cell 2 has satisfied all clauses, then we reach d3n+nm+2m+1, which is sent to cell 1 in exchange of the objects yes and f. In the next step, the object yes leaves the system, signaling the fact that the formula is satisfiable. In cell 1, the counter ewill increase one more step its subscript, but after that it will remain unchanged—it can leave cell 1 only in the presence of f, but this object was already moved to cell 2. If the counter ereaches the subscript 3n+nm +2m+2 and the object fis still in cell 1, then the object no can be moved to a cell 2, randomly chosen, and from there it exits the system, signaling that the formula is not satisfiable. Next, we justify that the solution provided is an uniform solution. We consider the polynomial encoding (cod, s)ofISAT in , defined as follows: If the formula ϕis an instance of SAT with size parameters n(number of variables) and m(number of clauses), then s(ϕ)=n, mand cod(ϕ) is the set  1≤i≤n,1≤j≤m,1≤r≤kj {si,j |yj,r =xi}∪{s i,j |yj,r =¬xi,} That is, in the multiset cod(ϕ) we replace each variable xifrom each clause Cjwith si,j and each negated variable ¬xifrom each clause Cjwith s i,j , then we remove all parentheses and connectives. In this way we pass from ϕto cod(ϕ) in a number of steps which is linear with respect to n·m. The presented family of tissue-like recognizing membrane systems is polynomially uniform by Turing machines, because the definition of the family is done in a recursive manner from a given instance of SAT, in particular from the constants n (number of variables) and m(number of clauses). Furthermore the tissue P system (n, m) uses an alphabet of 5nm +17n+4m+12 objects, 2 initial cells containing n+8 objects in all, and nrules. The length of any rule is bounded by 3. Clearly, all computations halt, and the number of steps is bounded by 3n+nm +2m+4 (when the answer is negative; if the answer is affirmative, then the number of steps is 3n+nm +2m+2). From the above we deduce the following results: THEOREM 5.2. 1. SAT ∈PMCTR . 2. NP ⊆PMCTR ,andNP ∪co −NP ⊆PMCTR . Remarks. We have presented two solutions to the SAT problem by using polarizationless recognizing membrane systems with active membranes. The first one, in the cell-like framework is semiuniform, does not use cooperation (i.e., the left-hand sides of the rules only have one object), and it is linear in time and in (the initial) space. The second one, in the tissue-like framework is a uniform solution, uses cooperation, and it is quadratic in time and in (the initial) space. Both solutions construct an exponential working space (in terms of membranes or cells) in linear time. 6. CONCLUSIONS In this paper, we have presented cell-like (inspired from the structure of the cell) and tissue-like (inspired from the cell inter-communication in tissues) recognizing membrane systems as computational devices specially suitable to attack the efficient solvability of computationally hard problems. In that new framework, two characterizations of the relation P=NP have been described through the solvability of NP-complete problems by a family of cell-like recognizing membrane systems using only basic rules. The main contribution of this paper is to formalize the concept of tissuelike membrane systems, and to present, in the framework of tissue-like recognizing membrane systems, a formal definition of the polynomial complexity class PMCTR . Besides, two polynomial time solutions to the satisfiability problem by using polarizationless (cell-like and tissue-like) recognizing membrane systems with active membranes are presented. Finally, we would like to mention two open questions for future research. What happens if in tissue-like P systems division rules are forbidden? What if communication rules are restricted to (i, a/b, j), where i, j are labels and a,b are objects (instead of multisets)? Acknowledgments The authors acknowledge the support of the project TIN2005-09345-C04-01 of the Ministerio de Educaci´ on y Ciencia of Spain, cofinanced by FEDER funds and of the project of Excellence TIC 581 of the Junta de Andaluc´ ıa. References 1. P˘ aun Gh. Membrane computing. An introduction. Berlin: Springer-Verlag; 2002. 2. P˘ aun Gh. P systems with active membranes: attacking NP–complete problems. J Automata, Lang Comb 2001;6(1):75–90. 3. Zandron C, Ferreti C, Mauri G. Solving NP–complete problems using P systems with active membranes. In: Antoniou I, Calude CS, Dinneen MJ, editors. Unconventional models of computation, UMC’2K, Berlin: Springer-Verlag; 2000. pp 289–301. 4. Krishna SN, Rama R. A variant of P systems with active membranes: solving NP–complete problems. Romanian J Inform Sci Technol 1999;2(4):357–367. 5. Obtulowicz A. Deterministic P systems for solving SAT problem. Romanian J Inform Sci Technol 2001;4(1–2):551–558. 6. P´ erez–Jim´ enez MJ. An approach to computational complexity in Membrane Computing. In: Mauri G, P˘ aun, Gh, P´ erez–Jim´ enez MJ, Rozenberg Gr, Salomaa A, editors. Membrane Computing, 5th International Workshop, WMC5, Lecture Notes in Computer Science, Vol. 3365. Berlin: Springer; 2005. pp 85–109. 7. P´ erez–Jim´ enez MJ, Romero–Jim´ enez A, Sancho–Caparrini F. The P versus NP problem through cellular computing with membranes. In: Jonoska N., P˘ aun Gh, Rozenberg G, editors. Aspects of molecular computing. Lecture Notes in Computer Science, Vol 2950. Berlin: Springer; 2004. pp 338–352. 8. Romero–Jim´ enez A. Complexity and universality in cellular computing models. PhD. Thesis, University of Seville, Spain, 2003. 9. Guti´ errez–Naranjo MA, P´ erez–Jim´ enez MJ, Riscos–N´ u˜ nez A, Romero–Campero FJ, Romero–Jim´ enez A. Characterizing tractability by cell-like membrane systems. In: K.G. Subramanian, K. Rangarajan, M. Mukund, editors. Formal models, languages and applications. MPAI Series, Vol 66. Singapore: World Scientific; 2006. pp 137–154. 10. P´ erez–Jim´ enez MJ, Riscos–N´ u˜ nez A. A linear-time solution to the knapsack problem using P systems with active membranes. In: Mart´ ın-Vide C, P˘ aun Gh, Rozenberg G, Salomaa A, editors. Membrane computing, Lecture Notes in Computer Science, Vol 2933. Berlin: Springer; 2004. pp. 248–266. 11. P´ erez–Jim´ enez MJ, Romero–Jim´ enez A, Sancho–Caparrini F. Complexity classes in cellular computing with membranes. Nat Comput 2003;2(3):265–285. 12. Alhazov A, Mart´ ın–Vide C, Pan L. Solving graph problems by P systems with restricted elementary active membranes. In: Jonoska N, P˘ aun Gh, Rozenberg G, editors. Aspects of molecular computing, Lecture Notes in Computer Science, Vol 2950. Berlin: Springer; 2004. pp 1–22. 13. P´ erez–Jim´ enez MJ, Romero–Campero FJ. An efficient family of P systems for packing items into bins. J Universal Comput Sci 2004; 10(5):650–670. 14. Sosik P. The computational power of cell division in P systems: Beating down parallel computers? Nat Comput 2003;2(3):287–298. 15. Alhazov A, Pan L, P˘ aun Gh. Trading polarizations for labels in P systems with active membranes. Acta Inform 2004;41(2–3):111–144. 16. Riscos–N´ u˜ nez A. Cellular programming: efficient resolution of NP–complete numerical problems. Ph.D. Thesis, University of Seville, Spain; 2004. 17. P´ erez–Jim´ enez MJ, Romero–Campero FJ. Trading polarizations for bi-stable catalysts in P systems with active membranes. In: Mauri G, P˘ aun Gh, P´ erez–Jim´ enez MJ, Rozenberg Gr, Salomaa A, editors. Membrane Computing, 5th International Workshop, WMC5, Lecture Notes in Computer Science, Vol. 3365. Berlin: Springer; 2005. pp. 373–388. 18. Pan L, Alhazov A, Ishdorj T-O. Further remarks on P systems with active membranes, separation, merging, and release rules. Soft Comp—A Fusion Found Methodol Appl 2005;9(9):686–690. 19. Pan L, Ishdorj T-O. P Systems with active membranes and separation rules. J Universal Comput Sci 2004;10(5):630–649. 20. P˘ aun Gh. Further twenty six open problems in membrane computing. In: Guti´ errez-Naranjo MA, Riscos-N´ u˜ nez A, Romero-Campero FJ, Sburlan D, editors. Proceedings of the Third Brainstorming Week on Membrane Computing; 2005. pp 249–262. 21. Guti´ errez–Naranjo MA, P´ erez–Jim´ enez MJ, Riscos–N´ u˜ nez A, Romero–Campero FJ. On the power of dissolution in P systems with active membranes. In: Lecture Notes in Computer Science. Berlin: Springer; Vol. 3850. 2006; pp 224–240. 22. Alhazov A, P´ erez-Jim´ enez MJ. Uniform solution to QSAT using polarizationless active membranes. In: Durand-Lose J and Margenstern M, editors. Machines, Computations, and Universality, Lecture Notes in Computer Science, Vol. 4664. Berlin: Springer; 2007. pp 122– 133. 23. P˘ aun Gh, Suzuki Y, Tanaka H, Yokomori T. On the power of membrane division in P systems. Theor Comput Sci 2004;324(1):61–85.