On a Paun’s Conjecture in Membrane Systems

On a P˘aun’s Conjecture in Membrane Systems Giancarlo Mauri2,MarioJ.P´erez-Jim´enez1, and Claudio Zandron2 1Research Group on Natural Computing Department of Computer Science and Artificial Intelligence. University of Sevilla Avda. Reina Mercedes s/n, 41012 Sevilla, Spain [email protected] 2Dipartimento di Informatica, Sistemistica e Comunicazione. Universit´adi Milano–Bicocca via Bicocca degli Arcimboldi 8, I–20126, Milano, Italy mauri/[email protected] Abstract. We study a P˘aun’s conjecture concerning the unsolvability of NP–complete problems by polarizationless P systems with active membranes in the usual framework, without cooperation, without priorities, without changing labels, using evolution, communication, dissolution and division rules, and working in maximal parallel manner. We also analyse a version of this conjecture where we consider polarizationless P systems working in the minimally parallel manner. 1 Introduction Every deterministic Turing machine working in polynomial time can be simulated in polynomial time by a family of recognizing P systems using only basic rules, that is, evolution, communication, and rules involving dissolution [14]. If a decision problem is solvable in polynomial time by a family of recognizing P systems (using only basic rules), then there exists a deterministic Turing machine solving it in polynomial time [20]. As a consequence of these results, the class of all decision problems solvable in polynomial time by this kind of P systems is equal to the standard complexity class P [5]. For that reason, recognizing P systems constructing in polynomial time an exponential workspace, expressed in the number of objects, cannot solve NP–complete problems in polynomial time (unless P = NP). Hence, in order to efficiently solve NP–complete problem by P systems it seems necessary to be able to construct an exponential workspace (expressed by the number of membranes) in polynomial time. These models abstract the way of obtaining new membranes through the processes of mitosis (membrane division) and autopoiesis (membrane creation). P systems with active membranes (using division rules) have been successfully used to efficiently solve NP–complete problems. The first solutions were given constructing a P system associated with each instance of the problem due to the systems lack of an input membrane. Actually, we say that this kind of solutions are semi–uniform if the following is true: (a) there exists a deterministic Turing machine working in polynomial time which constructs the P system processing an instance of the problem (we say the family of P systems associated with all the instances is polynomially uniform by Turing machines); and (b) the instance of the problem has an affirmative answer if and only if every computation of the P system associated with it is an accepting computation (we say the P system is confluent). The first semi–uniform polynomial–time solutions of computationally hard decision problems were given by Gh. P˘aun [11,12], C. Zandron et al. [20], S.N. Krishna et al. [7], and A. Obtulowicz [8]. In 2003, P. Sosik [19] gave a semi– uniform polynomial–time solution to QSAT,awellknownPSPACE–complete problem. There is another way to solve decision problems by P systems when we consider the possibility to have an input membrane in the systems in which we can introduce objects before the system starts to work. In this case, all instances of a decision problem having the same size (according to a prefixed polynomial time criterion) are processed by the same system. P systems with active membranes have also been successfully used to design uniform polynomial–time solutions to some well-known NP–complete problems, such as SAT [17], Subset Sum [15], Knapsack [16], Partition [6], and the Common Algorithmic Problem [18]. All papers mentioned above deal with P systems with three polarizations using only division of elementary membranes (in [19] also division for non–elementary membranes are permitted), and working in the maximal parallelism in using the rules, that is, in each step, the assignment of objects to the rules to be applied is maximal, no further rule can be applied in any region. The number of polarizations can be decreased to two [1] without loss of efficiency. It seems clear that the usual framework of P systems with active membranes to solve decision problems is too powerful from the complexity point of view. Then, it would be interesting to analyse which features allows to P systems with active membranes, but without polarizations, to still get polynomial–time solutions to computationally hard problems, and what features, once removed, only allows to obtain polynomial–time solutions to tractable problems, in the classical sense. The present paper is a contribution to the problem of describing borderlines between tractability and intractability in terms of descriptional resources required in (recognizing) membrane systems using division rules. The paper is organized as follows. In the next section we present the P˘aun’s conjecture concerning polarizationless P systems with active membranes with three electrical charges and working in the maximally parallel mode. Also we provide some partial solutions to this conjecture by using the notion of dependency graph associated with a P system. Section 3 is devoted to formulate a new version of the P˘aun’s conjecture, addressing P systems working in the minimally parallel mode. We give some partial solutions to this new version. Some conclusions and open problems are given in the last Section. 2AP˘aun’s Conjecture Usual P systems with active membranes use three electrical charges for membranes, controlling the application of the rules which, basically, can be of the following types: evolution rules, by which single objects evolve to a multiset of objects, communication rules, by which an object is introduced in or expelled from a membrane, maybe modified during this operation into another object, dissolution rules, by which a membrane is dissolved, under the influence of an object, which may be modified into another object by this operation, and membrane division rules (both for elementary and non-elementary membranes, or only for elementary membranes). Definition 1. A P system with polarizationless active membranes of the initial degree n≥1is a tuple of the form Π=(Γ,H,μ,M1,...,Mn,R,h o),where: 1. Γis the alphabet of objects; 2. His a finite set of labels for membranes; 3. μis a membrane structure, consisting of nmembranes having initially neutral polarizations, injectively labeled with elements of H; 4. M1,...,Mnare strings over Γ, describing the multisets of objects placed in the ninitial regions of μ; 5. Ris a finite set of developmental rules, of the following forms: (a) [a→v]h,forh∈H,a ∈Γ,v ∈Γ∗(object evolution rules). (b) a[] h→[b]h,forh∈H, a,b ∈Γ(in communication rules). (c) [a]h→b[] h,forh∈H, a,b ∈Γ(out communication rules). (d) [a]h→b,forh∈H, a,b ∈Γ(dissolution rules) (e) [a]h→[b]h[c]h,forh∈H,a,b, c ∈Γ(weak division rules for elementary or non-elementary membranes). (a) ho∈Hor ho=env indicates the output region (in this case, usually ho do not appear in the description of the system). Also, we can consider rules of the form [[ ]h1[] h2]h3→[[]h1]h3[[]h2]h3,where h1,h 2,h 3are labels: if the membrane with label h3contains other membranes than those with labels h1,h 2, these membranes and their contents are duplicated and placed in both new copies of the membrane h3; all membranes and objects placed inside membranes h1,h2, as well as the objects from membrane h3placed outside membranes h1and h2, are reproduced in the new copies of membrane h3. These rules are called strong division rules for non–elementary membranes. Using the maximally parallel manner, at each computation step (a global clock is assumed) in each region of the system we apply the rules in such a way that no further rule can be applied to the remaining objects or membranes. In each step, each object and each membrane can be involved in only one rule. A halting computation provides a result given by the number of objects present in region hoat the end of the computation; this is a region of the system if ho∈H(and in this case, for a computation to be successful, exactly one membrane with label hoshould be present in the halting configuration), or it is the environment if ho=env. We denote by AM0the class of recognizing polarizationless P systems with active membranes, and we denote by AM0(α, β), where α∈{−d, +d}and β∈ {−ne, +new, +nes}, the class of all recognizing P systems with polarizationless active membranes such that: (a) if α=+d(resp. α=−d) then dissolution rules are permitted (resp. forbidden); and (b) if β=+new or +nes (resp. β=−ne) then division rules for elementary and non–elementary membranes, weak or strong (respectively only division rules for elementary) are permitted. The class of all decision problems solvable in uniform (resp. semi–uniform) way, and in polynomial time by a family of recognizing membrane systems is denoted by PMCR(resp. PMC∗ R) Proposition 1. For each α∈{−d, +d},β∈{−ne, +new, +nes},and=∗,λ, we have: 1. PMCAM0(α,β)⊆PMC∗ AM0(α,β) 2. PMC AM0(α,−ne)⊆PMC AM0(α,+new) 3. PMC AM0(α,−ne)⊆PMC AM0(α,+nes) 4. PMC AM0(−d,β)⊆PMC AM0(+d,β) where =∗(respectively =empty string) means that the complexity classes are associated with semi–uniform (respectively, uniform) solutions. At the beginning of 2005, Gh. P˘aun (problem Ffrom [13]) wrote: My favorite question (related to complexity aspects in P systems with active membranes and with electrical charges) is that about the number of polarizations. Can the polarizations be completely avoided? The feeling is that this is not possible – and such a result would be rather sound: passing from no polarization to two polarizations amounts to passing from non–efficiency to efficiency. That is, formally we can formulate the called conjecture of P˘aun as follows: The class of all decision problems solvable in polynomial time by polarizationless P systems with active membranes using evolution, communication, dissolution and division rules for elementary membranes (working in the maximally parallel mode) is equal to the class P This conjecture can be expressed in terms of complexity classes in P systems as follows: P=PMCAM0(+d,−ne)=PMC∗ AM0(+d,−ne) Next, we study possible answers to the conjecture of P˘aun. 2.1 A Partial Affirmative Answer Let us recall that using the concept of dependency graph associated with a P system, a partial affirmative answer to the P˘aun’s conjecture can be given. Let Πbe a P system whose working alphabet is Γand the set of labels is H, and we denote by env the label of the environment. The dependency graph associated with the system Πis the directed graph GΠwhose nodes are the pairs (a, h)∈Γ×(H∪{env}) such that the object ain membrane (maybe the environment) labelled by heither triggers a rule or it is produced by a rule, and ((a, h),(a,h )) is an arc in the graph if there exists a rule rof Πsuch that the object ain membrane labelled by hproduces the object ain membrane (maybe the environment) labelled by hby the application of rule r. It can be proved that there exists a deterministic Turing machine that constructs the dependency graph, GΠ, associated with Π, in polynomial time, that is, in a time bounded by a polynomial function depending on the total number of rules and the maximum length of the rules (see [4]). Let ΔΠbe the set whose elements are the pairs (a, h)∈Γ×(H∪{env})such that there exists a path (within the dependency graph) from (a, h)to(yes,env). Having in mind that the reachability problem (see chapter 1 from [10]) can be solved by a search algorithm running in polynomial (quadratic) time, there exists a deterministic Turing machine that constructs the set ΔΠin polynomial time, that is, in a time bounded by a polynomial function depending on the total number of rules and the maximum length of the rules (see [4]). Let Π={Π(n): n∈N}be a family of recognizing P systems with input membranes (not using dissolution rules) solving a decision problem X, in a uniform way. Let (cod, s) be a polynomial encoding associated with that solution. An instance uof the problem will be accepted by the system Π(s(u)) with input cod(u) if and only if there is an object ain a membrane hof the initial configuration of the system such that there exists a path in the associated dependency graph from (a, h)to(yes,env). As a consequence of the previous results we have the following: Theorem 1. For each β∈{−ne, +new, +nes}, we have P=PMCAM0(−d,β). Similar characterizations of Pcan be obtained when we deal with semi–uniform solutions in the framework of recognizing polarizationless P systems with active membranes, and where dissolution rules are forbidden. The proofs are similar, it is enough to consider the system Π(u), for each instance uof the decision problem, instead of the system Π(s(u)) with input the multiset cod(u). Theorem 2. For each β∈{−ne, +new, +nes}, we have P=PMC∗ AM0(−d,β). 2.2 A Partial Negative Answer It has been shown ([4]) that the class of decision problems solvable in polynomial time in a semi–uniform way by families of recognizing polarizationless P systems with active membranes where dissolution rules are permitted, and using division rules for elementary and non–elementary membranes, contains the standard complexity class NP. Theorem 3. We have the following: 1. SAT ∈PMC∗ AM0(+d,+nes) 2. NP ∪co–NP⊆PMC∗ AM0(+d,+nes) Moreover, it has been obtained an efficient uniform solution for the QSAT– problem ([2]) in this framework. Theorem 4. We have the following: 1. QSAT ∈PMCAM0(+d,+nes). 2. PSPACE ⊆PMCAM0(+d,+nes). Hence, in the framework of polarizationless P systems with active membranes and working in the maximally parallel mode, dissolution rules play a crucial role from the computational efficiency point of view. Specifically, if dissolution rules are forbidden then it is not possible to solve NP–complete problems in polynomial time (unless P=NP). Nevertheless, if dissolution rules are permitted then it is possible to efficiently solve computationally hard problems. That is, the P˘aun’s conjecture has a (partial) negative answer (assuming that P=NP). Nevertheless, the answer will be (partially) affirmative if dissolution rules are forbidden. 3 A New Version of a P˘aun’s Conjecture Recently, in [3] a more relaxed strategy of using the rules was introduced, the so-called minimal parallelism: in each region where at least a rule can be applied, at least one rule must be applied (if there is no conflict with the objects), without any other restriction. This introduces an additional degree of non-determinism in the system evolution. P systems with active membranes working in the minimally parallel mode means the following: –All the rules of any type involving a membrane hform the set Rh, this means all the rules of the form [a→v]h, all the rules of the form a[] h→[b]h, and all the rules of the form [a]h→zand [a]h→[b]h[c]h,withthesame h, constitute the set Rh. –If a membrane happears several times in a given configuration of the system, then for each occurrence of the membrane we consider a different set Rh. –Then, in each step, from each set Rhassociated with each membrane labelled by h∈H, from which at least a rule can be used, at least one rule must be used (if there is no conflict with the objects; for example, if we have only an object ain membrane handwehaveanevolutionrule[a→b]hand a send–in rule a[] h→[c]h,beinghthe label of a membrane immediately inside membrane h, then we can apply at least a rule from Rhand from Rh, but we will apply only one between these two rules). Of course, as usual for P systems with active membranes, each membrane and each object can be involved in only one rule, and the choice of rules to use and of objects and membranes to evolve is done in a non-deterministic way. In each step, the use of rules is done in the bottom-up manner (first the inner objects and membranes evolve, and the result is duplicated if any surrounding membrane is divided). In this kind of P systems still universality and semi–uniform polynomial–time solutions to SAT were obtained in the new framework by using P systems with active membranes, with three polarizations [3]. Theorem 5. The SAT problem can be solved in a semi–uniform way and in a linear time by polarization P systems with active membranes, without dissolution rules and using (weak) division for non–elementary membranes, and working in the minimally parallel mode. Next, we define new classes of P systems related to AM0.Letα∈{−d, +d},β∈ {−ne, +new, +nes}and γ∈{m, M, md, Md}.ThenwedenotebyAM0(α, β, γ) the class of recognizing P systems with polarizationless active membranes such that: •α=+d: dissolution rules are permitted. •α=−d: dissolution rules are forbidden. •β=+new: division rules for elementary and (weak) non–elementary membranes are permitted. •β=+nes: division rules for elementary and (strong) non–elementary membranes are permitted. •β=−ne: only division rules for elementary membranes are permitted. •γ=m: working in the minimally parallel mode. •γ=md: working in the deterministic minimally parallel mode. •γ=M: working in the maximally parallel mode. •γ=Md: working in the deterministic maximally parallel mode. Proposition 2. We have the following: 1. PMC AM0(α,β,md)⊆PMC AM0(α,β,m) 2. PMC AM0(α,β,m)⊆PMC AM0(α,β,M) 3. PMC AM0(α,β,Md)⊆PMC AM0(α,β,M) where =∗or =empty string. We can formulate the P˘aun’s conjecture in P systems working in the minimally parallel mode. The class of all decision problems solvable in polynomial time by polarizationless P systems with active membranes using evolution, communication, dissolution and division rules for elementary membranes (working in the minimally parallel mode) is equal to the class P This conjecture can be expresses in terms of complexity classes in P systems as follows: P=PMCAM0(+d,−ne,m)=PMC∗ AM0(+d,−ne,m). Next, we study possible answers to the new version of P˘aun’s conjecture. 3.1 A Partial Affirmative Answer Let us recall that through the concept of dependency graph associated with a P system, we have given a partial affirmative answer to the P˘aun’s conjecture related with P systems working in the maximally parallel mode, and without using dissolution rules. Let us also recall that, in order to give that answer, the main property that the dependency graph associated with a P system must satisfy is the following: every computation of the system is an accepting computation if and only if there exists an object ain an initial membrane (labelled by h) of the system such that there exists a path (within the dependency graph) from (a, h)to(yes,env). When a polarizationless P system with active membranes works in the minimally parallel mode, in each transition step we can think that objects are assigned to rules, non–deterministically choosing the rules and the objects assigned to each rule, according to the semantic of the minimally parallel mode. The objects which remain unassigned are left where they are, and they are passed unchanged to the next configuration (and belonging to the same membrane because dissolution rules are not permitted). So, the above property is satisfied by the computations of this kind of P systems working in the minimally parallel mode (without using dissolution rules) because we can pass from a node (a, h) to another node (a,h ) in the dependency graph if and only if there exists a transition step producing (a,h )from(a, h). Hence, we have a negative answer to the to the P˘aun’s conjecture related with P systems working in the minimally parallel mode (deterministically or not), and without using dissolution rules. Theorem 6. P =PMC AM0(−d,β,md)=PMC AM0(−d,β,m),where=∗or =empty string. 3.2 A Partial Negative Answer Next, we give a semi–uniform linear–time solution to SAT by using polarizationless P systems with active membranes working in the minimally parallel mode, and now using dissolution rules. Theorem 7. SAT can be solved in a semi–uniform way and in a linear time by polarizationless P systems with active membranes, using evolution, communication, dissolution and (weak) division for non–elementary membrane rules, and working in the deterministic minimally parallel mode. Proof. Let ϕ=C1∧···∧Cmbe a propositional formula in conjunctive normal form, such that each clause Cj,1≤j≤m,isoftheformCj=yj,1∨···∨ yj,kj,k j≥1, for yj,r ∈{xi,¬xi|1≤i≤n},andbeing{x1,...,x n}the set of variables of ϕ.Foreachi=1,2,...,n, let us denote t(xi)={Cj|there is r, 1≤r≤kj,such that yj,r =xi}, f(xi)={Cj|there is r, 1≤r≤kj,such that yj,r =¬xi}. That is, t(xi) (respectively, f(xi)) is the set of clauses which assume the value true when xiis true (resp. when xiis false). Obviously, these sets have at most melements. We construct a recognizing P system Π(ϕ)=(Γ,H,μ, M0,M1,...,Mm,Mp,Mq,Mr,Ms,Ms,R) associated with the formula ϕas follows: Γ={ai,f i,t i|1≤i≤n}∪{cj,d j|1≤j≤m}∪{pi|1≤i≤2n+7} ∪{qi|1≤i≤2n+1}∪{ri|1≤i≤2n+5}∪{b1,b 2,y,yes,no}, H={0,1,2,...,m,p,q,r,s,s }, μ=[ s[s[p]p[0[q]q[r]r[1]1[2]2...[m]m]0]s]s, Mp=p1,Mq=q1,Mr=r1,M0=a1,Ms=Ms=Mj=λ, (1 ≤j≤m) The set of evolution rules, R, consists of the following rules: (a) [pi→pi+1]p,for all 1 ≤i≤2n+6 [qi→qi+1]q,for all 1 ≤i≤2n [ri→ri+1]r,for all 1 ≤i≤2n+4 (b) [ai]0→[fi]0[ti]0,for all 1 ≤i≤n [fi→f(xi)ai+1]0and [ti→t(xi)ai+1]0,for all 1 ≤i≤n−1, [fn→f(xn)]0;[tn→t(xn)]0 (c) cj[] j→[cj]jand [cj]j→dj, for all 1 ≤j≤m. (d) [q2n+1 ]q→q2n+1[] q;[q2n+1 →bm 1]0 (e) b1[] j→[b1]j;and[b1]j→b2, for all 1 ≤j≤m, [b2]0→b2;[p2n+7 ]p→p2n+7[] p;[p2n+7 ]s→no[] s;[no ]s→no[] s [r2n+5 ]r→r2n+5 ;[r2n+5 ]0→y[] 0;[y]s→yes ;[yes ]s→yes[] s An overview of the computation of Π(ϕ) The rules of type (a) are used for evolving general counters pi,q iand ri in membranes labelled by p, q and r, respectively, making possible the correct synchronization. In parallel with these rules, the non–elementary membrane 0 evolves by means oftherulesofthetype(b).Instep2i−1(1≤i≤2n), object aiproduces the division of the membrane 0 (with fi,t icorresponding to the truth values false, true, respectively, for variable xi). In step 2iwe introduce inside membrane 0 the clauses satisfied by xior ¬xi, respectively. Let us recall that when we divide membrane 0, all inner objects and membranes are replicated. At the end of this phase, all 2ntruth assignments for the nvariables are generated and they are encoded in membranes labeled by 0. In parallel with the process of membrane division, in the odd steps (until step 2n+ 1), if a clause Cjis satisfied by the previously expanded variable, then the corresponding object cjenters membrane j, by means of the first rule of the type (c), producing their dissolution in the next step by means of the second rule of that type and sending objects djto membrane 0. In step 2n+ 2, in each membrane 0, the counters qiand rifollow evolving and the second rule of the type (d) produces mcopies of the object b1. Thus, the configuration C2n+2 of the system obtained after 2n+ 2 steps, consists of 2ncopies of membrane 0, each of them encoding a truth assignment of the variables associated with ϕ, and containing the membrane qempty, the