An Efficient Cellular Solution for the Partition Problem

An Efficient Cellular Solution for the Partition Problem Miguel Angel GUTI´ ERREZ-NARANJO Mario J. P´ EREZ-JIM´ ENEZ Agust´ın RISCOS-N ´ U˜ NEZ Research Group on Natural Computing Department of Computer Science and Artificial Intelligence University of Sevilla Avda. Reina Mercedes s/n, 41012 Sevilla, Spain E-mail: {magutier, marper, ariscosn}@us.es Abstract. Numerical problems are not very frequently addressed in the P systems literature. In this paper we present an effective solution to the Partition problem via a family of deterministic P systems with active membranes using 2-division. The design of this solution is a sequel of several previous works on other problems, mainly the Subset-Sum and the Knapsack problems but also the VALIDITY and SAT. Several improvements are introduced and explained. 1 Introduction Cellular Computing is a recent branch of Natural Computing initiated in [4]. Its goal is to abstract computing models from the structure and the functioning of living cells. The present paper is focused in the design of a family of P systems that solves a numerical NP-complete problem, and in the formal verification of this solution. Also the similarities with the solutions presented in [6], [7], [9] and [10] will be highlighted and some conclusions will be extracted from them. The analysis of the solution presented here will be done from the point of view of the complexity classes. A complexity class for a model of computation is a collection of problems that can be solved (or languages that can be decided) by some devices of this model with similar computational resources. In this paper we present a polynomial complexity class in cellular computing with membranes inspired in some ideas of Gh. P˘aun ([3], section 7.1) discussed with some members of the Research Group on Natural Computing from the University of Seville. This class allows us to detect some intrinsic difficulties of the resolution of a problem in the model above mentioned. The paper is organized as follows: first a formal definition of recognizer P systems is given in the next section; then, in section 3 the polynomial complexity class PMCAM is introduced; in sections 4 and 5 a cellular solution for the Partition problem is presented, together with some comments; and finally some final remarks are given in section 6. 237 2 Preliminaries Recall that a decision problem, X, is a pair (IX, θX) such that IXis a language over a finite alphabet (whose elements are called instances) and θXis a total boolean function over IX. Definition 1 AP system with input is a tuple (Π,Σ, iΠ), where: •Πis a P system, with working alphabet Γ, with pmembranes labelled by 1, . . . , p, and initial multisets M1, . . . , Mpassociated with them. •Σis an (input) alphabet strictly contained in Γ. •The initial multisets are over Γ−Σ. •iΠis the label of a distinguished (input) membrane. Definition 2 Let (Π,Σ, iΠ)be a P system with input. Let Γbe the working alphabet of Π, µthe membrane structure, and M1,...,Mpthe initial multisets of Π. Let mbe a multiset over Σ. The initial configuration of (Π,Σ, iΠ) with input mis (µ0, M0), where µ0=µ, M0(j) = Mj, for each j6=iΠ, and M0(iΠ) = MiΠ∪m. Remark. 1 We denote by IΠthe set of all inputs of the P system Π. That is, IΠis a collection of multisets over Σ. The computations of a P system with input m∈M(Σ), a multiset over Σ, are defined in a natural way. The only novelty is that the initial configuration must be the initial configuration of the system associated with the input multiset m∈M(Σ). In the case of P systems with input and with external output, the concept of computation is introduced in a similar way but with a small change. In the configurations, we will not work directly with the membrane structure µbut with another structure associated with it including, in some sense, the environment. Definition 3 Let µ= (V(µ), E(µ)) be a membrane structure. The membrane structure with environment associated with µis the rooted tree Ext(µ)such that: (a)the root of the tree is a new node that we will denote env;(b)the set of nodes is V(µ)∪©envª; and (c)the set of edges is E(µ)∪©{env, skin}ª. The node env is called environment of the structure µ. Note that we have only included a new node representing the environment which is only connected with the skin, while the original membrane structure remains unchanged. In this way, every configuration of the system informs about the contents of the environment. Definition 4 Alanguage accepting P system is a P system with input, (Π,Σ, iΠ), and with external output, such that the output alphabet contains only two elements: Y es and No. This definition is stated in a general way, but in this paper P systems within the active membrane model will be used. We refer to [3] (see chapter 7) for a detailed definition of evolution rules, transition steps, and configurations in this model. Now let us define the Output function for our P systems. Given a computation C= {Ci}i<r, we will denote by Mj env the content of the environment in the configuration Cj. 238 Definition 5 The output of a computation C={Ci}i<r is: Output(C) =    Y es, if Cis halting, Y es ∈Mr−1 env and No /∈Mr−1 env , No, if Cis halting, No ∈Mr−1 env and Y es /∈Mr−1 env , not defined, otherwise. If Csatisfies any of the two first conditions, then we say that it is a successful computation. Definition 6 A language accepting P system is said to be valid if for every halting computation, and only for them, one symbol Y es or one symbol No (but not both) is sent out (in the last step of the computation). Definition 7 We say that Cis an accepting computation (respectively, rejecting computation) if the object Y es (respectively, No) appears in the environment associated with the corresponding halting configuration of C; that is, if Y es =Output(C)(respectively, No =Output(C)). Definition 8 Alanguage recognizer P system is a valid language accepting P system such that all its computations halt. This recognizer systems are specially suitable when trying to solve decision problems. 3 The Complexity Class PMCAM Roughly speaking, a computational complexity study of a solution for a problem is an estimation of the resources (time, space, ...) that are required through all the processes that take place in the way from the bare instance of the problem up to the final answer. The first results about “solvability” of NP–complete problems in polynomial time (even linear) by cellular computing systems with membranes were obtained using variants of P systems that lack an input membrane. Thus, the constructive proofs of such results need to design one system for each instance of the problem. If we wanted to perform such a solution of some decision problem in a laboratory, we will find a drawback on this approach: a system constructed to solve a concrete instance is useless when trying to solve another instance. This handicap can be easily overtaken if we consider a P system with input. Then, the same system could solve different instances of the problem, provided that the corresponding input multisets are introduced in the input membrane. Instead of looking for a single system that solves a problem, we prefer designing a family of P systems such that each element decides all the instances of “equivalent size”, in certain sense. Before introducing the definition of the complexity class we deal with, we need some preliminary notions. Let us denote by AM the class of language recognizer P systems with active membranes using 2-division (see [3], section 7.2). Definition 9 Let Lbe a language and Π= (Π(t))t∈Na family of P systems with active membranes using 2-division. A polynomial encoding of Lin Πis a pair (cod, s)of polynomial-time computable functions, cod :L→St∈NIΠ(t), and s:L→Nsuch that for every u∈Lwe have cod(u)∈IΠ(s(u)). 239 That is, for each word uof the language L, we have a multiset cod(u) and a number s(u) associated with it such that cod(u) is a multiset of input for the P system Π(s(u)). Lemma 3.1 Let L1⊆Σ∗ 1and L2⊆Σ∗ 2be languages. Let Π= (Π(t))t∈Na family of P systems with active membranes using 2-division. If r: Σ∗ 1→Σ∗ 2is a polynomial-time reduction from L1to L2, and (cod, s)is a polynomial encoding of L2in Π, then (g◦r, h◦r) is a polynomial encoding of L1in Π. Proof. This result follows directly from the previous definition. For a detailed proof, we refer the reader to [9]. 2 Considering all the definitions already presented, we are now ready to give the definition of the complexity class PMCAM, which is based on the one given in [9]. Definition 10 We will say that a decision problem, X= (IX, θX), is solvable in polynomial time by a family of language recognizer P systems with active membranes using 2-division, and we denote this by X∈PMCAM, if there exists a family of P systems, Π=¡Π(t)¢t∈N, with the following properties: 1. The family Πis consistent, with regard to the class AM; that is, ∀t∈N(Π(t)∈ AM). 2. The family Πis polynomially uniform, by Turing machines; that is, there exists a deterministic Turing machine constructing Π(t)from tin polynomial time. 3. There exist two functions, cod :IX→St∈NIΠ(t)and s:IX→N+, computable in polynomial time, such that: •For every u∈IX,cod(u)∈IΠ(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∈IXevery computation of the system Π(s(u)) with input cod(u)is halting and, moreover, it performs at most p(|u|)steps. •The family Πis sound, with regard to (X,cod,s); that is, for each u∈IXit is verified that if there exists an accepting computation of the system Π(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 it is verified that if θX(u) = 1, then every computation of the system Π(s(u)) with input cod(u)is an accepting one. Remark. 2 Note that, as a consequence of the above definition, the complexity class PMCAM is closed under complement (because we use recognizer P systems). Proposition 1 Let Xand Ybe decision problems such that Xis reducible to Yin polynomial time. If Y∈PMCAM, then X∈PMCAM. That is, the complexity class PMCAM is stable under polynomial-time reduction. The proof of this result can also be found in [9]. 240 4 Solving the Partition Problem in Linear Time The Partition problem can be stated as follows: Given a set Aof nelements, where each element has a “weight” wi∈N, decide whether or not there exists a partition of Ainto two subsets such that they have the same weight. We will represent the instances of the problem using tuples of the kind (n, (w1, . . . , wn)), where nis the size of the set Aand (w1, . . . , wn) is the list of weights of the elements from A. We can define in a natural way an additive function wthat corresponds to the data in the instance. We will address the resolution of the problem via a brute force algorithm, in the framework of language recognizer P systems with active membranes using 2-division, without cooperation nor priority among rules. Our strategy will consist in: •Generation stage: membrane division is used until a specific membrane for each pair (B, Bc) is obtained, where Bis a subset of Athat contains the element a1(this condition is stated to avoid considering twice the same pair). •Calculation stage: in each membrane the weight of the associated subset and of its complementary are calculated. •Checking stage: in each membrane it is checked whether or not these two weights coincide. •Output stage: the answer is delivered according to the results of the checkings. The family presented here is Π={(Π(n),Σ(n), i(n)) : n∈N}. For each element of the family, the input alphabet is Σ(n) = {x1, . . . , xn}, the input membrane is i(n) = e, and the P system Π(n) = (Γ(n),{e, r, s}, µ, Me,Mr,Ms, R) is defined as follows: •Working alphabet: Γ(n) = {a0, a, b0, b, c, d0, d1, d2, e1, . . . , en, g, ¯g, ˆg, h0, h1, i1, i2, i4, i5, p, ¯p, q, x1, . . . , xn, Y es, No, No0, z1, . . . , z2n+1,#}. •Membrane structure: µ= [ [ ]e[ ]r]s. •Initial multisets: Me=e1g;Mr=b0h0and Ms=z1. •The set of evolution rules, R, consists of the following rules: (a) [ei]0 e→[q]− e[ei]+ e,for i= 1, . . . , n, [ei]+ e→[ei+1]0 e[ei+1]+ e,for i= 1, . . . , n −1. The goal of these rules is to generate one membrane for each subset of Athat contains a1. In each step (according to the index of ei), we consider an element of Aand either we add it to the subset associated with the membrane, B, or we put it in the complementary subset, Bc. 241 (b) [x1→a0]0 e; [x1→¯p]+ e, [xi→xi−1]+ e,for i= 2, . . . , n, [xi→¯p]− e,for i= 2, . . . , n. In the beginning, the multiplicities of the objects xj(with 1 ≤j≤n) encode the weights of the corresponding elements of A. They are not present in the definition of the system, but they are inserted as input in the membrane labelled by ebefore starting the computation: for each aj∈A,wjcopies of xjhave to be added to the input membrane. During the computation, at the same time as elements are added to the subset associated with a membrane, objects a0and ¯pare generated to store the weight of such subset and of its complementary. (b2) [en]+ e→#, [a0→#]0 s; [¯p→#]0 s, [g→#]0 s. This rules perform a “cleaning” task dissolving the membranes that are not meaningful and erasing the contents that these dissolutions spill in the skin membrane. This is not essential in the design, but it is helpful. (c) [q→i1]− e, [¯p→p]− e, [a0→a]− e, [g]− e→[ ]− e¯g. When a membrane gets negatively charged, the two first stages (i.e. generation and calculation stages) end, and then some transition rules are applied. Objects a0and ¯p, whose multiplicities encode the weights of the associated subset and of its complementary, are renamed for the next stage, when their multiplicities are compared. Also an object g is sent out and the total weight of all the elements that have not been considered in the generation stage is added to the complementary. (d) [a]− e→[ ]0 e#, [p]0 e→[ ]− e#. These rules implement the comparison above mentioned (that is, they check whether w(B) = w(Bc) holds or not). They work as a loop that erases objects aand pone by one alternatively, changing the charge of the membrane in each step. (e) [i1→i2]− e, [i2→i1]0 e. A marker that controls the previous loop is described here. The index of ijand the electric charge of the membrane give enough information to point out if the number of objects ais greater than (less than or equal to) the number of objects p. (f) [i1]0 e→[ ]+ eNo. If a subset B⊆Averifies that w(B)> w(Bc), then inside the relevant membrane that encodes it (this will be defined later) there will be less objects pthan a. This forces the loop described in (e) to halt: the moment will come when there are no objects pleft, and then the rule [i2→i1]− ewill be applied but it will not be possible to apply the rule [p]0 e→[ ]− e# at the same time. Thus, an object i1will be present in the membrane and the latter will be neutrally charged, so the rule (f) will be applied ending the checking stage with negative result. (g) [i2→i4c]− e, [c]− e→[ ]0 e#, [i4→i5]0 e, [i5]0 e→[ ]+ eY es, [i5]− e→[ ]+ eNo. 242 If, on the contrary, w(B)≤w(Bc) holds, then the objects awill be exhausted before the objects p. It is important to distinguish between the cases where the multiplicity of pis strictly greater than the multiplicity of aand the cases where both multiplicities coincide. This is why object cgives again neutral charge to the membrane and then object i5checks if a rule [p]0 e→[e]− e# is applied or not. (h) [p→#]+ e, [a→#]+ e#. If after the checking loop of rules in (d) has finished there are still some objects por ain the membrane, they can be erased (again, just for “cleaning” purposes). (i) [¯g→ˆg]+ s, ˆg[ ]+ e→[ˆg]0 e. Before the answer is sent out, the system has to make sure that all the relevant membranes have finished their checking stages. This is done using the objects gthat are present in the skin and the auxiliary membrane labelled by r(see the next set of rules). There must be 2n−1copies of g, because each relevant membrane sends one, and there is one relevant membrane for each B⊆Asuch that a1∈B, that is 2n−1in all. (j) d0[ ]− r→[d0]0 r, [h0→h1]0 r, [h1→h0]+ r, [b0]0 r→[ ]+ rb, ˆg[ ]+ r→[ˆg]0 r, b[ ]0 r→[b0]+ r, [ˆg]+ r→[ ]0 rˆg, [h0]1 r→[ ]+ rd2, [d2]+ s→[ ]− sd2. The membrane labelled by ris present in the initial configuration, but remains inactive until an object d0“wakes it up”. The purpose of the membrane is to perform a loop where the objects ˆgare involved, and thus we can detect if there are no objects ˆgpresent in the skin region. This fact will mean that all the relevant membranes have finished their checking stage, and that the system is ready to send out the answer (Y es or No). (k) [No →No0]− s, [Y es]− s→[ ]0 sY es, [No0]− s→[ ]0 sNo. Finally, the output process is activated. The skin membrane needs to be negatively charged before the answer is sent out. Object d2takes care of this (see the previous set of rules) and then, if the answer is affirmative, an object Y es will be sent out recovering the neutral charge for the skin. Note that the answer Y es has some priority over the negative answer, in the sense that we first check if there is any object Y es and then, if it is not the case, the answer No will be sent out. 5 Improving the Design If one studies how the generation stage works, one can notice that the number of spare membranes that are generated and immediately dissolved (the ones with positive charge and containing the object en) is actually 2n−1, the same amount that of relevant membranes. In the formal model we do not worry about this, because this space is created during the computation, and thus it is not needed a priori. But if we try to run a simulation of the design in a computer, then the space complexity becomes much more important. 243 Even if we use the trick of dissolving the membranes immediately after being generated, the resources used are too much. A possible solution is to avoid the generation of such useless membranes. This can be done for example using a division strategy that follows a complete binary tree structure. We are not using this strategy because we have the intention to get some of the relevant membranes before the generation stage ends, instead of getting all the membranes together after a linear number of steps. This is motivated because we are looking for better efficiency in the best or average case. Here is a proposal: Generation stage [ei]0 e→[q]0 e[ei]+ e, for i= 1, . . . , n −1, [en→q]e 0, [ei]+ e→[ei+1]0 e[ei+1]+ e, for i= 1, . . . , n −2, [en−1]+ e→[ ]0 e#, [e0 i→e0 i+1]e +, [e00 i→e0 i+1]e +, for i= 1, . . . , n −2, [e0 i→e00 i]e 0, [e00 i→λ]e 0, for i= 1, . . . , n −1, [e0 n−1→en]e +, [e00 n−1→en]e +. In this new approach, we do not produce any useless membrane, so the dissolving rules are no longer needed. Furthermore, only two electrical charges are used. Although the sequence of electrical charges of a membrane is still meaningful, the end of the stage is not marked anymore now by getting negative charge, but by having neutral charge for two consecutive evolution steps (see [1] for an example of using active membranes with only two charges). This condition is controlled by the “witness-objects” e0 iand e00 i, that show whether in the previous step the charge was 0 (e00 i) or + (e0 i). If we want to use these rules instead of the rules in (a), then the checking stage needs also to be adapted, and this could be done as follows: Weight calculation stage [x1→a0]0 e, [x1→¯p]+ e, [x0 1→a0]0 e, [x0 1→¯p]+ e, [xi→xi−1]+ e,for i= 2, . . . , n, [x0 i→xi−1]+ e,for i= 2, . . . , n, [xi→x0 i]0 e,for i= 2, . . . , n, [x0 i→¯p]0 e,for i= 2, . . . , n. This stage is almost the same as it was in the former designs, but again it is necessary to introduce “witness-objects” to detect when the generation stage finishes, because in this moment the calculation stage must also conclude. 244 6 Final Remarks The designs proposed here try to be as general as possible, and at the same time we try to be uniform, in the sense that the design of a family of P systems that solves a problem is not made thinking on one P system for each instance of the problem. Instead, each P system of the family can deal with a set of instances of the same size (in this case, with the same value of n, independently of the values of the weight function), receiving at the beginning of the computation an input that encodes the concrete instance. It is also important that the number of steps of the computations is polynomial (preferably linear) with respect to the input given; in the case of Partition the number of steps is of a linear order. Several numerical problems have already been solved with similar techniques: the Subset-Sum problem ([6]), the Knapsack problem ([7]) and the Partition problem (in this paper), among others. This fact gives rise to the following question: is it possible to formalize a procedure of “reusing rules”? This question is addressed in [11], in this volume. Some first attempts in this direction have already been made, in the framework of the P systems simulator in Prolog (see [2]). Several files have been created, containing the instructions to generate the evolution rules that deal with the different problems (following the schemes given in the corresponding designs), and now we are working to put these files together and reuse somehow the information. Another research topic related with these ideas is trying to formalize what means polynomial reduction performed by P systems. It will be nice to have a definition of a complexity class that only depends on P systems parameters, without including a polynomial-time precomputing process (which is somehow unnatural). Finally, the omnipresent burden of membrane computing: still not implemented in labs (neither in other physical means). Chemical processes in nature are often cyclic, or reversible. Maybe instead of trying to bridge the definition of the P systems model with biology, a more reachable goal is to bridge the “subroutines language” of membrane computing with cellular biochemistry. Acknowledgements. The support of this research through the project TIC200204220-C03-01 of the Ministerio de Ciencia y Tecnolog´ıa of Spain, cofinanced by FEDER funds, is gratefully acknowledged. References [1] Alhazov, A., Freund, R., P˘aun, Gh.: P systems with active membranes and two polarizations, in the present volume. [2] Cord´on-Franco, A., Guti´errez-Naranjo, M.A., P´erez-Jim´enez, M.J. Sancho-Caparrini, F.: A Prolog simulator for deterministic P systems with active membranes, New Generation Computing, to appear. [3] P˘aun, Gh.: Membrane Computing. An introduction, Springer-Verlag, Berlin, 2002. [4] P˘aun, Gh.: Computing with membranes, Journal of Computer and System Sciences, 61, 1 (2000), 108–143. 245