A Logarithmic Bound for Solving Subset Sum with P Systems

A Logarithmic Bound for Solving Subset Sum with P Systems Daniel D´ıaz-Pernil, Miguel A. Guti´errez-Naranjo, Mario J. P´erez-Jim´enez, and Agust´ın Riscos-N´u˜nez Research Group on Natural Computing University of Sevilla, Spain {sbdani,magutier,marper,ariscosn}@us.es Abstract. The aim of our paper is twofold. On one hand we prove the ability of polarizationless P systems with dissolution and with division rules for non-elementary membranes to solve NP-complete problems in a polynomial number of steps, and we do this by presenting a solution to the Subset Sum problem. On the other hand, we improve some similar results obtained for different models of P systems by reducing the number of steps and the necessary resources to be of a logarithmic order with respect to k(recall that nand kare the two parameters used to indicate the size of an instance of the Subset Sum problem). As the model we work with does not allow cooperative rules and does not consider the membranes to have an associated polarization, the strategy that we will follow consists on using objects to represent the weights of the subsets through their multiplicities, and comparing the number of objects against a fixed number of membranes. More precisely, we will generate kmembranes in log ksteps. 1 Introduction This paper is the continuation of a series of results on Complexity Classes in Membrane Computing that are trying to establish the relevance, in terms of computing power, of each one of the possible features of a P system (see [3]). The Subset Sum problem is a well-known NP-complete problem which can be formulated as follows: Given a finite set A, a weight function, w : A → N,anda constant k ∈ N, determine whether or not there exists a subset B ⊆ A such that w(B)=k. It has been a matter of study in Membrane Computing several times, being mainly used to prove the ability of different P system models in order to solve problems from the NP class in a polynomial time. This speed-up is achieved by trading space for time, in the sense that the considered models allow that an exponential amount of membranes can be produced by a P system in a polynomial number of steps. For example, solutions to the Subset Sum problem working in a number of steps which is linear with respect to the parameters n and k have been designed using P systems with active membranes [9], using tissue P systems with cell division [2], and using P systems with membrane creation [4]. In this paper we work with P systems using division of non-elementary membranes and dissolution rules. Our aim goes beyond adding this P system model to the above mentioned list; we improve previous complexity results by solving the Subset Sum problem in a linear number of steps with respect to nand logk. We also improve the pre-computation process, as the initial resources are also bounded by logk. The paper is structured as follows: in the next section we present the formal framework, i.e., we recall the definition of recognizing P systems, the P system model used along the paper is settled and the class PMCAM0(+d,+ne)is presented. In Section 3, our design of the solution of the Subset Sum problem is presented and some conclusions are given in the last section. 2 Formal Framework In this paper we are using cellular systems for attacking the resolution of decision problems. This means that for each instance of a problem that we try to solve, we are only interested in obtaining a Boolean answer (Yes or No). Therefore, the P system can behave as a black box to which the user supplies an input and from which an affirmative or negative answer is received. This is indeed the motivation for defining the concept of recognizing P systems (introduced in [13]). 2.1 Recognizing P Systems Let us recall that a decision problem, X,isapair(IX,θ X)whereIXis a language over an alphabet whose elements are called instances and θXis a total Boolean function over IX.Ifuis an instance of the problem Xsuch that θX(u)=1 (respectively, θX(u) = 0), then we say that the answer to the problem for the instance considered is Yes (respectively, No). Keeping this in mind, recognizing P systems are defined as a special class of membrane systems that will be used to solve decision problems, in the framework of the complexity classes theory. Note that this definition is stated informally, and it can be adapted for any kind of membrane system paradigm. A recognizing P system is a P system with input and with external output having two distinguished objects yes and no in its working alphabet such that: –All computations halt. –If Cis a computation of Π, then either the object yes or the object no (but not both) must have been released into the environment, and only in the last step of the computation. 2.2 The P System Model The power of membrane division as a tool for efficiently solving NP problems in Membrane Computing has been widely proved. Many examples of designs of P systems solving NP-complete problems have been proposed in the framework of P systems with active membranes with two polarizations and three polarizations and in the framework of P systems with non-elementary membrane division. The key of such solutions is the creation of an exponential amount of workspace (membranes) in a polynomial time. In the literature, one can find two quite different rules for performing membrane division. On the one hand, in [7], P systems with active membranes were presented. In this model new membranes were obtained through the process of mitosis (membrane division). In these devices membranes have polarizations, one of the “electrical charges” 0,−,+, and several times the problem was formulated whether or not these polarizations are necessary in order to obtain polynomial solutions to NP–complete problems. The last result is that from [1], where one proves that two polarizations suffice. P systems with active membranes have been successfully used to design (uniform) solutions to well-known NP–complete problems, such as SAT [13], Subset Sum [9], Knapsack [10], Bin Packing [11], Partition [5], and the Common Algorithmic Problem [12]. The syntactic representation of membrane division rule is [a]e1 h→[b]e2 h[c]e3 h(1) where his a label, e1,e2and e3are electrical charges and a,band care objects. The interpretation is well-known: An elementary membrane can be divided into two membranes with the same label, possibly transforming some objects and changing the electrical charge. All objects present in the membrane except the object triggering the rule are copied into both new membranes. In [6], a variant of this rule was used in which the polarization was dropped: [a]h→[b]h[c]h.(2) In both cases (with and without polarizations) the key point is that the membranes are always elementary membranes. In the literature, there also exist rules for the division of non-elementary polarizationless membranes, as [[]h1[]h2]h0→[[]h1]h0[[]h2]h0(3) where h0,h 1and h2are labels. There exists an important difference with respect to elementary membrane division: in the case of (3), the rule is not triggered by the occurrence of an object inside a membrane, but by the membrane structure instead. This point has a crucial importance in the design of solutions, since a membrane can be divided by the corresponding rule even if there are no objects inside it. According to the representation (3), the membrane h0divides into two new membranes also with label h0and all the information (objects and membranes) different from membranes h1and h2inside is duplicated. In this paper we use a type of membrane division which is syntactically equivalent to (2) [a]h→[b]h[c]h,(4) but we will consider a semantic difference; the dividing membrane can be elementary or non-elementary and after the division, all the objects and membranes inside the dividing membrane are duplicated, except the object athat triggers the rule, which appears in the new membranes possibly modified (represented as objects band c). In this paper we work with a variant of P systems with active membranes which we call with weak division, and that does not use polarizations. Definition 1. A P system with active membranes with weak division is a P system with Γas working alphabet, with Has the finite set of labels for membranes, and where the rules are of the following forms: (a) [a→u]hfor h∈H,a∈Γ,u∈Γ∗. This is an object evolution rule, associated with a membrane labelled with h:anobjecta∈Γbelonging to that membrane evolves to a multiset u∈Γ∗. (b) a[] h→[b]hfor h∈H,a, b ∈Γ. An object from the region immediately outside a membrane labeled with his introduced in this membrane, possibly transformed into another object. (c) [a]h→b[] hfor h∈H,a, b ∈Γ. An object is sent out from membrane labeled with hto the region immediately outside, possibly transformed into another object. (d) [a]h→bfor h∈H,a, b ∈Γ: A membrane labeled with his dissolved in reaction with an object. The skin is never dissolved. (e) [a]h→[b]h[c]hfor h∈H,a, b, c ∈Γ. A membrane can be divided into two membranes with the same label, possibly transforming some objects. The content of the membrane is duplicated. The membrane can be elementary or not. 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 non– deterministic way), but any object which can evolve by one rule of any form, must evolve. –If at the same time a membrane labeled with 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 with 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 note that in this framework we work without cooperation, without priorities, with weak division, and without changing the labels of membranes. In this paper we work within the model of polarizationless P systems using weak division of non-elementary membranes and dissolution.LetAM0(+d, +ne) be the class of such systems. 2.3 The Class PMCAM0(+d,+ne) Definition 2. We say that a decision problem X=(IX,θ X)is solvable in polynomial time by a family Π={Π(n): n∈N}of recognizing P systems from AM0(+d, +ne)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 Π(n)from n∈N. •There exists a pair (cod, s)of polynomial-time computable functions over IX such 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∈IXevery computation of Π(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∈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 to every P system Π(n)aconfluent condition, in the following sense: every computation of a system with the same input multiset must always give the same answer. The pair of functions (cod, s) is called a polynomial encoding of the problem in the family of P systems. We denote by PMCAM0(+d,+ne)the set of all decision problems which can be solved by means of recognizing polarizationless P systems using division of non-elementary membranes and dissolution in polynomial time. 3 Designing the Solution to Subset Sum In this section we address the resolution of the problem following a brute force algorithm, implemented in the framework of recognizing P systems from the AM0(+d, +ne) class. The idea of the design is better understood if we divide the solution to the problem into several stages: –Generation stage: for every subset of A, a membrane labeled by eis generated via membrane division. –Calculation stage: in each membrane the weight of the associated subset is calculated (using the auxiliary membranes e0,...,e n). –Checking stage: in each membrane it is checked whether the weight of its associated subset is exactly k(using the auxiliary membranes ch). –Output stage: the system sends out the answer to the environment, according to the result of the checking stage. Let us now present a family of recognizing P systems from the AM0(+d, +ne) class that solves Subset Sum, according to Definition 2. We shall use a tuple (n, (w1,...,w n),k) to represent an instance of the Subset Sum problem, where nstands for the size of A={a1,...,a n},wi=w(ai), and kis the constant given as input for the problem. Let g:N×N→Nbe a function defined by g(n, k)=(n+k)(n+k+1) 2+n This function is primitive recursive and bijective between N×Nand Nand computable in polynomial time. We define the polynomially computable function s(u)=g(n, k). We shall provide a family of P systems where each P system solves all the instances of the Subset Sum problem with the same size. Let us consider the binary decomposition of k,Σi∈I2i=k, where the indices i∈Iindicate the positions of the binary expression of kwhere a 1 occurs. Let I={1,...,logk} − I be the complementary set, that is, the positions where a 0 occurs. This binary encoding of k, together with the weight function wof the concrete instance, will be provided via an input multiset determined by the function cod as follows: cod(u)=cod1(u)∪cod2(u), where cod1(u)={{bwi i:1≤i≤n}} and cod2(u)={{cj:j∈I}}∪{{c j:j∈I}} Next, we shall provide a family Π={Π(g(n, k)) : n, k ∈N}of recognizing P systems which solve the Subset Sum problem in a number of steps being of O(n+logk) order. We shall indicate for each system of the family its initial configuration and its set of rules. We shall present the list of rules divided by groups, and we shall provide for each of them some comments about the way their rules work. Let us consider an arbitrary pair (n, k)∈N×N. The system Π(g(n, k)) is determined by the tuple (Γ,Σ, μ,M,R,i in,i 0), that is described next: •Alphabet: Γ=Σ∪{b+ i,b − i,b = i,d i,d + i,d − i,p i,q i:i=1,...,n} ∪{g0,...,g 2log k+2,h 0,...,h 2log k+2n+8,l 0,...,l 2log k+2n+10} ∪{v0,...,v 2log k+2n+12} ∪{w0,...,w 2log k+2n+18} ∪{x0,...,x 2log k+2n+15,z 0,...,z 2log k+2n+7} ∪{s, yes,no,Trash} •Input alphabet: Σ(n, k)={b1,...,b n,c 0,...,c log k,c  0,...,c  log k}. The initial configuration consists of n+log k+ 9 membranes, arranged as shown in Figure 1. Formally, the membrane structure μis [[[[[[ n ... [[[[[]ch ...[]ch]a1]a2]e0]e1n ...]en]a3[]c]a4]e]f]skin ••••• • • •••• • • skin f e a4a3 c ene1e0a2a1 ch ch . . . w0g0v0h0 x0 cod(u)z0 l0 l0   ...   @@ @ Fig. 1. Initial Configuration wherethereareexactlylogk+ 1 copies of membrane []ch. Roughly speaking (more precise explanations will be given for the rules), we can classify the membranes according to their role as follows: –n+2 membranes that take care of the generation stage, namely those labeled by e0,e 1,...e nand e. –logk+ 3 membranes that take care of preparing and implementing the checking stage, namely those labeled by ch,a1and a2. –4 membranes that take care of the answer stage, handling and synchronizing the results of the checking, namely those labeled by a3,a 4,c and f. •The initial multisets are: M(f)={{w0}};M(e)={{g0}};M(a4)={{v0}};M(a3)={{h0}}; M(c)={{x0}};M(a1)={{z0}};M(ch)={{l0}} M(skin)=M(a2)=M(e0)=···=M(en)=∅ •The input membrane is iin =e0, and the output region is the environment (i0=env). First task: generate kmembranes ch.At the beginning of the computation, kmembranes ch will be generated inside the innermost region of the structure. The strategy works as follows: 1. Initially, there are logkmembranes ch in the region a1, and the input multiset is located in region e0(recall that cod2(u) consists of log kobjects cior c irepresenting the binary encoding of k). 2. In the first log ksteps, the objects from cod2(u)getintomembranea2(the objects enter one by one membrane a2). Simultaneously, the counter ziis evolving inside membrane a1and dissolves it at the logkstep. 3. Thus, in the next step each element from cod2(u) will go inside a membrane ch (all objects go in parallel into different membranes in a one-to-one manner). 4. Objects c iwill dissolve the membranes where they enter, while each object ciwill generate by division 2imembranes ch. 5. After at most log kfurther steps all divisions have been completed, and the number of membranes ch is exactly k. Membrane a2will not be divided until the generation and weight calculation stages have been completed, acting as a separator between objects from cod1(u) and membranes ch. Set (A1). ci[]a2→[ci]a2 c i[]a2→[c i]a2 ci[]ch →[ci]ch c i[]ch →[c i]ch [c i]ch →Trash ⎫ ⎪ ⎪ ⎪ ⎪ ⎪ ⎬ ⎪ ⎪ ⎪ ⎪ ⎪ ⎭ for i∈{0,...,logk}. Set (A2). [c0→Trash]ch [ci]ch →[ci−1]ch [ci−1]ch for i=1,...,logk [zi→zi+1]a1for i=0,...,logk−1 [zlog k]a1→zlog k+1 [gi→gi+1]efor i=0,...,2logk+1 [g2log k+2 →d1s]e In the last step of this stage, the counter giproduces the objects d1and s which will trigger the beginning of the next stage. Set(B). [wi→wi+1]f [vi→vi+1]a4 [hi→hi+1]a3 [xi→xi+1]c [li→li+1]ch ⎫ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎬ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎭ for i∈{0,...,2logk+2}. [zi→zi+1]a2fori∈{logk+1,...,2logk+2}. The rest of the counters simply increase their indices in this stage. (See Fig. 2.) ••••• • • ••• • • skin f e a4a3 c ene1e0a ch ch . . . wβd1sv βhβ xβ cod1(u)zβ lβ lβ β=2log k+3   ...   @@ @ Fig. 2. Time 2log k+3 Second task: generate 2nmembranes e.Objects diresiding inside membrane(s) ewill produce nconsecutive divisions, thus yielding 2ncopies of membrane e. To each one of them, a subset of Ais associated in the following way: after each division, the membranes where object pioccurs correspond to subsets of Acontaining ai, and conversely, membranes where qioccurs will be associated with subsets not containing ai. Set (C). [di]e→[d+ i]e[d− i]efor i=1,...n [d+ i→pidi+1]efor i=1,...n−1 [d− i→qidi+1]efor i=1,...n−1 [d+ n→pn]e [d− n→qn]e Membrane divisions take place every two steps, so in the (2logk+2n+2)-th step there will be 2nmembranes e. Set (D). s[]ai→[s]aifor i=3,4 s[]ei→[s]eifor i=0,...,n [s]e0→Trash pj[]ai→[pj]aifor i=3,4j=1,...,n pj[]ei→[pj]eifor j=1,...,n i=j,...,n [pi→qi]eifor i=1,...,n qj[]ai→[qj]aifor i=3,4j=1,...,n qj[]ei→[qj]eifor j=1,...,n i=j,...,n [qi]ei→Trash for i=1,...,n While the divisions are being carried out, objects s,pjand qj,forj=1,...,n, travel into inner membranes (recall that whenever membrane egets divided, the internal nested structure of membranes eiis duplicated). In the (2logk+n+2)- th step, an object sarrives to every membrane e0. This object dissolves the membrane in the next step, and therefore in the (2logk+n+ 3)-th step we find inside every membrane e1the multiset cod1(u),andinthismomentthe weight calculation stage begins (see rules in Set (E)). As we said before, objects pjand qjare traveling into inner membranes, until they reach ej. This is done in such a way that in the (2logk+n+ 3)-th step there is in each membrane e1either an object p1or an object q1, in addition to the multiset cod1(u). Before going on, let us state two points. First, recall that in the input multiset, introduced in e0at the beginning of the computation, there are w(ai)copies of bi,fori=1,...,n. Second, let us note that objects qidissolve membrane ei immediately after arriving to it, while objects pitake two steps to dissolve membrane ei(first they are transformed into qiand in the next step the dissolution takes place).