A uniform solution to SAT using membrane creation

A uniform solution to SAT using membrane creation Miguel A. Guti´ errez-Naranjo, Mario J. P´ erez-Jim´ enez∗, Francisco J. Romero-Campero Research Group on Natural Computing, Department of Computer Science and Artificial Intelligence, University of Sevilla, Avda. Reina Mercedes s/n, 41012, Sevilla, Spain Abstract In living cells, new membranes are produced basically through two processes: mitosis and autopoiesis. These two processes have inspired two variants of cell-like membrane systems, namely P systems with active membranes and P systems with membrane creation. In this paper, we provide the first u niform, e fficient so lution to th e SAT pr oblem in th e fr amework of re cogniser P systems with membrane creation using dissolution rules. Recently the authors have proved that if the dissolution rules are not allowed to be used, then the polynomial complexity class associated with this variant of P systems is the standard complexity class P. This result, together with the main result of this paper, shows the surprising role of the apparently “innocent” operation of membrane dissolution. The use of this type of rule establishes the difference between efficiency and non-efficiency for P systems with membrane creation, and provides a barrier between P and NP (assuming P 6= NP). Keywords: Natural computing; Membrane computing; Cellular complexity classes; SAT problem 1. Introduction Membrane computing is an emergent branch of natural computing introduced by P˘ aun in [12]. Since then, it has received important attention from the scientific community. In fact, membrane computing has been selected by the Institute for Scientific Information, USA, as a Fast Emerging Research Front in Computer Science, and [11] was mentioned in [14] as a highly cited paper in October 2003. This non-deterministic model of computation starts from the assumption that the processes taking place in the compartmental structures of living cells can be interpreted as computations. The devices of this model are called P systems. Roughly speaking, a P system consists of a cell-like membrane structure, in the compartments of which one places multisets of objects that evolve according to given rules in a synchronous non-deterministic maximally parallel manner.1The representation of data as multisets is an abstraction from the way in which chemical compounds are found in living cells. Membrane computing is a cross-disciplinary field, with contributions by computer scientists, ∗Corresponding author. Tel.: +34 954557952; fax: +34 954557952. E-mail address: [email protected] (M.J. P´ erez-Jim´ enez). 1An introduction can be found in [6], and updated information at [15]. biologists, formal linguists and complexity theoreticians, enriching each others’ results and problems, and promising new research lines. In this paper, we present a contribution from the computational side. We introduce a family of P systems with membrane creation, constructed in a uniform way, that solves the problem of determining, for a given formula in conjunctive normal form, whether it is satisfiable or not (the SAT problem). The paper is organised as follows: first P systems with membrane creation are introduced in the next section. In Section 3, recogniser P systems (devices that capture the intuitive idea underlying the concept of an algorithm) are presented. The solution in the framework of membrane creation to the SAT problem is given in Section 4. Finally, some formal details and conclusions are given. 2. P systems with membrane creation Polynomial solutions to NP-complete problems in membrane computing are produced by trading time for space. This is inspired by the capability of cells to produce an exponential number of new membranes (new workspaces) in polynomial time. Basically, there are two ways of producing new membranes in living cells: mitosis (membrane division) and autopoiesis (membrane creation, see [5]). Both ways of generating new membranes have given rise to different variants of P systems: P systems with active membranes, where the new workspace is generated by membrane division, and P systems with membrane creation, where the new membranes are created from objects. Both models have been proved to be universal, but up to now there is no theoretical result proving that these models simulate each other in polynomial time. P systems with active membranes have been successfully used to design solutions to NP-complete problems, as SAT [10], Subset Sum [7], Knapsack [8], Bin Packing [9] and Partition [2], but as P˘ aun pointed in [13]“membrane division was much more carefully investigated than membrane creation as a way to obtain tractable solutions to hard problems”. In this paper, we investigate the second variant mentioned above. Membranes are created in living cells, for instance, in the process of vesicle mediated transport, and in order to keep molecules close to each other to facilitate their reactions. Membranes can also be created in a laboratory—see [5]. Here, we abstract the operation of the creation of new membranes under the influence of existing chemical substances to define P systems with membrane creation. Recall that a P system with membrane creation is a construct of the form Π=(O,H, µ, w1, . . . , wm,R), where m≥1 is the initial degree of the system; Ois the alphabet of objects, and His a finite set of labels for membranes; µis a membrane structure, consisting of mmembranes injectively labelled with elements of H, and w1, . . . , wmare strings over O, describing the multisets of objects placed in the mregions of µ;Ris a finite set of rules, of the forms: (a) [a→v]hwhere h∈H,a∈Oand vis a string over Odescribing a multiset of objects (object evolution rules) associated with membranes and depending only on the label of the membrane. (b) a[ ]h→ [b]hwhere h∈H,a,b∈O (send-in communication rules). An object is introduced in the membrane, possibly modified. (c) [a]h→ [ ]hbwhere h∈H,a,b∈O (send-out communication rules). An object is sent out of the membrane, possibly modified. (d) [a]h→bwhere h∈H,a,b∈O (dissolution rules). A membrane is dissolved in reaction with an object, which can be modified. (e) [a→ [v]h2]h1where h1,h2∈H,a∈Oand vis a string over Odescribing a multiset of objects (creation rules). In reaction with an object, a new membrane is created. This new membrane is placed inside of the membrane of the object, which triggers the rule and has associated an initial multiset and a label. Rules are applied according to the following principles: •Rules from (a) to (d) are used as is usual in the framework of membrane computing, i.e., in a maximal parallel way. In one step, each object in a membrane can only be used for one rule (nondeterministically chosen), but any object which can evolve by a rule must do it (with the restrictions indicated below). •Rules of type (e) are used also in a maximal parallel way. Each object ain a membrane labelled with h1produces a new membrane with label h2, placing in it the multiset of objects described by the string v. •If a membrane is dissolved, its content (multiset and interior membranes) becomes part of the immediately external one. The skin is never dissolved. •All the elements which are not involved in any of the operations to be applied remain unchanged. •Rules associated with the label hare used for all membranes with this label, irrespective of whether the membrane is an initial one or whether it was created. •Several rules can be applied to different objects in the same membrane simultaneously. The exceptions are the rules of type (d), since a membrane can be dissolved only once. 3. Recogniser P systems with membrane creation Recogniser P systems were introduced in [8], and are the natural framework to study and solve decision problems, since deciding whether an instance has an affirmative or negative answer is equivalent to deciding if a string belongs to the language associated with the problem or not. In the literature, recogniser P systems are associated in a natural way with P systems with input. The data related to an instance of the decision problem has to be provided to the P system in order for it to compute the appropriate answer. This is done by codifying each instance as a multiset placed in an input membrane. The output of the computation, (yes or no), is sent to the environment. In this way, P systems with input and external output are devices which can be seen as black boxes, in which the user provides the data before the computation starts, and the P system sends to the environment the output in the last step of the computation. Another important feature of P systems is their non-determinism. The design of a family of recogniser P systems has to consider it, because all possibilities in the non-deterministic computations have to output the same answer. This can be summarised in the following definitions (taken from [1]). Definition 1. AP system with input is a tuple (Π,Σ,iΠ), where: (a) Πis a P system, with working alphabet Γ, with pmembranes labelled by 1, . . . , p, and initial multisets w1, . . . , wpassociated with them; (b) Σis an (input) alphabet strictly contained in Γ; the initial multisets are over Γ−Σ; and (c) iΠis the label of a distinguished (input) membrane. Let mbe a multiset over Σ. The initial configuration of (Π,Σ,iΠ)with input m is (µ, w1, . . . , wiΠ∪m, . . . wp). Definition 2. Arecogniser P system is a P system with input, (Π,Σ,iΠ), and with external output such that: (1) The working alphabet contains two distinguished elements, yes and no. (2) All its computations halt. (3) If Cis a computation of Π, then either some object yes or some object no (but not both) must have been released into the environment, and only in the last step of the computation. We say that Cis an accepting computation (respectively, rejecting computation) if the object yes (respectively, no) appears in the external environment associated with the corresponding halting configuration of C. In the next section, we present a uniform solution to the SAT problem in linear time in the following sense. Definition 3. Let Fbe a class of recogniser P systems. A decision problem X=(IX, θX)is solvable in polynomial time by a family Π=(Π(n))n∈N, of P systems from F, and we denote this by X∈PMCF, if the following holds: •The family Πis polynomially uniform by Turing machines; that is, there exists a deterministic Turing machine constructing Π(n)from n∈Nin polynomial time. •There exist a pair (cod,s)of polynomial-time computable functions over IXsuch that: −For each instance u∈IX,s(u)is a natural number and cod(u)is an input multiset of the system Π(s(u)). −The family Πis polynomially bounded with regard to (X,cod,s); that is, there exists a polynomial function p, such that for each u∈IX, each computation of Π(s(u)) with input cod(u)performs at most p(|u|)steps. −The family Πis sound with regard to (X,cod,s); i.e., for each u∈IX, if there exists an accepting computation of Π(s(u)) with input cod(u), then θX(u)=1. −The family Πis complete with regard to (X,cod,s); that is, for each u∈IX, if θX(u)=1, then every computation of Π(s(u)) with input cod(u)is an accepting one. In the above definition we have imposed a requirement for every P system Π(n)to be confluent, in the following sense: every computation of a system with the same input must always give the same answer. It can be proved that the class PMCFis closed under polynomial-time reduction and complement, see [10]. In this paper, we will deal with the class MC of recogniser P systems with membrane creation. 4. Solving SAT in linear time with membrane creation The SAT problem is the following: Given a Boolean formula in conjunctive normal form (CNF), to determine whether or not it is satisfiable, that is, whether there exists an assignment to its variables on which it evaluates to true. In this section, we describe a family of P systems which solves this problem. We will address the resolution via a brute force algorithm, in the framework of recogniser P systems with membrane creation, which consists in the following stages: •Generation and evaluation stage: Using membrane creation, we will generate all possible assignments associated with the formula and evaluate it for each. •Checking stage: In each membrane, we check whether or not the formula evaluates to true on the assignment associated with it. •Output stage: The systems sends out to the environment the right answer. Let us consider the pair function h,idefined by hn,mi = ((n+m)(n+m+1)/2)+n. This function is polynomial-time computable (it is primitive recursive and bijective from N2onto N). For any given formula in CNF, ϕ=C1∧ · · · ∧ Cm, with nvariables and mclauses, we construct a P system Π(hn,mi)solving it. Therefore the family presented here is Π= {(Π(hn,mi), Σ(hn,mi), i(hn,mi)) :(n,m)∈N2}. For each element of the family, the input membrane is i(hn,mi)=t, the input alphabet is Σ(hn,mi)= {xi,j,xi,j: 1≤i≤m,1≤j≤n}and the P system Π(hn,mi)=(Γ(hn,mi), {a,t,f,1, . . . , m}, µ, wa, wt,R(hn,mi)) is defined as: •Working alphabet: Γ(hn,mi)=Σ(hn,mi)∪ {xi,j,l,xi,j,l,zi,zi,l,rj,rj,l,dj:l=t,f,1≤i≤n,1≤j≤ m} ∪ {yes,no,yesi,noj:0≤i≤9,0≤j≤2n+11} ∪ {q,k0,k1,k2,t0,t1,t2,t3}. Note that the size of the alphabet is 6nm +5n+4m+32 ∈Θ(nm), and recall that the size of an instance of the SAT problem, a formula with nvariables and mclauses, is of the order Ω(nm); therefore the size of the working alphabet is linear on the size of the input. •Initial membrane structure: µ= [ [ ]a]t •Initial Multisets: wa= {no0}wt= {z0,t,z0,f} •The set of evolution rules, R(hn,mi), consists of the following (recall that λdenotes the empty string): 1.[zj,t→ [zj+1k0]t]l[zj,f→ [zj+1k0]f]lfor l=t,fand j=0, . . . , n−2. The goal of these rules is to create one membrane for each assignment to the variables of the formula. The new membrane with label t, where the object zj+1is placed, represents the assignment xj+1=true; on the other hand the new membrane with label f, where the object zj+1is placed represents the assignment xj+1=false. 2.[xi j →xi,j,txi,j,f]l[ri→ri,tri,f]l [xi,j→xi,j,txi,j,f]l[zk→zk,tzk,f]l)for l=t,f;k=0, . . . , n−1 i=1, . . . , m;j=1, . . . n. These rules duplicate the objects representing the formula so it can be evaluated on the two possible assignments, xj=true (xi,j,t,xi,j,t) and xj=false (xi,j,f,xi,j,f). The objects riare also duplicated (ri,t,ri,f) in order to keep track of the clauses that evaluate to true on the previous assignments to the variables. The objects zkproduce the objects zk,tand zk,fwhich will create the new membranes representing the two possible assignments for the next variable. 3.xi,1,t[ ]t→ [ri]t,xi,1,t[ ]t→ [λ]t xi,1,f[ ] f→ [λ]f,xi,1,f[ ] f→ [ri]f)for i=1, . . . , m. According to these rules, the formula is evaluated in the two possible assignments for the variable that is being analysed. The objects xi,1,t(respectively xi,1,f) get into the membrane labelled with t(respectively f), being transformed into the objects rirepresenting that the clause number ievaluates to true on the assignment xj+1=true (resp. xj+1=false). On the other hand, the objects xi,1,t(respectively xi,1,t) get into the membrane labelled with f (respectively t), producing no objects. This signifies that these objects do not make the clause true in the assignment xj+1=true (respectively xj+1=false). 4.xi,j,t[ ]t→ [xi,j−1]t,xi,j,t[ ]t→ [xi,j−1]t xi,j,f[ ] f→ [xi,j−1]f,xi,j,f[ ] f→ [xi,j−1]f ri,t[ ]t→ [ri]t,ri,f[ ] f→ [ri]f      for i=1, . . . , m j=2, . . . , n. In order to analyse the next variable, the second subscripts of the objects xi,j,land xi,j,lare decreased when they are sent into the corresponding membrane, labelled with l. Moreover, following the last rule, the objects ri,lget into the new membranes to keep track of the clauses that evaluate to true on the previous assignments. 5.[ks→ks+1]l[k2]l→λfor l=t,f;s=0,1. The objects kifor i=0,1,2 are counters that dissolve membranes when they are not useful any longer during the rest of the computation. 6.[zn−1,t→ [zn]t]l,[zn−1,f→ [zn]f]l,[zn→d1. . . dmq]lfor l=t,f. At the end of the generation stage, the objects zn−1,lcreate two new membranes where the formula will be evaluated on the two possible assignments for the last variable xn. The object znis placed in both membranes, and will produce the objects d1, . . . , dm,yes0, which will take part in the checking stage. 7.[di→ [t0]i]lri,t[ ]i→ [ri]i,[ri]i→λ [ts→ts+1]i,[t2]i→t3)for i=1, . . . , m s=0,1. Following these rules, each object dicreates a new membrane with label iwhere the object t0is placed; this object will act as a counter. The object rigets into the membrane labelled with iand dissolves it, preventing the counter, ti, from reaching the object t2. The fact that the object t2appears in a membrane with label imeans that there is no object ri; that is, the clause number idoes not evaluate to true on the assignment associated with the membrane; therefore neither does the formula evaluate to true nor its associated assignment. 8.[q→ [yes0]a]lt3[ ]a→ [t3]a[t3]a→λ [yesh→yesh+1]a,[yes5]a→yes6[yes6]l→yes7[ ]l)for l=t,f h=0, . . . , 4. The object qcreates a membrane with label awhere the object yes0is placed. The object yeshevolves to the object yesh+1; at the same time the objects t3can get into the membrane labelled with aand dissolve it, preventing the object yes6from being sent out from this membrane. 9.[nop→nop+1]a,[no2n+10]a→no2n+11 yes7[ ]a→ [yes8]a,[yes8]a→yes9 [yes9]t→yes[ ]t[no2n+11]t→no[ ]t      for p=0, . . . , 2n+9. From the beginning of the computation, the object nopevolves to the object nop+1inside the membrane labelled with a. If any object yes7is produced during the computation, it means that the formula evaluates to true on some assignment to its variables, and it gets into this membrane and dissolves it, producing the object yes9that will send out to the environment the object yes. On the other hand, if no object yes7appears in the skin, the object no2n+10 will dissolve the membrane labelled with a, producing the object no2n+11 that will send out to the environment the object no. 4.1. An overview of the computation First of all, given a formula in CNF, ϕ=C1∧ · · · ∧ Cmsuch that Var(ϕ) = {x1, . . . , xn}, we define s(ϕ) = hn,mi and cod(ϕ) = {xi,j:xj∈Ci} ∪ {xi,j: ¬xi,j∈Ci}. Then (cod,s)is a pair of polynomial-time computable functions over ISAT such that s(ϕ) is a natural number and cod(ϕ) is an input multiset over Π(s(u)). Next, we describe informally how the P system with Π(s(ϕ)) and with input cod(ϕ) works. In the initial configuration, we have, on the one hand, the input multiset cod(ϕ) and the objects z0,tand z0,fplaced in the skin (membrane labelled with t); and on the other hand, we have in the membrane labelled with athe object no0. This object evolves during the computation following the first rule in the set 9. In the first step of the computation, the object z0,tcreates a new membrane with label t, which represents the assignment x1=true and the object z0,fcreates a new membrane with label f, which represents the assignment x1=false. In these two new membranes, the objects z1and k0are placed. At the same time, the input multiset representing the formula is duplicated following the two first rules in 2. In the next step, according to the rules in 3, the formula is evaluated on the two possible assignments for x1. In the same step, the rules in 4 decrease the second subscript of the objects representing the formula (xi,j,l,xi,j,lwith j≥2) in order to analyse the next variable. Moreover, at the same time, the object z1produces the object z1,tand z1,fand the system is ready to analyse the next variable. And so the generation and evaluation stages go until all the possible assignments to the variables are generated, and the formula is evaluated on each one of them. Observe that it takes two steps to generate the possible assignments for a variable and to evaluate the formula on them; therefore the generation and evaluation stages take 2n steps. Note that the object k0in the rules in 5 is a counter that dissolves the membrane when the object k2appears; that is, it dissolves the membrane once the membrane is not useful any longer in the rest of the computation. The checking stage starts when the object znproduces the objects d1, . . . , dmand the object q. In the first step of the checking stage, each object di, for i=1, . . . , mcreates a new membrane labelled with i, where the object t0is placed, and the object qcreates a new membrane with label a, placing the object yes0in it. The objects ri, which signify that the clause number ievaluates to true on the assignment associated with the membrane, are sent into the membranes by the last rule in 4, so the system keeps track of the clauses that are true. The objects ri,tget into the membrane with label i, and dissolve it in the following two steps, preventing the counter t2from dissolving the membrane and producing the object t3according to the last rule in 7. If, for some i, there is no object ri, which means that the clause idoes not evaluate to true on the associated assignment, then the object t2will dissolve the membrane labelled with i, thus producing the object t3that will get into the membrane with label awhere the object yeshevolves following the rules in 8. The object t3dissolves the membrane, preventing the production of the object yes6. Therefore the checking stage takes 6 steps. Finally the output stage takes place according to the rules in 9. On the one hand, if some object yes6is present in any membrane (which represents that the formula evaluates to true on the assignment associated with this membrane) it is sent out to the skin being transformed into the object yes7. In the next step, yes7gets into the membrane labelled with a, being transformed into yes8; then it dissolves the membrane, producing the object yes9. This dissolution prevents the object no2n+11 from being produced. And finally the object yes is sent out to the environment. On the other hand, if there is no object yes6, then the membrane with label ais not dissolved, and thus the object no2n+11 is produced, and the object no is sent out to the environment. Observe that the output stage takes 5 steps if the answer is yes, and 6 steps if the answer is no. 5. Some formal details In the previous section, we have presented a family Πof recogniser P systems which solve the SAT problem. For each Boolean formula, a P system Π(hn,mi)is constructed, where nis the number of variables and mis the number of clauses. First of all, observe that the evolution rules of Π(s(ϕ)) are defined in a recursive manner from ϕ, in particular from nand m. Let us list the necessary resources to construct Π(s(ϕ)): •Size of the alphabet: 6nm +5n+4m+32 ∈Θ(nm) •Initial number of membranes: 2 ∈Θ(1) •Initial number of objects: 3 ∈Θ(1) •Sum of the lengths of the rules: 86nm +84n+144m+121 ∈Θ(nm). Therefore a Turing machine working in polynomial time can build Π(s(ϕ)) from the formula ϕ. Finally, we can prove, using a formal description of the computation, that the P system Π(s(ϕ)) with input cod(ϕ) always halts and sends to the environment the object yes or no in the last step. The number of steps of such a P system is 2n+11 if the output is yes and 2n+12 if the output is no; therefore there exists a linear bound for the number of steps of the computation. Hence, the family Πof recogniser P systems with membrane creation using dissolution rules solves the SAT problem in polynomial (actually, linear) time according to Definition 3. So, we have the following result: Theorem 4. SAT ∈PMCMC . Corollary 5. NP ∪co-NP ⊆PMCMC . Proof. It suffices to remark that the SAT problem is NP-complete, SAT ∈PMCMC , and that this complexity class is closed under polynomial time reduction and under complement.  Remark 6. Note that in the family of recogniser P systems given in Section 4, membrane creation rules are used to produce an exponential workspace where all possible assignments to the variables of the formula are generated, whereas the process of checking whether or not the formula evaluates to true on any of them is done using dissolution rules. If we denote by MC+d(respectively, MC−d) the class of recogniser P systems with membrane creation and with dissolution rules (respectively, without dissolution rules), then we have just proved that NP ∪co-NP ⊆PMCMC+d. In [3], the authors showed that the generation in polynomial time of an exponential workspace (number of membranes) using membrane creation rules, is not enough to solve NP-complete problems in polynomial time (unless P=NP). More precisely, the authors proved that P=PMCMC−d. Summing up, in the framework of recogniser P systems with membrane creation, we have proved the following: (a) the class of problems which can be solved in a polynomial time by a family of such P systems without dissolution is equal to class P; and (b) the class of problems which can be solved in a polynomial time by a family of such P systems with dissolution contains the class NP ∪co-NP. 6. Conclusions Membrane computing is a new cross-disciplinary field of natural computing, which has reached an important success in its short life. This paper deals with the study of efficient solutions to well-known computationally hard problems, and in this sense it is placed between the theoretical results mainly related to computational completeness and computational efficiency, and the real implementation of the devices. It exploits membrane creation (a poorly studied variant) to solve NP-complete problems, giving the first uniform solution to SAT in polynomial time (recently, we have proved that this variant is PSPACE powerful [4]). We stress the relevant role played by the rules of dissolution in the framework of recogniser P systems using membrane creation, in order to “separate” their tractability from the (presumable) intractability of decision problems, putting a barrier between the complexity classes Pand NP (assuming P6= NP). This paper can be considered as a contribution to the interesting problem of characterising the tractability of hard decision problems in terms of the descriptional resources required in membrane systems. Acknowledgements This work is supported by Ministerio de Ciencia y Tecnolog´ ıa of Spain, by Plan Nacional de I+D+I (2000– 2003) (TIC2002-04220-C03-01), cofinanced by FEDER funds, and by a FPI fellowship (of the third author) from the University of Seville. References [1] M.A. Guti´ errez-Naranjo, M.J. P´ erez-Jim´ enez, A. Riscos-N´ u˜ nez, Towards a programming language in cellular computing, Electronic Notes in Theoretical Computer Science 123 (2005) 93–110. [2] M.A. Guti´ errez-Naranjo, M.J. P´ erez-Jim´ enez, A. Riscos-N´ u˜ nez, A fast P system for finding a balanced 2-partition, Soft Computing 9 (9) (2005) 673–678. [3] M.A. Guti´ errez-Naranjo, M.J. P´ erez-Jim´ enez, A. Riscos-N´ u˜ nez, F.J. Romero-Campero, Characterizing tractability with membrane creation, in: 7th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, SYNASC 2005. Workshop on Theory and Applications of P Systems, Timisoara, Romania, 2005, IEEE Computer Society, 2005, pp. 448–457. [4] M.A. Guti´ errez-Naranjo, M.J. P´ erez-Jim´ enez, F.J. Romero-Campero, A linear time solution for QSAT with membrane creation, in: R. Freund, G. Lojka, M. Oswald, Gh. Paun (Eds.), Pre-Proceedings of the Sixth International Workshop on Membrane Computing, WMC6, Vienna University of Technology, Vienna, Austria, 2005, pp. 395–409. [5] P.L. Luisi, The chemical implementation of autopoiesis, in: G.R. Fleishaker, S. Colonna, P.L. Luisi (Eds.), Self-Production of Supramolecular Structures, Kluwer, Dordrecht, 1994. [6] Gh. P˘ aun, Membrane Computing. An Introduction, Springer-Verlag, Berl´ ın, 2002. [7] M.J. P´ erez-Jim´ enez, A. Riscos-N´ u˜ nez, Solving the Subset-Sum problem by active membranes, New Generation Computing 23 (4) (2005) 367–384. [8] M.J. P´ erez-Jim´ enez, A. Riscos-N´ u˜ nez, A linear solution for the Knapsack problem using active membranes, Lecture Notes in Computer Science 2933 (2004) 250–268. [9] M.J. P´ erez-Jim´ enez, F.J. Romero-Campero, Solving the BIN PACKING problem by recognizer P systems with active membranes, in: Gh. P˘ aun, A. Riscos, A. Romero, F. Sancho (Eds.), Proceedings of the Second Brainstorming Week on Membrane Computing, Report RGNC 01/04, University of Seville, Seville, Spain, 2004, pp. 414–430. [10] M.J. P´ erez-Jim´ enez, A. Romero-Jim´ enez, F. Sancho-Caparrini, A polynomial complexity class in P systems using membrane division, in: E. Csuhaj-Varj´ u, C. Kintala, D. Wotschke, Gy. Vaszyl (Eds.), Proceedings of the 5th Workshop on Descriptional Complexity of Formal Systems, DCFS 2003, 2003, pp. 284–294. [11] A. P˘ aun, Gh. P˘ aun, The power of communication: P systems with symport/antiport, New Generation Computing 20 (3) (2002) 295–305. [12] Gh. P˘ aun, Computing with membranes, Journal of Computer and System Sciences 61 (1) (2000) 108–143. [13] Gh. P˘ aun, Further open problems in membrane computing, in: Gh. P˘ aun, A. Riscos, A. Romero, F. Sancho (Eds.), Proceedings of the Second Brainstorming Week on Membrane Computing, Report RGNC 01/04, University of Seville, Seville, Spain, 2004, pp. 354–365. [14] ISI web page. http://esi-topics.com/erf/october2003.html. [15] P systems web page. http://psystems.disco.unimib.it/.