The Relevance of the Environment on the Efficiency of Tissue P Systems

The Relevance of the Environment on the Efficiency of Tissue P Systems Mario J. P´erez-Jim´enez1,Agust´ın Riscos-N´u˜nez1,MiquelRius-Font 2, and Luis Valencia-Cabrera1 1Research Group on Natural Computing Department of Computer Science and Artificial Intelligence University of Sevilla Avda. Reina Mercedes s/n, 41012 Sevilla, Spain {marper,ariscosn,lvalencia}@us.es 2Department of Applied Mathematics IV Universitat Polit´ecnica de Catalunya, Spain [email protected] Abstract. The efficiency of computational devices is usually expressed in terms of their capability to solve computationally hard problems in polynomial time. This paper focuses on tissue P systems, whose efficiency has been shown for several scenarios where the number of cells in the system can grow exponentially, e.g. by using cell division rules or cell separation rules. Moreover, in the first case it suffices to consider very short communication rules with length bounded by two, and in the second one it is enough to consider communication rules with length at most three. This kind of systems have an environment with the property that objects initially located in it appear in an arbitrarily large number of copies, which is a somewhat unfair condition from a computational complexity point of view. In this context, we study the role played by the environment and its ability to handle infinitely many objects, in particular we consider tissue P systems whose environment is initially empty. 1 Introduction Several different models of cell-like P systems have been successfully used to efficiently solve computationally hard problems by trading space for time. An exponential workspace is created in polynomial time by using some kind of rules, and then massive parallelism is used to simultaneously check all the candidate solutions. Inspired by living cells, several ways for obtaining exponential workspace in polynomial time were proposed: membrane division (mitosis)[12],membrane creation (autopoiesis) [5], and membrane separation (membrane fission)[8] 1. These three ways have given rise to the following models: P systems with active 1The name separation rule appeared earlier in [1], but with a slightly different definition. membranes,P systems with membrane creation,andP systems with membrane separation, respectively. A new type of P systems, the so-called tissue P systems, was introduced in [7]. The hierarchical membrane structure that was commonly used in the first models, inspired on the way vesicles and compartments are arranged within a cell, is discarded. Instead, an arbitrary graph of connections among elementary membranes (now called cells) is considered. That is, the inspiration comes now not from a single cell but from a collection of cooperating cells within a multicellular organism, e.g. in a tissue. Moreover, the functioning of tissue P systems heavily relies on the intercellular communication, since objects can move under symport/antiport rules, but cannot be rewritten. This paper addresses two models of tissue P systems which are of a great interest from a computational complexity point of view. The first one was presented in [14], where the definition of tissue P systems is combined with aspects of the definition of P systems with active membranes, yielding tissue P systems with cell division. In these models, cells may replicate, that is, the two new cells generated by a division rule have exactly the same objects except for at most one differing pair of objects. The second model that will be considered is tissue P systems with cell separation [9]. In this case, an alternative method for generating an exponential number of cells in linear time is used. When a cell divides, its contents are not replicated, but distributed, according to a fixed partition of the alphabet. The paper is organized as follows. First, we recall the basic mathematical and theoretical background underlying the definitions of the two tissue P systems models mentioned above, together with the definition of complexity class in the membrane computing framework. Then, Section 3 compares the computational power achieved by cell division and by cell separation, evaluating in both cases the role of the environment. Some concluding remarks summarizing the borderlines of efficiency discussed in the paper are given in Section 4. 2 Tissue P Systems Let us recall that an alphabet Γis a non–empty set whose elements are called symbols.Amultiset mover an alphabet Γis a pair m=(Γ,f)wheref:Γ→IN is a mapping. If m=(Γ, f) is a multiset then its support is defined as supp(m)={x∈Γ|f(x)>0}. A multiset is finite if its support is a finite set. Let supp(m)={a1,...,a k}be the support of a finite multiset, m,thenwe will denote m=af(a1) 1...a f(ak) k(here the order is irrelevant), and we say that f(a1)+...+f(ak) is the cardinal of m, denoted by |m|. The empty multiset is denoted by λ.WealsodenotebyMf(Γ) the set of all finite multisets over Γ. Let m1=(Γ,f1)andm2=(Γ,f2) multisets over Γ.Theunion of m1and m2, denoted by m1+m2is the multiset (Γ,g), where g=f1+f2,thatis,g(x)= f1(x)+f2(x)foreachx∈Γ.Therelative complement of m2in m1, denoted by m1\m2is the multiset (Γ,g), where g(x)=f1(x)−f2(x)iff1(x)≥f2(x)and g(x)=0otherwise. Definition 1. A basic tissue P system of degree q≥1is a tuple Π=(Γ,Σ,E,M1,...,Mq,R,i in,i out),where: 1. Γis a finite alphabet and Eis a subset of Γ. 2. Σis an (input) alphabet strictly contained in Γsuch that E∩Σ=∅. 3. M1,...,Mqare finite multisets over Γ\Σ. 4. Ris a finite set of communication rules of the form (i, u/v, j), for i, j ∈{0,1,2,...,q},i=j,u, v ∈Mf(Γ),and|u+v| =0; 5. iin ∈{1,2,...,q},andiout ∈{0,1,...,q}. Abasic tissue P system Π=(Γ, Σ, E,M1,...,Mq,R,i in,i out)ofdegreeq≥1 canbeviewedasasetofqcells, labelled by 1,...,q,withanenvironment labelled by 0 such that: (a) M1,...,Mqare finite multisets over Γrepresenting the objects (elements in Γ) initially placed in the qcells of the system; (b) Σis the input alphabet and Eis the set of objects located initially in the environment of the system, all of them appearing in an arbitrary number of copies;and(c) iin represents the input cell, and iout ∈{0,1,...,q}indicates the region that stores the output of the system (which can be either a distinguished cell when iout ∈{1,...,q}, or the environment when iout =0).IfE=∅then we say that the tissue P system is without environment. A communication rule (i, u/v, j)isapplicable to regions i, j if the multiset u is contained in region iand multiset vis contained in region j. When applying a communication rule (i, u/v, j), the objects of multiset uare sent from region i to region jand, simultaneously, the objects of multiset vare sent from region j to region i.Thelength of communication rule (i, u/v, j) is defined as |u|+|v|. The rules are used in a non-deterministic maximally parallel manner as customary in membrane computing. At each step, we apply a multiset of rules which is maximal: no further applicable rule can be added. Aconfiguration at any instant of a basic tissue P system is described by all multisets of objects over Γassociated with all the cells present in the system, and the multiset of objects over Γ\E associated with the environment at that moment. Recall that there are infinitely many copies of objects from Ein the environment, and hence this set is not properly changed along the computation. For each multiset mover the input alphabet Σ,theinitial configuration with input mis C0=(M1,···,Miin +m, ···,Mq;∅). Therefore, we have an initial configuration associated with each input multiset m(over the input alphabet Σ) in this kind of systems. We will use the notation (Π+m)torefertoaP system Πsuch that its initial configuration is the one associated with m.A configuration is a halting configuration if no rule of the system is applicable to it. We say that configuration C1yields configuration C2in one transition step, denoted by C1⇒ΠC2, if we can pass from C1to C2by applying the rules from Rfollowing the previous remarks. Acomputation of Πis a (finite or infinite) sequence of configurations such that: (a) the first term of the sequence is the initial configuration C0of the system associated with a given input; (b) for each n≥2then–th configuration of the sequence is obtained from the previous configuration by applying a maximal multiset of rules of the system as described above; and (c) if the sequence is finite (called halting computation) then the last term of the sequence must be a halting configuration. Only halting computations give a result, which is encoded by the objects present in the output region iout in the halting configuration. The result of a computation can be defined in various ways, just like in the cell-like case. Obviously, when the output is collected in the environment, symbols from Emust be ignored. If C={Ct}0≤t≤rof Π(r∈IN) is a halting computation, then the length of C, denoted by |C|,isr. 2.1 Cell Division and Cell Separation Reproduction is doubtlessly one of the fundamental mechanisms on every living being. Thus, there is a clear motivation to try to get inspiration from the various processes that generate new cells (or new membranes, in general) and to adapt them into the tissue P systems framework. Moreover, as mentioned in the Introduction, division rules (mitosis), and separation rules (membrane fission) have been already introduced for cell-like P systems [12,8]. Definition 2. A tissue P system with cell division of degree q≥1is a tuple Π=(Γ,Σ,E,M1,...,Mq,R,i in,i out),where: 1. Π=(Γ,Σ,E,M1,...,Mq,Rc,i in,i out)is a basic tissue P system, where Rc is the set of communication rules in R. 2. Rmay also contain cell division rules of the form [a]i→[b]i[c]i,where i∈{1,2,...,q},i=iout and a, b, c ∈Γ. Definition 3. A tissue P system with cell separation of degree q≥1is a tuple Π=(Γ,Γ1,Γ 2,Σ,E,M1,...,Mq,R,i out),where: 1. Π=(Γ,Σ,E,M1,...,Mq,Rc,i in,i out)is a basic tissue P system, where Rc is the set of communication rules in R. 2. {Γ1,Γ 2}is a partition of Γ, that is, Γ=Γ1∪Γ2,Γ1,Γ 2=∅,Γ1∩Γ2=∅. 3. Rmay also contain cell separation rules of the form [a]i→[Γ1]i[Γ2]i,where i∈{1,...,q},a∈Γand i=iout. Atissue P system with cell division is a basic tissue P system that allows cell division rules. When applying a division rule [a]i→[b]i[c]i, under the influence of object a, the cell with label iis divided into two cells with the same label; in the first copy, object ais replaced by object b, in the second one, object ais replaced by object c; all the other objects are replicated and copies of them are placed in the two new cells. Atissue P system with cell separation is a basic tissue P system that allows cell separation rules. When applying a separation rule [a]i→[Γ1]i[Γ2]i, in reaction with an object a, the cell iis separated into two cells with the same label; at the same time, object ais consumed; all the other objects in the cell are distributed (not replicated): those from Γ1are placed in the first cell, while those from Γ2are placed in the second cell. The output cell iout cannot be divided nor separated. The label of a cell precisely identifies the rules which can be applied to it. Note that in the previous definitions {1,...,q}is used as the set of labels, but without loss of generality any finite set can be considered instead. The rules are used in a non-deterministic maximally parallel manner with the following restriction: when a cell is divided (or separated), the objects inside that cell do not get involved in any communication rule during this step. The two new resulting cells could participate in the interaction with other cells or the environment by means of communication rules at the next step – provided that they are not divided (or separated) again. 2.2 Recognizer Tissue P Systems Adecision problem is a pair (IX,θ X)whereIXis a language over a finite alphabet (whose elements are called instances)andθXis a total Boolean function over IX. There are many different ways to describe instances of a decision problem, but we assume that each problem has associated with it a fixed reasonable encoding scheme (in the sense of [3], page 10) which provides a string associated with each problem instance. The size of an instance u∈IXis the length of the string associated with it by means of a reasonable encoding scheme. A correspondence between decision problems and languages over a finite alphabet, can be established as follows. Given a decision problem X=(IX,θ X), its associated language is LX={w∈IX:θX(w)=1}. Conversely, given a language Lover an alphabet Σ, its associated decision problem is XL=(IXL,θ XL), where IXL=Σ∗,andθXL={(x, 1) |x∈L}∪{(x, 0) |x/∈L}. The solvability of decision problems is defined through the recognition of the languages associated with them by means of language recognizer devices. Definition 4. Atissue P system of degree q≥1is a recognizer system if: 1. The working alphabet Γhas two distinguished objects yes and no being, at least, one copy of them present in some initial multisets, but none of them are present in the alphabet of the environment. 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 at the last step of the computation. Note that, because of the first condition, the presence or absence of objects yes and no in the environment can be accounted for in any configuration. Note also that all computations are finite as a consequence of the second condition, and thus it is possible to refer to their “last step”. Given a recognizer tissue P system Πand a computation Cof Π,wesay that Cis an accepting computation (respectively, rejecting computation) if object yes (respectively, object no) appears in the environment associated with the corresponding halting configuration of C. Note that, since Πis a recognizer system, neither object yes nor no appears in the environment associated with any non–halting configuration of C. For each natural number k≥1, we denote by TDC(k) (respectively, TSC(k)) the class of recognizer tissue P systems with cell division (respectively, with cell separation) and communication rules with length at most k.Wedenoteby  TDC(k) (respectively,  TSC(k)) the class of recognizer tissue P systems with cell division (respectively, with cell separation), with communication rules with length at most k, and without environment. Now, we define what it means to solve a decision problem in the framework of tissue P systems efficiently and in a uniform way. Since we define each tissue P system to work on a finite number of inputs, to solve a decision problem we define a numerable family of tissue P systems. Definition 5. We say that a decision problem X=(IX,θ X)is solvable in a uniform way and polynomial time by a family Π={Π(n)|n∈IN }of recognizer P systems if the following holds: 1. The family Πis polynomially uniform by Turing machines, that is, there exists a deterministic Turing machine working in polynomial time which constructs the system Π(n)from n∈IN . 2. There exists a pair (cod, s)of polynomial-time computable functions over IX such that: (a) for each instance u∈IX,s(u)is a natural number and cod(u)is an input multiset of the system Π(s(u)); (b) for each n∈IN ,s−1(n)is a finite set; (c) the family Πis polynomially bounded with regard to (X,cod, s), that is, there exists a polynomial function p, such that for each u∈IXevery computation of Π(s(u)) with input cod(u)is halting and it performs at most p(|u|)steps; (d) the family Πis sound with regard to (X,cod, s), that is, for each u∈IX, if there exists an accepting computation of Π(s(u)) with input cod(u), then θX(u)=1; (e) the family Πis complete with regard to (X,cod,s), that is, for each u∈IX,ifθX(u)=1, then every computation of Π(s(u)) with input cod(u)is an accepting one. From the soundness and completeness conditions above we deduce that every PsystemΠ(n)isconfluent, in the following sense: every computation of a system with the same input multiset must always give the same answer. Let Rbe a class of recognizer P systems. We denote by PMCRthe set of all decision problems which can be solved in a uniform way and polynomial time by means of families of systems from R.TheclassPMCRis closed under complement and polynomial–time reductions [16]. 3 Computational Efficiency of Tissue P Systems without Environment It is well known that tissue P systems with cell division and tissue P systems with cell separation are able to solve computationally hard problems efficiently. Specifically, NP–complete problems have been solved in polynomial time in [19] by using families of tissue P systems with cell division and communication rules of length at most 2, and by using families of tissue P systems with cell separation and communication rules of length at most 3. Thus, NP ∪co −NP ⊆PMCTDC(2)∩PMCTSC(3) In [4,9,10] it has been proved that only tractable problems can be efficiently solved by using families of tissue P systems with cell division and communication rules of length 1 (or with cell separation and communication rules of length bounded by 2). That is, P=PMCTDC(1)=PMCTSC(1)=PMCTSC(2). Therefore, in the framework of tissue P systems with cell division (respectively, cell separation), passing the maximum length of communication rules of the systems from 1 to 2 (respectively, from 2 to 3) amounts to passing from non– efficiency to efficiency, assuming that P=NP. That is, the cooperation of 2 objects (respectively, 3 objects) in the communication rules is a key feature that allows efficient solutions of NP–complete problems. 3.1 Efficiency of Tissue P Systems with Cell Division and without Environment In this section, we give a family of tissue P systems with cell division, communication rules of length at most 2, and without environment which solves the HAM-CYCLE problem, a well known NP–complete problem [3], in polynomial time, according to Definition 5. Let us recall that the HAM-CYCLE problem is the following: given a directed graph, to determine whether or not there exists a Hamiltonian cycle in the graph. Our starting point will be the family Π={Π(n)|n∈IN }of tissue P systems from TDC(2) provided in [19]. We will not recall in detail the definition of this solution, but let us provide an informal overview of the design. The authors follow a brute force approach, generating all possible combination of arcs from the graph, and then checking whether they represent a Hamiltonian cycle or not. Let us consider an arbitrary instance G=(V,E)oftheHAM-CYCLE problem, where |V|=n. In order to represent the generated paths, there are nspecial obects (u, v)1,...(u, v)nin the input multiset of the system for each arc (u, v)∈E. Having the object (u, v)iin the multiset of a cell after the generation stage is completed will mean “the arc (u, v)isthei−th component of the path associated with this cell”. All possible subsets of the input multiset are generated in the first stage of the computation, and then there is a checking stage that filters all invalid paths, as well as those which are not Hamiltonian cycles (a collection of auxiliary cells and symbols are used, but we will skip the details here). Finally, the computation ends with a final stage that sends the appropriate answer to the environment, depending on the results of all those checkings. The idea of the solution presented here is the following: starting from the above mentioned family Π, we construct a family Π={Π(n)|n∈IN }of tissue P systems from  TDC(2) such that Π(n) processes all instances Gof HAM-CYCLE with nnodes. The construction is implemented according to Definition 6.2 in [15], in such a way that each Π(n)simulates its counterpart Π(n)inanefficient way. We refer to [15] for details, but informally speaking, each computation from Π(n) matches (or “simulates”) an equivalent one from Π(n), except for a polynomial amount of additional auxiliary steps. Let us recall that for each n∈IN , Π(n) is the following tissue P system: Π(n)=(Γ, Σ, E,Min,Mh,My,Myes,Mno,Mout, Mei,j,k (1 ≤i, j, k ≤n),Mci(1 ≤i≤n),R,i in,i out) •The input alphabet is Σ={(i, j)k|1≤i, j, k ≤n}. •The working alphabet is Γ={(i, j)k,(i, j) k,(i, j) k|1≤i, j, k ≤n}∪ {(i, j)k,r,(i, j) k,r,(i, j) k,r |1≤i, j, k ≤n∧1≤r≤n3}∪ {wi|1≤i≤n3+6}∪{cr,h r,y r|1≤r≤n3}∪ {w,c,c,c ,h,h ,h ,h ,y,y,y,y,y,x,yes,no,#} •The alphabet of the environment is E={wi|1≤i≤n3+5}∪{w,c,y,h ,y,h ,y} •The initial multisets are ⎧ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎩ Min =cnyh Mei,j,k =(i, j) k,n3,1≤i, j, k ≤n Mci=cn3,1≤i≤n Mh=hn3 My=yn3 Myes =yes Mno =wn3+6 no Mout =x •The set Rconsists of the following rules: (1) (no , wr/w r−1,0), for 2 ≤r≤n3+6. (2) (no , w1/w, 0). (3) [ (i, j)k]in →[(i, j) k]in [#] in,for1≤i, j, k ≤n. (4) [ (i, j) k,r ]ei,j,k →[(i, j) k,r−1]ei,j,k [(i, j) k,r−1]ei,j,k , for 1 ≤i, j, k ≤nand 2 ≤r≤n3. (5) [ (i, j) k,1]ei,j,k →[(i, j) k]ei,j,k [(i, j) k]ei,j,k ,for1≤i, j, k ≤n. (6) [ cr]ci→[cr−1]ci[cr−1]ci,for1≤i≤n∧1≤r≤n3. (7) [ yr]y→[yr−1]y[yr−1]y,for1≤r≤n3. (8) [ hr]h→[hr−1]h[ar−1]h,for1≤r≤n3. (9) (in , (i, j) k/(i, j) k,e i,j,k), for 1 ≤i, j, k ≤n. (10) (in , c / c,c i), for 1 ≤i≤n. (11) (in , y / y,y). (12) (in , h / h,h). (13) (in, (i, j) k(i, j) k/λ, 0), for 1 ≤i, j, j,k,k≤n. (14) (in, (i, j) k(i,j) k/λ, 0), for 1 ≤i, i,j,k,k≤n. (15) (in, (i, j) k(i,j) k+1 /λ, 0), for 1 ≤i, i,j,j,k ≤n,andj=i. (16) (in, (i, j) k(i,j) k/λ, 0), for 1 ≤i, i,j,j,k≤n. (17) (in , c/c  ,0). (18) (in , y/y ,0). (19) (in , h/h  ,0). (20) (in , (i, j) kc /λ, 0) for 1 ≤i, j, k ≤n. (21) (in , y /y ,0). (22) (in , h /h  ,0). (23) (in , c h /λ, 0). (24) (in , y /y ,0). (25) (in , h y /λ,yes). (26) (yes, y yes/λ, out). (27) (out , x yes / λ , 0). (28) (no , w no / λ , out). (29) (out, xno/λ, 0). •The input cell is iin =in. •The output region is the environment, iout =0. Let us notice that |Γ|=3n4+7n3+ 23, |E| =n3+12andthedegreeofΠ(n)is q=n3+n+6.LetLabndenote the set of labels of cells in Π(n). Besides, the execution-time is n3+ 7 if the answer is affirmative and it is n3+ 8 if the answer is negative. We thus consider p(n)=n3+ 8 as the polynomial function needed for the construction of Π(n), according to Definition 6.2 in [15]. Now, for each n∈IN, let us construct, using Π(n) as a starting point, a tissue Psystemfrom  TDC(2) of degree q1=1+(n3+n+6)·(n3+ 10) + (n3+ 12), Π(n)=(Γ,Σ,E,M 0,M 1,...,M q1−1,R,i  in,i  out) defined as follows: •Γ=Γ∪{αj|0≤j≤n3+7}. •Σ=Σand E=∅. •Each one of the qcells of Π(n) provides a cell of Π(n) with the same label. In addition, Π(n)has: −For each one of the qcells of Π(n), n3+ 9 new cells, labelled by (i, 0),...,(i, n3+8), respectively, where istands for the original label of the cell in Π(n). −A distinguished cell labelled by 0. −A new cell, labelled by lb,foreachb∈E. •M  lb={α0},foreachb∈E,M (i,0) =Mi,foreachi∈Labn, and every other multiset of Π(n) is initially empty.