Computationally Hard Problems Addressed Through P Systems

Computationally Hard Problems Addressed Through P Systems Mario J. P´erez-Jim´enez, Alvaro Romero-Jim´enez, Fernando Sancho-Caparrini Department Computer Science and Artificial Intelligence E.T.S. Ingenier´ıa Inform´atica, University of Seville Avda. Reina Mercedes s/n, 41012 Sevilla, Spain {Mario.Perez,Alvaro.Romero,Fernando.Sancho}@cs.us.es Summary. In this chapter we present a general framework to provide efficient solutions to decision problems through families of cell-like membrane systems constructed in a semi-uniform way (associating with each instance of the problem one P system solving it) or a uniform way (all instances of a decision problem having the same size are processed by the same system). We also show a brief compendium of efficient semi-uniform and uniform solutions to hard problems in these systems, and we explicitly describe some of these solutions. 1 Introduction Many interesting problems of the real world are presumably intractable (unless P = NP) and hence it is not possible to obtain algorithmic solutions when we address large instances of those problems on an electronic computer. From this point of view, membrane systems have two attractive features: they are inherently parallel and nondeterministic. Can the parallelism and nondeterminism of P systems be used to solve hard problems in feasible time? The answer is yes, but we must point out two facts. On the one hand, we have to deal with the nondeterminism in such a way that the solutions obtained by using these devices are algorithmic solutions in the classical sense, that is, the answers of the computations of the system must be reliable. On the other hand, the drastic decrease of the execution time from exponential to polynomial is not achieved for free, but with the use of an exponential amount of space, although this space is created in polynomial time. In this chapter we present the theoretical requirements for a P system to provide an algorithmic solution to an abstract decision problem (a precise definition of the latter is given in Section 2). First, all computations of the system must halt, providing a positive or negative answer to the problem (i.e., for a particular instance of it). Second, we impose that the systems be confluent. This is a generalization of the notion of determinism for which we require all possible computations to provide the same answer. This way we do not obtain a contradictory result. In Section 3, P systems verifying these two properties are called recognizer systems. It is important to note that all the feasible solutions to hard problems obtained by means of these biologically inspired devices so far presented do not use a single P system, but a family of systems. However, there are significative differences between those solutions, dividing them in two groups: the semiuniform solutions, which associate with each instance of the problem one P system solving it, and the uniform solutions, which associate with each possible size of the instances of the problem one P system that can solve all instances of that size. A formal definition of these two concepts can be found in Sections 4 and 5. Another possible classification can be considered with respect to the existence or not in the system of a membrane where the input data is introduced before the computation starts. Usually, the semi-uniform solutions are performed by P systems without input, whereas the uniform solutions are performed by P systems with input. In Section 4 we present a compendium of known semi-uniform solutions to hard problems by P systems without input, and a detailed description of two of these solutions: one to the Satisfiability Problem and the other to the Hamiltonian Path Problem. Finally, in Section 5 we do the same for known uniform solutions to hard problems by P systems with input, detailing the ones corresponding to the Decision Knapsack Problem (0/1) and to the Common Algorithmic Decision Problem. 2 Abstract Problems Membrane systems provide devices with the ability to solve problems. But these machines are equipped only with tools able to handle inputs and outputs that are multisets of symbol objects. Hence, we are forced to treat these problems as collections of multisets. In general we define an abstract problem Xto be a pair X=(IX,S X) where IXis a language over a finite alphabet, whose elements are called instances of the problem, SXis a function whose domain is IX,andforany instance i∈IX,thesetSX(i) is finite (the elements of this set are called candidate solutions). Observe that the set of instances of an abstract problem is a finite or enumerable set. As an example, consider the problem MAX-CLIQUE of finding a largest clique in a given unidirected graph. Recall that a clique in a graph is a set of vertices such that their each pair is connected by an edge. An instance of MAX-CLIQUE is an undirected graph, and a candidate solution is a set of vertices. An exact solution will be a set of vertices which is a clique with the maximal number of vertices. The problem MAX-CLIQUE itself is the relation that associates each undirected graph with each largest cliques in the graph (an exact solution). Since largest cliques in an uniderected graph are not necessarily unique, a given problem instance may have more than one exact solution; that is, the binary relation associated with the problem is not necessarily univocal. In this chapter we will work only with decision problems, that is, abstracts problems that require either a yes or a no answer. Formally, a decision problem Xis an abstract problem (IX,S X) such that SXis a total boolean function (that is, a predicate) over IX. For example, the following is a decision version of the problem CLIQUE: given an undirected graph Gand a natural number k, determine whether or not Ghas a clique of size at least k. An instance for CLIQUE is a pair (G, k) where Gis an undirected graph and kis a natural number, and a candidate solution is 1 (yes)or0(no). If i=(G, k) is an instance of this problem, then SCLIQUE(i)=1(yes) if there exists a clique in Gof size at least k,and SCLIQUE(i)=0(no)otherwise. There exists a natural correspondence between languages and decision problems in the following way: each language Lover an alphabet Σhas a decision problem, XL=(IXL,S XL), associated with it, where IXL=Σand SXL={(x, 1) |x∈L}∪{(x, 0) |x/∈L}; reciprocally, given a decision problem X=(IX,S X), the language LXover IXcorresponding to it is defined as LX={a∈IX|SX(a)=1}. Let Mbe a Turing machine such that the result of any halting computation is yes or no.LetLbe a language over an alphabet Σ.IfMis a deterministic device then we say that Mrecognizes or decides Lwhenever, for any string a over Σ,ifa∈Lthen the answer of Mon input ais yes,andno otherwise. If Mis a nondeterministic Turing machine, then we say that Mrecognizes or decides Lif the following is true: for any string aover Σ,a∈Lif and only if there exists a computation of Mwith input asuch that the answer is yes. That is, an input string ais accepted if there is some accepting computation of Mon input a. Notice the difference in the definition of acceptance by deterministic and nondeterministic Turing machines. An input string ais accepted by a deterministic Turing machine Mif the computation of Mon input ahalts and answers yes. A nondeterministic Turing machine Maccepts a string aif there exists some computation of Mon input aanswering yes; that is, there exists a sequence of nondeterministic choices that results in yes. In this case, it is possible that we accept a string but that there exists another computation with the same input that either halts and answers no,ordoesnothalt. In some sense, we can state that nondeterministic devices do not properly capture the intuitive idea underlying the concept of algorithm, because the result of such a machine on an input is not reliable, since the answer of the device is not always the same. In the context of computability theory, we consider a problem Xto be solved when we have a general method (described in a model of computation) that works for any instance of the problem. From a practical point of view, such methods run only over a finite set of instances whose cardinality depends on the available resources. We say that a Turing machine Msolves a decision problem Xif Mrecognizes the language associated with X; that is, for any instance aof the problem: (a) in the deterministic case, the machine (with input a) outputs yes if the answer of the problem is yes, and outputs no otherwise, and (b) in the nondeterministic case, some computation of the machine (with input a) outputs yes if the answer of the problem is yes. As for when the instances of abstract problems are strings, we can consider their size in a natural manner: the size of an instance is the length of the string. Then, how do the resources required to execute a method increase according to the size of the instance? This is a fundamental question in computational complexity theory. Let Mbe a deterministic Turing machine. Let Rbe a resource used by the device (for example, the number of steps executed before the machine halts, the time of execution). We consider a function fRmapping nonnegative integers to nonnegative integers defined as follows: fR(n) is the maximum, over all instances aof size n, of the amount of resource Rused when the device Mis executed with input a. For example, if Ris the time of execution, then we say that Moperates in time fR(n); if fRturns to be a polynomial function, then we say that Mworks in polynomial time. 3 Recognizer P Systems In this chapter we use membrane computing as a framework to address the resolution of decision problems; that is why we consider P systems as recognizer devices. Since P systems work in a nondeterministic manner, we need to adapt the usual definition of the processes of acceptance in nondeterministic Turing machines. In order to accept or reject an input string/multiset it should be enough to read the answer of any computation of the system. Hence it is necessary to require a condition of confluence in the following sense: every computation of the system is a halting computation, and (on the same input, if any) all computations have the same output. Definition 1. Arecognizer P system is a P system with external output such that: 1. The working alphabet contains two distinguished elements yes and no. 2. All computations halt. 3. If Cis a computation of the system, then either some object yes or some object no (but not both) must have been released into the environment, and only in the last step of the computation. For recognizer P systems, we say that a computation Cis an accepting computation (or rejecting computation) if the object yes (or no)appearsinthe external environment associated with the corresponding halting configuration of C. Hence, these devices send to the environment an accepting or rejecting answer at the end of their computations. Therefore, if we want these kinds of systems to properly solve decision problems, we have to require all responses to be consistent, in the sense that the system must always give the same answer. 4 Recognizer P Systems Without Input The first results about solvability of NP-complete problems in polynomial (even linear) time by membrane systems were given by Gh. P˘aun [24], C. Zandron et al. [40], S.N. Krishna et al. [10], and A. Obtulowicz [15] in the framework 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. This method for solving problems provides a specific algorithmic solution, in the following sense: if we wanted to apply such a method to some decision problem then a system should be constructed for every instance of the problem. However, the construction is done in polynomial time, which prevents the solving of the problem during the “programming” phase. Now, we formalize these ideas in the following definition. Definition 2. Let X=(IX,θ X)be a decision problem. We say that Xis solvable in polynomial time by a family of recognizer membrane systems without input Π=(Π(w))w∈IXif the following are true: •The family Πis “Turing polynomially uniform”; that is, there exists a deterministic Turing machine which, in polynomial time, constructs the system Π(w)starting from the instance w∈IX. •The family Πis polynomially bounded; that is, there exists a polynomial function p(n)such that for each w∈IX, every computation of Π(w)halts in at most p(|w|)steps. •The family Πis sound; that is, for each instance of the problem w∈IX, if there exists an accepting computation of Π(w),thenθX(w)=1(the corresponding answer of the problem is yes). •The family Πis complete; that is, for each instance of the problem w∈IX, if θX(w)=1(the answer to the problem is yes), then every computation of Π(w)is an accepting computation (the system also responds yes). The soundness property means that if we obtain an acceptance response of the system (associated with an instance) through some computation, then the answer to the problem (for that instance) has to be yes. The completeness property means that if we obtain an affirmative response to the problem, then any computation of the system must be an accepting one. Notice that in the above definition we consider two different tasks. The first one is the construction of the family solving the problem, which we require to be done in polynomial time; that is, there exists a deterministic Turing machine M, and a polynomial function q(n) such that for each w∈IX,M(w) provides a complete description of the system Π(w)inatmostq(|w|)steps. This is precomputation time, expressed in the number of sequential steps. The second task is the execution of the systems Π(w) of the family, and for this task we impose that the total number of steps performed by the computations of system Π(w) is bounded by the polynomial function p(n). This is the real computation time, and it is described by the number of parallel steps. In this section we use recognizer membrane systems without input membrane in order to solve decision problems. In this context, we need to associate with each instance of the problem such a system, accepting or rejecting it. Bearing in mind the nondeterminism of the system, we require the confluence condition; that is, all branches of a computation associated with the instance eventually reach a unique configuration. Unless P=NP, to solve an NP-complete problem in an efficient way using P systems we have to create an exponential workspace in polynomial time. This is possible in various types of membrane systems, for example, through membrane division [24] (we can repeatedly divide membranes in order to obtain 2nmembranes in nsteps), membrane creation [9], [13] (new membranes are produced under the influence of the existing objects in a membrane), string replication [4] (in a rewriting membrane system using string objects we can generate exponentially many strings in linear time), or by using precomputed resources [25], [6] (we start from an arbitrarily large initial membrane structure, without objects placed in its regions, and we trigger a computation by introducing both objects and rules related to a given problem in a specified membrane). In [23] Gh. P˘aun explains the convenience of solving many NP-complete problems in a uniform manner, that is, with P systems which are very similar to each other. This idea about the uniformity of the P systems able to solve a decision problem was formulated for the first time by A. Obtulowicz [17] in relation to a proposed solution to SAT: the family of P systems (without input membrane) described in [24] is generated in a logarithmic space by a multitape deterministic Turing machine. We say that this construction is semi-uniform: the systems of the family solving the decision problem are constructed starting not from the size of an instance, but from an instance only; that is, in a recursive manner, for each instance of the problem a P system associated with it is constructed. In contrast, in Section 5 we will define the concept of uniform construction of families of P systems solving a decision problem. Now, we briefly comment the different efficient solutions of NP-complete problems in the framework of P systems without input, described in a semiuniform way, proposed until now. The first efficient solution to SAT is given by Gh. P˘aun in [24], using division for non-elementary membranes. This result was improved by Gh. P˘aun, Y. Suzuki, H. Tanaka, and T. Yokomori in [29] using only division for elementary membranes (in that paper a solution to HPP using membrane creation is also presented). In [2], A. Alhazov and T.O. Ishdorj present a linear time solution to SAT through P systems with active membranes without polarizations but using some membrane rules (merging, separation, and release). The first efficient solution to HPP by P systems is due to S.N. Krishna and R. Rama [10], but using rules for d-division, with an arbitrary d(a solution to Vertex Cover is also provided in this paper). The result of S.N. Krishna and R. Rama about HPP was improved by A. P˘aun in [21] by using only rules for 2-division. Different efficient solutions to several variants of SAT (3-SAT,Not-all-equal 3SAT,One-in-three 3SAT,andMinimum 2-satisfiability) are decribed by Gh. P˘aun, Y. Suzuki, H. Tanaka, and T. Yokomori in [29]. Also, in that paper solutions to several problems of graph theory (Vertex Cover,k-closure,Independent set,Graph 3-colourability,andMonochromatic triangle)aregivenby P systems with active membranes using cooperative rules. Other efficient solutions to SAT and HPP are given by J. Castellanos et al. [4], through P systems using string replications (similar solutions are given by S.N. Krishna and R. Rama in [11]), and by E. Czeizler [6], through P systems using precomputed resources. A polynomial solution to Integer Factorization Problem is presented by A. Obtulowicz in [16] through deterministic P systems with active membranes but using cooperative rules. P. Sosik in [39] provides a semi-uniform efficient solution to QBF (satisfiability of quantified propositional formulas), a well known PSPACE-complete problem in the framework of P systems with active membranes but using 2-division for nonelementary membranes. S.N. Krishna and R. Rama [12] show how P systems with membrane division can theoretically break the most widely used cryptosystem, DES. That is, given an arbitrary (plain text, cipher text) pair, one can recover the DES key in linear time with respect to the length of the key. In this section we present a semi-uniform solution to SAT problem due to C. Zandron, G. Mauri, and C. Ferretti [41] (with slight modifications the above solution can be adapted to a linear time solution by recognizer P systems, as we point out at the end of subsection 4.1). We also describe a quadratic time semi-uniform solution to the Hamiltonian Path Problem, a variant of a solution presented by M.J. P´erez-Jim´enez, A. Romero-Jim´enez, and F. Sancho- Caparrini in [35]. 4.1 A Linear Time Solution to SAT The Satisfiability Problem (SAT) is the following decision problem: Given a propositional formula in conjunctive normal form, determine if there exists a truth assignment of its variables which makes the formula true. In what follows we present a family of P systems with active membranes using 2-division that solves SAT in linear time. Given an instance φof SAT we construct a P system Π(φ) whose functioning can be divided into the following stages: (a) Generate all the possible truth assignments for the variables of φ.(This will be done in a nondeterministic way.) (b) Apply the assignments generated in the previous stage to the formula. (c) Check if all the clauses have value true. (d) Answer yes or no depending on the results from (c). Let us suppose that φis a formula with mclauses and nvariables. That is, φ=C1∧···∧Cmfor some m≥1, with Ci=yi,1∨···∨yi,pifor some pi≥1andyi,j ∈{xk,¬xk|1≤k≤n},foreach1≤i≤m, 1≤j≤pi. The P system Π(φ) is defined as follows. •The working alphabet is Γ(φ)={ai,t i,f i|1≤i≤n}∪{ri|0≤i≤m} ∪{ci|1≤i≤m−1}∪{di|0≤i≤n}∪{yes}. •The set of labels is {1,2}. •The initial membrane structure is [1[2]0 2]0 1(each membrane with label 2 is said to be an internal membrane). •The initial multisets associated with the membranes are M1=λand M2=a1a2...a nd0. •The rules are: (a.1) [2ai]0 2→[2ti]0 2[2fi]0 2,for1≤i≤n, (a.2) [2dk→dk+1]0 2,for0≤k≤n−2, (a.3) [2dn−1→dnc]0 2, (a.4) [2dn]0 2→[2]+ 2dn, (b.1) [2ti→rhi,1...r hi,ji]+ 2,for1≤i≤n, and the clauses Chi,1,...,C hi,ji contain the literal xi, (b.2) [2fi→rhi,1...r hi,ji]+ 2,for1≤i≤n, and the clauses Chi,1,...,C hi,ji contain the literal ¬xi, (c.1) [2r1]+ 2→[2]− 2r1, (c.2) [2ci→ci+1]− 2,for1≤i≤m, (c.3) [2rk→rk−1]− 2,for2≤k≤m, (c.4) r1[2]− 2→[2r0]+ 2, (c.5) [2cm+1]+ 2→[2]+ 2yes, (d.1) [1yes]0 1→[1]0 1yes. Let us see now that this P system indeed solves SAT for the formula φ. The objects aicontained in the initial internal membrane of the system correspond to the variables xi. By using a rule from (a.1), for inondeterministically chosen, we produce the truth values true and false assigned to variable xi. The truth values are represented by the objects tiand fi, respectively, and are placed in two separate copies of the internal membrane. Since the charge remains neutral for both membranes, the process can continue. In this way, in nsteps we assign truth values to all variables. Hence, we get all the 2ndifferent truth assignments for the formula φ, placed in 2nseparate internal membranes, which, in turn, are placed in the skin membrane. Note that, in spite of the fact that in each step the object aiis nondeterministically chosen, after nsteps we get the same result, regardless of the objects used in each step. On the other hand, the objects diare used as counters, to control when the process described above has finished. The initial internal membrane starts with the object d0and at each division step we pass from dkto dk+1 using the rules from (a.2). Also, each new internal membrane created by division gets copies of these objects, keeping their own counter this way. At the step before the last division, the rule from (a.3) introduces both dnand c1.The former object will exit the membrane (at step n+1 using the rule from (a.4)), changing its polarization to positive, and this finishes the first stage and starts the second one in that membrane. The latter object will be used in the third stage. In the second stage we look for the clauses satisfied by the truth assignments associated with each internal membrane. We do this in one step in parallel for all the 2nmembranes and in parallel for all the truth values present in them, using the rules from (b.1) and (b.2). These rules introduce an object ri in the membrane for each clause satisfied by the truth value being considered. If, after completing this step, there is at least one internal membrane which contains all symbols r1,...,r m, this means that the truth assignment associated with that membrane satisfies all the clauses, and therefore satisfies the formula φ. Otherwise, if no internal membrane gets all the objects r1,...,r m, the formula φis not satisfiable. Note that the satisfiability problem has already been solved, in n+ 2 steps, making an essential use of the parallelism, but we still have to “read” the answer and send a suitable signal out of the system. We use the rules from (c.1–4) in the third stage to check if some internal membrane has an associated truth assignment that makes true all the clauses Π(s(w)). This is a precomputation stage, running in polynomial time represented by the number of sequential steps. Next, we execute the system Π(s(w)) with input cod(w). This is the proper computation stage, also running in polynomial time, but now the time is represented by the number of parallel steps. Consequently, in order to solve a decision problem in this context, we need two polynomial time computable functions over the set of instances of the problem, in such a way that the first function assigns the P system that will process the instance when we give a suitable input provided by the second function. Then the system will accept or reject the instance. Bearing in mind the nondeterminism of the system, we require the confluence condition; that is, all computations of the system associated with the instance must always have the same answer. Now, we briefly comment on the different efficient solutions of NP- complete problems obtained in the framework of P systems with input, described in a uniform way, so far proposed. Unless stated otherwise, the solutions cited are described in the usual framework of P systems with active membranes using 2-division, with three electrical charges, without change of membrane labels, without cooperation, and without priority. M.J. P´erez-Jim´enez, A. Romero-Jim´enez, and F. Sancho-Caparrini present in [34] a linear time solution to SAT in a semi-uniform manner but in such a way that we can easily decribe that solution in an uniform manner (see [35]). Other interesting uniform linear time solutions to SAT are given by: •A. Alhazov [1], through P systems with active membranes and using only two electrical charges. •L. Pan, A. Alhazov, and T.O. Ishdorj [18], in the framework of P systems with active membranes, and without division, without polarizations, but using three types of membrane rules (separation, merging, and release). •L. Pan and T.O. Ishdorj [19], through P systems with separation rules instead of division rules, in two different cases: in the first, using polarizations and separation rules; and in the second without polarizations and without change of membrane labels, but using separation rules with change of membrane labels. •Gh. P˘aun, M.J. P´erez-Jim´enez, and A. Riscos-N´u˜nez [26], using P systems with tables of rules (each membrane is associated with several sets of rules, one of which is nondeterministically chosen in each computation step); in particular, they consider tables with obligatory rules, which are distinguished rules which must be applied at least once when the table is applied. In [36], M.J. P´erez-Jim´enez, A. Romero-Jim´enez, and F. Sancho-Caparrini present the first linear time uniform solution to the VALIDITY problem, for formulas in conjuctive normal form. Different efficient solutions to graph problems (Vertex Cover,Clique)ina uniform way are presented by A. Alhazov, C. Mart´ın-Vide, and L. Pan in [3]. The first efficient and uniform solutions to numerical NP-complete problems were given by M.J. P´erez-Jim´enez and A. Riscos-N´u˜nez in [30] where a solution to the Knapsack problem was presented. A uniform solution to Multiset 0–1 Knapsack problem is given in the same framework by L. Pan and C. Mart´ın-Vide in [20]. Other uniform solutions to numerical problems are the following: •M.J. P´erez-Jim´enez and A. Riscos-N´u˜nez provide in [31] a solution to Subset Sum, and in [7] give a solution to the Partition problem. •M.J. P´erez-Jim´enez and F.J. Romero-Campero present in [32] a solution to the Bin Packing problem, and in [33] give a solution to Common Algorithmic Problem, a problem with a property of local universality in the sense that many other interesting NP-complete problems can be reduced to it in linear time. In this section we present a linear time uniform solution to the Knapsack problem, and a quadratic time uniform solution to the decision version of the Common Algorithmic Problem. 5.1 A Linear Time Solution to the Decision Knapsack Problem The decision Knapsack problem (0/1) is as follows: Given a knapsack of capacity k∈N,asetAof nelements, where each element has a “weight” wi∈Nand a “value” vi∈N, and given a constant c∈N, decide whether or not there exists a subset of Asuch that its weight does not exceed kand its value is greater than or equal to c. The instances of the problem will be represented by tuples of the form (n, (w1,...,w n),(v1,...,v n),k,c), where nis the size of the set A,(w1,...,w n) and (v1,...,v n) are the weights and the values, respectively, of the elements from A,andkand care the constants mentioned above. The funtions wand vcan be extended to every subset of Ain a natural way from the data in the instance. Also, we consider the size of the instance to be n, k, c(where  is a polynomial encoding of the tuple, for example, using the Cantor pair function). In the discussion that follows we will construct a family of recognizer P systems with active membranes using 2-division and with input that solves the decision Knapsack problem (0/1) in linear time. Specifically, given the size nof the set Aand two constants kand c, we construct a P system Π(n, k, c) that solves all the instances of size n, k, c, given an appropriate encoding for the input membrane of the weights and values of the elements from A.The functioning of this P system can be divided in the following stages: (a) Generate all the subsets of A, computing simultaneously the weights and the values of the subsets. (b) For all the subsets check if the condition w(B)≤kholds. (c) For all the subsets of Athat satisfy the first condition, check if the condition v(B)≥cholds. (d) Answer yes or no according to the results of the two checking stages. The P system Π(n, k, c) is defined as follows. •The input alphabet is Σ(n, k, c)={x1,...,x n,y 1,...,y n}. •The working alphabet is Γ(n, k, c)={a0,a,¯a0,¯a, b0,b,¯ b0,¯ b,ˆ b0,ˆ b, d+,d −,e 0,...,e n, q0,...,q 2k+1,q,¯q, ¯q0,...,¯q2c+1,x 0,...,x n,y 0,...,y n, yes,no,z0,...,z 2n+2k+2c+6,#}. •The set of labels is {s, e}. •The initial membrane structure is [s[e]0 e]0 s(each membrane with label eis said to be internal). •The input membrane is the one with label e. •The initial multisets associated with the membranes are Ms=z0and Me=e0¯ak¯ bc. •The rules are: (a.1) [eei]0 e→[eq]− e[eei]+ e,for0≤i≤n, (a.2) [eei]+ e→[eei+1]0 e[eei+1]+ e,for0≤i≤n−1, (a.3) [ex0→λ]+ e,[ exi→xi−1]+ e,for1≤i≤n, (a.4) [ex0→¯a0]0 e, (a.5) [ey0→λ]+ e,[ eyi→yi−1]+ e,for1≤i≤n, (a.6) [ey0→¯ b0]0 e, (a.7) [eq→¯qq0]− e,[ e¯a0→a0]− e,[ e¯a→a]− e,[ e¯ b0→ˆ b0]− e,[ e¯ b→ˆ b]− e, (b.1) [ea0]− e→[e]0 e#, [ea]0 e→[e]− e#, (b.2) [eq2j→q2j+1]− e,for0≤j≤k, (b.3) [eq2j+1 →q2j+2]0 e,for0≤j≤k−1, (b.4) [eq2j+1]− e→[e]+ e#, for 0 ≤j≤k, (b.5) [e¯q→¯q0]+ e,[ eˆ b0→b0]+ e,[ eˆ b→b]+ e,[ ea→λ]+ e, (c.1) [eb0]+ e→[e]0 e#, [eb]0 e→[e]+ e#, (c.2) [e¯q2j→¯q2j+1]+ e,for0≤j≤c, (c.3) [e¯q2j+1 →¯q2j+2]0 e,for0≤j≤c−1, (c.4) [e¯q2c+1]+ e→[e]0 eyes,[ e¯q2c+1]0 e→[e]0 eyes, (d.1) [szi→zi+1]0 s,for0≤i≤2n+2k+2c+5, (d.2) [sz2n+2k+2c+6 →d+d−]0 s, (d.3) [sd+]0 s→[s]+ sd+,[ sd−→no]+ s, (d.4) [syes]+ s→[s]0 syes,[ sno]+ s→[s]0 sno. Let us see if this P system solves the Knapsack problem for every instance of size n, k, c. First of all we must define a polynomial encoding of the problem into the family Πin order to give a suitable input to the system. Given an instance u=(n, (w1,...,w n),(v1,...v n),k,c)oftheKnapsack problem, we define cod(u)=xw1 1...x wn nyv1 1...yvn n. Now we will informally describe how the system Π(n, k, c) with input cod(u)works. As we have just shown, the objects xiand yiwill represent the weights and values of the elements of A. On the other hand, the objects ¯aand ¯ b(the first will change to afor the second stage, while the second will change to ˆ b for the second stage and to bfor the third stage), included from the beginning by definition of the system, represent the constants kand c, respectively. In the first stage of the computation the initial internal membrane is continuosly divided by means of the rules from (a.1) and (a.2). These membrane divisions are controlled by the objects ei, which represent the elements of the set Abeing considered. The charges of the newly created membranes indicate whether or not the element has been included in the subsets of Athat are being generated. We show in Figure 2 an example for n= 4 of the membrane generation tree that is obtained. Let us introduce the concept of subset associated with an internal membrane through the following recursive definition: •The subset associated with the initial internal membrane is the empty one. •When an object ejappears in a neutrally charged internal membrane (with j<n), the jth element of Ais selected and added to the previously associated subset. Once the stage is over, the associated subset will not be modified any more. •When a division rule is applied, the two newborn internal membranes inherit the associated subset from the original one. What we intend to get is a single internal membrane for each subset of A but, as we will later see, the membranes are not generated simultaneously (it can be shown that the membrane corresponding to the subset {ai1,...,a ir} is generated at the (ir+r+ 2)th computation step). After a division rule from (a.1) is applied, the two new membranes will behave in quite different ways. On the one hand, in the negatively charged membrane (we have marked such membranes in Figure 2 with a circle) the first stage ends, and in the next step the rules from (a.5) will be applied, renaming the objects to prepare the third stage. This is a significant step, so we will designate as relevant those membranes that have negative charge and contain an object q0. A relevant membrane will not further divide during the computation, and its associated subset will remain unchanged. On the other hand, the positively charged membranes will continue the generation of Q− Q−Q− Q−Q− Q− Q− + E E0+ E + EE0 + E E0 + EE0+ EE0+ E+ E E0 3 + E + E + E + E E0 + E + E 1 22 33 3 44 4 4 4 + E2 3 4 4 4 3 3 44 4 Q− Q−Q− Q−Q− Q− Q− Q− 0 E1 + E1 Q− E0+ E + EE0 + E E0 + EE0+ EE0+ E+ E E0 3 + E + E + E + E E0 + E + E 22 33 3 44 4 4 4 + E2 3 4 4 4 3 3 44 4 0 E + E 0 0 Fig. 2. Membrane generation tree for n=4. subsets of A; they will give rise to membranes associated with subsets that are obtained by adding elements of Aof index i+ 1 or greater to the current subset. Note that if i=n, then the membrane cannot continue generating subsets, since it is not possible to add elements of indices greater than n.This has been taking into account because, as there is no rule from (a.1) or (a.2) thatcanbeappliedtoanobjectenin a positively charged membrane (see the membranes surrounded by a diamond in Figure 2), the membrane halts. Thus, since the indices of objects einever decrease, the relevant membranes are generated in a kind of lexicographic order, in the following sense: if the jth element of Ahas already been added to the associated subset, then no element with index lower than jwill be added later to the subset associated with that membrane, or to the subsets associated with its descendants. The generation of subsets and the computation of their weights and values are carried out in parallel. In fact, there is only a gap of one step of computation between the time an element is added to the associated subset and the time the new weight and value of the subset are updated. The rules involved here are those from (a.3–6). Recall that the objects xirepresent the weights of the elements of Aand the objects yirepresent their values. The rules from (a.3) and (a.5) performed a rotation of these objects so that the objects x0 and y0correspond to the weight and the value of the current element of A; that is, if a positively charged internal membrane contains an object ei,meaning that the element of Abeing considered is the ith one, then the objects x0 represent the weight of the element and the objects y0represent the value. On the other hand, if an internal membrane contains an object eiand is neutrally charged, it means that the ith element of Ais going to be added to the subset associated with the membrane. Then the weight and value of the subset have to be updated. This is done by means of the rules from (a.4) and (a.6), which transform the objects x0and y0into objects ¯a0and ¯ b0representing the partial weight and value of the subset (note that the objects ¯a0will change to a0for the second stage, and the objects ¯ b0will change to ˆ b0for the second stage and to b0for the third stage). The purpose of the rules from (a.5) is to prevent the rules for the second stage from being applied to an internal membrane that has not yet reached the end of the first stage. For that, we rename the objects obtained at the end of the latter, q, ¯a0,¯a,¯ b0,and¯ b, to objects ¯q,q0,a 0,a,ˆ b0,andˆ bthat are not used in it. The objects ¯q,ˆ b0,andˆ bare not used until the third stage, so they remain unchanged through the second stage. The objects a0and aare used in a loop that checks if the weight of the subset of Abeing considered satisfies the condition of being less than or equal to k. The rules from (b.1) eliminate alternatively (the alternation is controlled by the negative and neutral charges of the membrane), at each step of the loop, one by one, until we run out of one (or both) of the objects. It is easy to see that the required condition is verified if and only if the loop can make an even number of steps. The objects qiare then used to count the number of steps performed by the loop. Let us see in a more detail how this loop works. Let Bbe a subset of a certain weight wB. The evolution of the relevant membrane associated with it along the second stage is described in Table 1. Multiset Charge Parity of qi q0awB 0ak¯qˆ bvB 0ˆ bc−EVEN q1awB−1 0ak¯qˆ bvB 0ˆ bc0ODD q2awB−1 0ak−1¯qˆ bvB 0ˆ bc−EVEN . . .. . .. . . q2jawB−j 0ak−j¯qˆ bvB 0ˆ bc−EVEN q2j+1 awB−(j+1) 0ak−j¯qˆ bvB 0ˆ bc0ODD . . .. . .. . . Table 1. Comparison of weight with k. Note 1. Observe that the index of qicoincides with the total number of copies of aand a0that have already been erased during the comparison. Note 2. If B={ai1,...,a ir}with ir=n, then there will be in the multiset some objects xjand yj,for1≤j≤n−ir, but they are irrelevant for this stage and therefore they will be omitted. If the number wBof objects a0is less than or equal to the number kof objects a, then the result of this stage is successful and we can proceed with the next stage. This situation is described in Table 2. Multiset Charge Parity of qi . . .. . .. . . q2wB−1ak−wB+1 ¯qˆ bvB 0ˆ bc0ODD q2wBak−wB¯qˆ bvB 0ˆ bc−EVEN q2wB+1 ak−wB¯qˆ bvB 0ˆ bc−ODD ak−wB¯qˆ bvB 0ˆ bc+ODD Table 2. Weight less than or equal to k. If the number wBof objects a0is greater than the number kof objects a, then every time the rules from (b.2) can be applied (that is, for j=0,...,k), the first rule from (b.1) will also be applied. Thus, we can never get to a situation where the index of the counter qiis an odd number and the charge of the internal membrane is negative. This means that the rule (b.4) can never be applied, and moreover, the membrane gets blocked (it will not evolve anymore during the computation). This situation is described in Table 3. Multiset Charge Parity of qi . . .. . .. . . q2k−1awB−k 0a¯qˆ bvB 0ˆ bc0ODD q2kawB−k 0¯qˆ bvB 0ˆ bc−EVEN q2k+1 awB−(k+1) 0¯qˆ bvB 0ˆ bc0ODD Table 3. Weight greater than k. Let us suppose that the second stage has successfully finished in an internal membrane. That means that this membrane encodes a subset B⊆Asuch that w(B)≤k. Then, after applying the rule (b.4), this membrane gets a positive charge. For the objects used in this stage, so as not to fire the rules corresponding to the next stage, they are renamed by means of the rules from (b.5). In this way, the objects ˆ b0are transformed to objects b0and the objects ˆ bto objects b. The counter ¯qiis initialized to ¯q0. The third stage works in a similar way as the second one, using the rules from (c.1), (c.2), and (c.2) corresponding to the rules from (b.1), (b.2), and (b.3), respectively. The end of the stage, however, is different. In this stage, we have to check if the number of objects b0, corresponding to the value of the subset of Aassociated with the membrane, is greater than or equal to the number of objects b, corresponding to the constant c. Therefore, to pass to the final stage the two rules from (c.1) must have been applied ctimes each. Consequently, the rules from (c.2) and (c.3) take the counter of the loop to qc+1, when the rules from (c.4) send it out to the skin as a yes object. Table 4 summarizes all the process described above. Finally, rules from (d.1–3) are associated with the skin membrane and take care of the output stage. The counter zi, used by the rules from (d.1) and (d.2), waits through 2n+2k+2c+7steps(2n+3 steps for the first stage, 2k+ 2 steps for the second stage and 2c+ 2 for the third stage). After all these steps are performed, we are sure that all the inner membranes have already finished their checking stages (or have already got blocked), and thus, the output process is activated. Then, the skin will be neutrally charged and will contain the objects d+ and d−. Furthermore, some objects yes will be present in the skin if and only if both checking stages have been successful in at least one internal membrane. Multiset Charge Parity of qi ¯q0bvB 0bc+EVEN ¯q1bvB−1 0bc0ODD . . .. . .. . . ¯q2c−1bvB−c 0b0ODD ¯q2cbvB−c 0+EVEN ¯q2c+1bvB−(c+1) 0(if vB>c) 0 ODD or ¯q2c+1 (if vB=c) + ODD bvB−(c+1) 0or ∅+ Table 4. Comparison of value with c. The output process then begins. First the object d+is sent out to the environment, giving a positive charge to the skin. Then the object d−evolves to no inside the skin and, simultaneously, if there exists any object yes present in the membrane, it is sent out of the system, giving a neutral charge to the skin and making the system halt (in particular, further evolution of the object no is avoided). Otherwise, if none of the membranes has successfully passed both checking stages, then there will be no object yes present in the skin when the output stage begins. Thus, after the object no is generated, the skin will still have a positive charge, so the object will be sent out to the environment and the system will halt. Now we are going to justify that the family Π=(Π(n, k, c))n,k,c∈Nsolves the decision Knapsack problem (0/1) in linear time. First, the above description of the system is computable in a uniform way. It is also a polynomial description, since the size of the input alphabet is 2n; the size of the working alphabet is 5n+4k+4c+ 31; the size of the set of labels is 2; the number of membranes in the initial membrane structure is 2; the maximum cardinal of the initial multisets is 3; the total number of evolution rules is 6n+5k+4c+ 34; and the maximum length of a rule is 7. Hence, the family Πis Turing polynomially uniform. Second, the family Πis linearly bounded, since given an instance u= (n, (w1,...,w n),(v1,...,v n),k,c) of the problem, the total number of steps performed by the unique computation of the system Π(n, k, c) given the input cod(u)isatmost2n+2k+2c+ 10. Third, from the description of the functioning of the P system Π(n, k, c) it can be seen that the family Πis sound and complete. 5.2 A Quadratic Time Solution to CADP The Common Algorithmic Problem (CAP) [8] is the following optimization problem: Let Sbe a finite set and Fbe a family of subsets of S,called forbidden sets. Find the cardinality of a maximal subset of Swhich does not include any set belonging to F. The Common Algorithmic Problem can be transformed into a roughly equivalent decision problem by supplying a target value to the quantity to be optimized, and asking the question as to whether or not this value can be attained. The Common Algorithmic Decision Problem (CADP) is the following decision problem: Let Sbe a finite set, Fbe a family of subsets of S,and k∈N. Determine if there exists a subset Aof Ssuch that |A|≥k, and which does not include any set belonging to F. We will say that a problem Xis a subproblem of another problem Yif there exists a linear time reduction from Xto Y(using logarithmic bounded space). That is, Xis a subproblem of Yif we can pass from the former to the latter by a simple rewriting process. Next, we present some NP-complete decision problems that are subproblems of CADP. •The Independent Set Decision Problem (ISD): Given an undirected graph G,andk∈N, determine whether or not Ghas an independent set of size at least k. •The Vertex Cover Decision Problem (VCD): Given an undirected graph G, and k∈N, determine whether or not Ghas a vertex cover of size at most k. •The Clique Decision Problem (CDP):Given an undirected graph G,and k∈N, determine whether or not Ghasacliqueofsizeatleastk. •The Hamiltonian Path Problem (HPP). •The Satisfiability Problem (SAT). •The Tripartite Matching Problem: Given three sets B,G,andH,each containing nelements, and a ternary relation T⊆B×G×H, determine whether or not there exists a subset Tof Tsuch that |T|=nand no two triples belonging to Thave a component in common. In what follows we will construct a family of recognizer P systems with active membranes using 2-division and with input that solves CADP in polynomial time. Specifically, given the size nof the set S,thesizemof the set F, and a constant k, we construct a P system Π(n, m, k) that solves the problem for all the instances of size n, m, k, given as input an appropriate encoding of the subsets of Sbelonging to F. The functioning of this P system can be divided into the following stages: 26. Gh. P˘aun, M.J. P´erez-Jim´enez, A. Riscos-N´u˜nez: P Systems with Tables of Rules. In Theory is Forever, Essays Dedicated to Arto Salomaa on the Ocassion of His 70th Birthday (J.Karhumaki,H.Maurer,Gh.P˘aun, G. Rozenberg, eds.), LNCS 3113, Springer, Berlin, 2004, 235–249. 27. Gh. P˘aun, A. Riscos-N´u˜nez, A. Romero-Jim´enez, F. Sancho-Caparrini, eds.: Proceedings of the Second Brainstorming Week on Membrane Computing, Sevilla, February 2004, Report RGNC 01/04, Univ. of Sevilla, 2004. 28. Gh. P˘aun, G. Rozenberg: A Guide to Membrane Computing. Theoretical Computer Science, 287 (2002), 73–100. 29. Gh. P˘aun, Y. Suzuki, H. Tanaka, T. Yokomori: On the Power of Membrane Division in P Systems. Theoretical Computer Science, 324, 1 (2004), 61–85. 30. M.J. P´erez-Jim´enez, A. Riscos-N´u˜nez: A Linear Time Solution to the Knapsack Problem Using Active Membranes. In [14], 250–268. 31. M.J. P´erez-Jim´enez, A. Riscos-N´u˜nez: Solving the Subset-Sum Problem by P Systems with Active Membranes. New Generation Computing, in press. 32. M.J. P´erez-Jim´enez, F.J. Romero-Campero: An Efficient Family of P Systems for Packing Items Into Bins. Journal of Universal Computer Science, 10, 5 (2004), 650–670. 33. M.J. P´erez-Jim´enez, F.J. Romero-Campero: Attacking the Common Algorithmic Problem by Recognizer P Systems. In Pre-proceedings of the Machines, Computations and Universality, MCU’2004 (abstracts), September 21-26, 2004, Sankt Petesburg, p. 27. 34. M.J. P´erez-Jim´enez, A. Romero-Jim´enez, F. Sancho-Caparrini: Teor´ıa de la Complejidad en Modelos de Computaci´on con Membranas. Ed. Kronos, Sevilla, 2002. 35. M.J. P´erez-Jim´enez, A. Romero-Jim´enez, F. Sancho-Caparrini: Complexity Classes in Models of Cellular Computing with Membranes. Natural Computing, 2, 3 (2003), 265–285. 36. M.J. P´erez-Jim´enez, A. Romero-Jim´enez, F. Sancho-Caparrini: Solving VALIDITY Problem by Active Membranes with Input. In Proceedings of the Brainstorming Week on Membrane Computing, Tarragona, February 2003 (M. Cavaliere, C. Mart´ın-Vide, Gh. P˘aun, eds.) Report GRLMC 26/03, 2003, 279–290. 37. A. Romero-Jim´enez: Complexity and Universality in Cellular Computing Models. PhD. Thesis, University of Seville, Spain, 2003. 38. A. Romero-Jim´enez, M.J. P´erez-Jim´ enez: Simulating Turing Machines by P Systems with External Output. Fundamenta Informaticae, 49, 1-3 (2002), 273–287. 39. P. Sosik: The Computational Power of Cell Division. Natural Computing,2,3 (2003), 287–298. 40. C. Zandron, C. Ferreti, G. Mauri: Solving NP-Complete Problems Using P Systems with Active Membranes. In Unconventional Models of Computation, UMC’2K (I. Antoniou, C.S. Calude, M.J. Dinneen, eds.), Springer, London, 2000, 289–301. 41. C. Zandron, G. Mauri, C. Ferreti, Universality and Normal Forms on Membrane Systems. In Proceedings of International Workshop on Grammar Systems, 2000 (R. Freund, A. Kelemenova, eds.), Bad Ischl, Austria, July 2000, 61–74.