On Descriptive Complexity of P Systems

On Descriptive Complexity of P Systems Miguel A. Guti´errez-Naranjo, Mario J. P´erez-Jim´enez, and Agustin 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 {magutier, marper, ariscosn}@us.es Abstract. In this paper we address the problem of describing the complexity of the evolution of a P system. This issue is is specially hard in the case of P systems with active membranes, where the number of steps of a computation is not sufficient to evaluate the complexity. Sevilla carpets were introduced in [1], and they describe the space-time complexity of P systems. Based on them, we define some new parameters which can be used to compare evolutions of P systems. To illustrate this, we also include two different cellular solutions to the Subset Sum problem and compare them via these new parameters. 1 Introduction The evolution of a P system is a complex process where (possibly) a large number of symbol-objects, membranes and rules are involved. In the case of P systems with active membranes, the problem of describing the complexity of the computational process becomes specially hard. In this case, elementary membranes can divide into two new membranes and, due to the parallelism intrinsic to P systems, an exponential number of membranes can be obtained in polynomial time. This feature makes P systems with active membranes a powerful tool to attack NP-complete problems and, indeed, several efficient solutions to this type of problems have been presented (see, e.g., [4, 9, 10, 11] or [12]). These solutions are proposed in the framework of recognizer P systems with external output, and they present significant similarities among them. The basic idea in these designs is the creation of an exponential number of membranes (workspace) in polynomial time and the use of each membrane as an independent computational device. All membranes evolve in parallel and the computation has a polynomial cost in time. The process ends with a final stage (with polynomial cost) that checks the answers of these devices and sends an output to the environment. The complexity in time (the number of cellular steps) of these solutions is polynomial, but it is clear that the time is not the unique variable that we need to consider in order to evaluate the complexity of the process. Ciobanu, P˘aun and ¸Stef˘anescu presented in [1] a new way to describe the complexity of a computation in a P system. The so-called Sevilla carpet is an extension of the notion of Szilard language from grammars to the case when several rules are used at the same time. In this paper we make use of Sevilla carpets to describe the computations of P systems that solve the Subset Sum problem. Two families of recognizer P systems have been designed that need a polynomial time to send an output to the environment. We present their corresponding Sevilla carpets in order to compare them, and then some ideas to improve the design of P systems for solving other new problems are proposed. The paper is organized as follows. In Section 2 we first give some preliminary notions about recognizer P systems and a polynomial complexity class on P systems is defined. Section 3 presents the Sevilla carpets and some new parameters related with them are introduced in Section 4. Finally, we use these parameters to compare two solutions of the Subset Sum problem. 2 Preliminaries Roughly speaking, a P system consists of a cell-like membrane structure, in the compartments of which one places multisets of objects which evolve according to given rules in a synchronous non-deterministic maximally parallel manner. Definition 1. AP system with input is a tuple (Π,Σ,iΠ), where: ΠisaP 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 Γ−Σ; finally, iΠis the label of a distinguished (input) membrane. The computations of a P system with input a multiset mover Σ, are defined in a natural way. The only novelty is that the initial configuration must be the initial configuration of the system to which the input multiset mis added to the multiset from region iΠ. 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 Π.Letmbe a multiset over Σ. The initial configuration of (Π,Σ,iΠ) with input mis (µ, M1,...,MiΠ∪m,...,Mp). In the case of P systems with input and with external output, the concept of computation is as standard in membrane computing, with a minor difference which will be explained below. We consider that it is not possible to observe the internal processes inside the P system and we can only know if the computation has halted via some distinguished objects sent out of the skin. We can formalize these ideas in the following way. 2.1 Recognizer P Systems Recall that a decision problem Xis 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. In order to solve decision problems we need P systems with input such that all halting computations starting from an initial configuration with a given input multiset (encoding an instance of the problem) produce the same output. The systems of this type will be called recognizer P systems. Definition 3. Arecognizer P system is a P system with input, (Π,Σ,iΠ), and with external output such that: 1. The working alphabet contains two distinguished elements YES, NO. 2. All computations halt. 3. If Cis a computation of Π, then either object YES or 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 environment associated with the corresponding halting configuration of C. The above definitions are stated in a general way, but in this paper P systems with active membranes will be used. We refer to [8] (see chapter 7) for a detailed definition of evolution rules, transition steps, configurations and computations in this model. We denote by AM the class of all recognizer P systems with active membranes. 2.2 The Computational Complexity Class PMCF 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 (see e.g. [7] or [14]). 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 shortcoming can be easily overtaken if we consider a P system with input. Then, a 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. Definition 4. Let Fbe a class of recognizer P systems. We say that a decision problem X=(IX,θ X)is solvable in polynomial time by a family Π= (Π(n))n∈N+of type F, and we denote this by X∈PMCF, if the following is true: –The family Πis polynomially uniform by Turing machines; that is, there exists a deterministic Turing machine constructing Π(n)from n∈N+in polynomial time. –There exists a pair (g,h)of polynomial-time computable functions g:L→ n∈N+IΠ(n)and h:L→N+such that for every u∈Lwe have g(u)∈IΠ(h(u)), and •The family Πis polynomially bounded with regard to (g,h); that is, there exists a polynomial function p, such that for each u∈IXevery computation of Π(h(u)) with input g(u)is halting and, moreover, it performs at most p(|u|)steps. •The family Πis sound, with regard to (X,g,h); that is, for each u∈IX it is verified that if there exists an accepting computation of Π(h(u)) with input g(u), then θX(u)=1. •The family Πis complete, with regard to (X, g, h); that is, for each u∈ IXit is verified that if θX(u)=1, then every computation of Π(h(u)) with input g(u)is an accepting one. In the above definition we have imposed every P system Π(n)tobeconfluent,in the following sense: every computation with the same input produces the same output. From the dfinition, one can easily prove that the class PMCFis closed under polynomial–time reduction and complement. 3 Sevilla Carpets Sevilla carpets were presented in [1] as an extension of the Szilard language, which consists of all strings of rule labels describing correct derivations in a given grammar (see, e.g., [5, 6] or [13]). The Szilard language is usually defined for grammars in the Chomsky hierarchy where only a single rule is used in each derivation step, so a derivation can be represented as the string of the labels of the rules used in the derivation (the labelling is supposed to be one-to-one). Sevilla carpets are a Szilard-way to describe a computation in a P system. The main difference is that now a multiset of rules can be used in each evolution step of a P system. In [1] a bidimensional writing is proposed to describe a computation of a P system. The (Sevilla) carpet associated with a computation of a P system is a table with the time on the horizontal axis and the rules explicitly mentioned along the vertical axis; then, for each rule, in each step, a piece of information is given. Depending on the amount of information given to describe the evolution, Ciobanu, P˘aun, and S¸tef˘anescu propose five variants for the Sevilla carpets: 1. Specifying in each time unit for each membrane whether at least one rule was used in its region or not. 2. Specifying in each time unit for each rule whether it was used or not. 3. Mentioning in each time unit the number of applications of each rule; this is 0 when the rule is not used and can be arbitrarily large when the rules are dealing with arbitrarily large multisets. 4. We can also distinguish three cases: that a rule cannot be used, that a rule can be used but it is not because of the nondeterministic choice, and that a rule is actually used. 5. A further possibility is to assign a cost to each rule, and to multiply the number of times a rule is used with its cost. They also propose two parameters (weight and surface) to study Sevilla carpets. In this paper we popose two new parameters (height and average weight) that will be described in the next section. 4 Parameters for the Descriptive Complexity Many times we are not interested only in the number of cellular steps of the computation, but also in other types of resources required to perform the computation. Especially if we want to implement in silico a P system, we need to be careful with the number of times that a rule is applied, maybe with the number of membranes and/or the number of objects present in a given configuration. In order to describe the complexity of the computation, the following parameters are proposed: – Weight: It is defined in [1] as the sum of all the elements in the carpet, i.e., as the total number of applications of rules along the computation. The application of a rule has a cost and the weight measures the total cost of the computation. – Surface: This is the multiplication of the number of steps by the total number of the rules used by the P system. It can be considered as the potential size of the computation. From a computational point of view we are not only interested in P systems which halt in a small number of steps, but in P systems which use a small amount of resources. The surface measures the resources used in the design of the P system. Graphically, it represents the surface where the Sevilla carpet lies on. – Height: This is the maximum number of applications of any rule in a step along the computation. Graphically, it represents the highest point reached by the Sevilla carpet. – Average Weight: It is calculated by dividing the weight to the surface of the Sevilla carpet. This concept provides a relation between both parameters, and gives an indication on how the P system exploits its massive parallelism. 5 Comparing Two Solutions to the Subset Sum Problem The Subset Sum problem is the following one: Given a finite set A, a weight function, w:A→N, and a constant k∈N, determine whether or not there exists a subset B⊆Asuch that w(B)=k. We will use a tuple (n, (w1,...,w n),k) to represent an instance of the problem, where nstands for the size of A={a1,...,a n},wi=w(ai), and kis the constant given as input for the problem. We propose here two solutions to this problem based on a brute force algorithm implemented in the framework of P systems with active membranes. 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 is generated via membrane division. –Weight calculation stage: in each membrane the weight of the associated subset is calculated. This stage will take place in parallel with the previous one. –Checking stage: in each membrane it is checked whether or not the weight of its associated subset is exactly k. This stage cannot start in a membrane before the previous ones are over in that membrane. –Output stage: when the previous stage has been completed in all membranes, the system sends out the answer to the environment. First Design Next we present a family of recognizer P systems solving Subset Sum, according to Definition 4. This family can be found in [9]. First, we consider a polynomial–time computable and bijective function from N2onto N(for example, x, y=((x+y)(x+y+1)/2)+y). For each (n, k)∈N2 we consider the P system (Π1(n, k),Σ(n, k),i(n, k)), where the input alphabet is Σ(n, k)={x1,...,x n}, the input membrane is i(n, k)=eand Π1(n, k)= (Γ(n, k),{e, s},µ,Me,Ms,R) is defined as follows: •Alphabet: Γ(n, k)=Σ(n, k)∪{¯a0,¯a, a0,a,d +,e 0,...,e n,q,q 0,...,q 2k+1, z0,...,z 2n+2k+2, Y es, no, No, #}. •membrane structure: µ=[[] e]s. •Initial multisets: Ms=z0;Me=e0¯ak. •The set Rof evolution rules consists of the following rules: (a)[ei]0 e→[q]− e[ei]+ e,for i=0,...,n. [ei]+ e→[ei+1]0 e[ei+1]+ e,for i=0,...,n−1. (b)[x0→¯a0]0 e;[x0→λ]+ e;[xi→xi−1]+ e,for i=1,...,n. (c)[q→q0]− e;[¯a0→a0]− e;[¯a→a]− e. (d)[a0]− e→[] 0 e#; [a]0 e→[] − e#. (e)[q2j→q2j+1]− e, for j=0,...,k. [q2j+1 →q2j+2]0 e, for j=0,...,k−1. (f)[q2k+1]− e→[] 0 eYes;[q2k+1]0 e→[] 0 e#. [q2j+1]− e→[] − e#,for j=0,...,k−1. (g)[zi→zi+1]0 s,for i=0,...,2n+2k+1; [z2n+2k+2 →d+no]0 s. (h)[d+]0 s→[] + sd+;[no →No]+ s;[Yes]+ s→[] 0 sYes;[No]+ s→[] 0 sNo. Let us recall that the instance u=(n, (w1,...,w n),k) is processed by the P system Π1(n, k) with input the multiset xw1 1xw2 2...x wn n. This design depends on the two constants that are given as input in the problem: nand k. It consists on 5n+5k+18 evolution rules, and if an apropriate input multiset is introduced inside membrane ebefore starting the computation, the system will stop and output an answer in 2n+2k+ 6 steps (if the answer is No)orin2n+2k+ 5 steps (if the answer is Yes). According to Definition 4 and using the above family of P systems, we can prove that, Subset Sum ∈PMCAM (see [9], for details). Second Design Next we present a new family of recognizer P systems solving Subset Sum, inspired in the previous one. Some modifications are made following the design presented in [3]. For each n∈Nwe consider the P system (Π2(n),Σ(n),i(n)), where the input alphabet is Σ(n)={x1,...,x n}, the input membrane is i(n)=eand Π2(n)=(Γ(n),{e, r, s},µ,Me,Mr,Ms,R) is defined as follows: •Alphabet: Γ(n)=Σ(n)∪{¯a0,¯a, a0,a,c,d 0,d 1,d 2,e 0,...,e n,g,¯g, ˆg,h0,h 1, q,q0,q 1,q 2,q 3, Y es, No, no, z0,...,z 2n+1,#}. •Membrane structure: µ=[[] e]s. •Initial multisets: Ms=z0;Me=e0g¯ak;Mr=h0b. •The set Rof evolution rules consists of the following rules: (a)[ei]0 e→[q]− e[ei]+ e,for i=0,...,n. [ei]+ e→[ei+1]0 e[ei+1]+ e,for i=0,...,n−1. (b)[x0→¯a0]0 e;[x0→λ]+ e;[xi→xi−1]+ e,for i=1,...,n. (c)[q→q0]− e;[¯a0→a0]− e;[¯a→a]− e. [g]− e→[] − e¯g. [en]+ e→#. [¯a0→λ]0 s;[¯a→λ]0 s;[g→λ]0 s. [a→λ]+ e;[a0→λ]+ e. (d)[a0]− e→[] 0 e#; [a]0 e→[] − e#. (e)[q0→q1]− e;[q1→q0]0 e. [q0]0 e→[] + eno. [q1→q2c]− e;[q2→q3]0 e;[c]− e→[] 0 ek. (f)[q3]0 e→[] + eYes;[q3]− e→[] + eno. (g)[zi→zi+1]0 s,for i=0,...,2n;[z2n+1 →d0d1]0 s. d0[] 0 r→[d0]− r;[d1]0 s→[] + sd1. (det)[h0→h1]− r,[h1→h0]+ r, [b]− r→[] + rb,ˆg[] + r→[ˆg]− r, b[] − r→[b]+ r,[ˆg]+ r→[] − rˆg, [h0]+ r→[] + rd2,[d2]+ s→[] − sd2. (h)[ no →No]− s;[Yes]− s→[] 0 sYes;[No]− s→[] 0 sNo. In this solution the instance u=(n, (w1,...,w n),k) is processed by the P system Π2(n) with input the multiset xw1 1xw2 2...x wn n. The above design depends only on one of the constants that are given as input in the problem: n. It is quite similar to the previous one, the difference lies in the checking stage and the answer stage. In this case we avoid the use of counters that require knowing the constant k. The number of evolution rules is 5n+ 41, and the number of steps of the computation depends on the concrete instance that we need to solve, but it is linearly bounded. Descriptive Complexity We present some detailed statistics about the previous designs, trying to compare them on a more general basis than just looking the number of steps that the computation performs. Following this scheme, we present the Sevilla carpets associated with the computations of the two different solutions to the Subset Sum problem working on the same instance: u=(5,(3,5,3,2,5),9). That is, n=5,k= 9, and the list of weights is w1=3,w 2=5,w 3=3,w 4=2,w 5=5. The input multiset is then: x3 1x5 2x3 3x2 4x5 5. 0 10 20 30 40 50 60 70 80 90 Rules 0510 15 20 25 30 35 Steps Fig. 1. Sevilla carpet for solution 1 The P system Π1(5,9) has 88 evolution rules, and all of them are applied with the exception of the rules: [q19]− e→[] 0 eYes,[q3]− e→[] − e#, [q9]− e→[] − e# and [Yes]− s→[] 0 sYes. The P system Π1(5,9) stops at step 33 and sends an object No to the environment. The weight of the Sevilla carpet (the total number of rule applications along the computation) is 2179, and its height (the maximal number of times that a rule is applied in one evolution step) is 82 and it is reached at Step 9 by the rule [¯a0→a0]− e. The surface of the Sevilla carpet is 2904, and its average weight is 0.749656 010203040506070 Rules 0510 15 20 25 30 35 40 Steps Fig. 2. Sevilla carpet for solution 2 The P system Π2(5) has 65 evolution rules, and all of them are applied with the exception of the rules: [q3]0 e→[] + eYesand [Yes]− s→[] 0 sYes. The P system Π2(5) stops at step 38 and sends an object No to the environment. The weight of the Sevilla carpet is 3368, and its height is 108, this height is reached at Step 10 by the rule [¯a0→λ]0 s. The surface of the Sevilla carpet is 2470, and its average weight is 1.36275 The following table shows the parameters of both solutions: Solution 1 Solution 2 Rules 88 65 Steps 33 38 Surface 2904 2470 Weight 2179 3368 Height 82 108 Average Weight 0.749656 1.36275 If we consider the number of steps as a complexity measure to compare both designs, then we conclude that the first solution is better than the second one (although not asymptotically), since it needs less steps. Moreover, concerning the weight of the Sevilla carpet, solution 1 is again better than solution 2, because it uses less resources during the computation. However, the fact that the average weight of solution 2 is larger than the average weight of solution 1 can be interpreted by saying that the second design makes a better use of the parallelism in P systems (the computation is more intense). We would like to remark that these are not asymptotical comparisons, as we focus only on the data corresponding to one instance. Indeed, due to the exponential number of membranes created during the generation stage, we believe that considering another instance with a greater size will stress the differences between the design based only on nand the other one, based on both nand k. The bound on the size of the intances that can be studied is imposed by the