A linear-time tissue P system based solution for the 3-coloring problem

A Linear–time Tissue P System Based Solution for the 3–coloring Problem Daniel Díaz-Pernil1Miguel A. Gutiérrez-Naranjo2 Mario J. Pérez-Jiménez3Agustín Riscos-Núñez4 Research Group on Natural Computing Dpto. de Ciencias de la Computación e Inteligencia Artificial Universidad de Sevilla Sevilla, Spain Abstract In the literature, several examples of the efficiency of cell-like P systems regarding the solution of NPcomplete problems in polynomial time can be found (obviously, trading space for time). Recently, different new models of tissue-like P systems have received important attention from the scientific community. In this paper we present a linear-time solution to an NP-complete problem from graph theory, the 3–coloring problem, and we discuss the suitability of tissue-like P systems as a framework to address the efficient solution to intractable problems. Keywords: Membrane Computing, Tissue P Systems, cell division, 3–coloring problem. 1 Introduction Membranes are involved in many reactions taking place inside various compartments of a cell, and they act as selective channels of communication between different compartments as well as between the cell and its environment [1]. This paper is enclosed in the Natural Computing framework. More precisely, in the study of the structure and functioning of cells as living organisms able to process and generate information. Assuming this starting point, two different disciplines within Natural Computing can be found in the literature: Membrane Computing and Brane Calculi. 1Email: [email protected] 2Email: [email protected] 3Email: [email protected] 4Email: [email protected] Brane Calculi were recently introduced in [6], under the assumption that in living cells membranes are not merely containers, but they are actually highly dynamic and participate actively in the cell life. In this way, “computation” happens on the membranes, not inside them. On the other hand, Membrane Computing starts from the assumption that the processes taking place within the compartmental structure of a living cell can be interpreted as computations [19]. This emergent cross-disciplinary branch of Natural Computing was introduced by Gh. Păun in [18]. It has received important attention from the scientific community since then, with contributions by computer scientists, biologists, formal linguists and complexity theoreticians, enriching each others with results, open problems and promising new research lines. In fact, Membrane Computing has been selected by the Institute for Scientific Information, USA, as a fast Emerging Research Front in Computer Science, and [20]wasmentionedin[30] as a highly cited paper in October 2003. The computational devices in Membrane Computing are called Psystems. Roughly speaking, a P system consists of a membrane structure, in the compartments of which one places multisets of objects which evolve according to given rules in a synchronous non-deterministic maximally parallel manner 5. In the last years, many different models of P systems have been proposed. The most studied variants are characterized by a cell-like membrane structure, where the communication happens between a membrane and the surrounding one. In this model we have a set of nested membranes, in such a way that the graph of neighborhood relation is a tree. One of the topics in the field is the study of the computational power and efficiency of P systems. In particular, different models of these cell-like P systems have been successfully used in order to design solutions to NP-complete problems in polynomial time (see [10] and the references therein). These solutions are obtained by generating an exponential amount of workspace in polynomial time and using parallelism to check simultaneously all the candidate solutions. Inspired in living cells, cell-like P systems abstract the way of obtaining new membranes, mainly from two biological processes: mitosis (membrane division) and autopoiesis,see[14] (membrane creation). Both ways of generating new membranes have given rise to the corresponding P systems model: P systems with active membranes, where the new workspace is generated by membrane division and P systems with membrane creation, where the new membranes are created from objects. Both models are universal from a computational point of view, but technically, they are pretty different. In fact, nowadays there does not exist any theoretical result which proves that these models can simulate each other in polynomial time. Under the hypothesis P=NP, Zandron et al. [29] established the limitations of P systems that do not use membrane division concerning the efficient solution of NP-complete problems. This result was generalized by Pérez Jiménez et al. [25] 5A layman-oriented introduction can be found in [21] and further bibliography at [31]. obtaining a characterization of the P=NP conjecture by the polynomial time unsolvability of an NP-complete problem by language accepting P systems (without using rules that allow to construct an exponential number of membranes in polynomial time). We shall focus here on another type of P systems, the so-called (because of their membrane structure) Tissue P Systems. Instead of considering that membranes are hierarchically arranged, the membranes are placed in the nodes of a graph. This variant has two biological inspirations (see [17]): intercellular communication and cooperation between neurons. The common mathematical model of these two mechanisms is a net of processors dealing with symbols and communicating these symbols along channels specified in advance. The communication among cells is based on symport/antiport rules 6. Symport rules move objects across a membrane together in one direction, whereas antiport rules move objects across a membrane in opposite directions. >From the seminal definition of Tissue P systems [16,17], several research lines have been developed and other variants have arisen (see, for example, [2,5,7,12,13,27]). One of the most interesting variants of Tissue P systems was presented in [22]. In that paper, the definition of Tissue P systems is combined with the one of P systems with active membranes, yielding Tissue P systems with cell division. One of the main features of such Tissue P systems with cell division is related to their computational efficiency. In [22], a polynomial-time solution to the NPcomplete problem SAT is shown. In this paper we go on with the research in this variant and present a linear-time solution to another well-known NP-complete problem: the 3–coloring problem. The paper is organized as follows: first we recall some preliminaries and the definition of Tissue P systems with cell division. Next, recognizer Tissue P systems are briefly described. A linear–time solution to the 3–coloring problem is presented in the following section, with a short overview of the computation and the necessary resources. Finally, the main results, some conclusions and new open research lines are presented. 2 Preliminares In this section we briefly recall some of the concepts used later on in the paper. An alphabet,Σ, is a non empty set, whose elements are called symbols.An ordered sequence of symbols is a string. The number of symbols in a string uis the length of the string, and it is denoted by |u|. As usual, the empty string (with length 0) will be denoted by λ. The set of strings of length nbuilt with symbols from the alphabet Σis denoted by Σnand Σ∗=∪n≥0Σn.Alanguage over Σis a subset from Σ∗. Amultiset mover a set Ais a pair (A, f)where f:A→IN is a mapping. If 6This way of communication for P systems was introduced in [20]. m=(A, f)is a multiset then its support,supp(m),isdefinedassupp(m)={x∈ A|f(x)>0}and its size is defined as x∈Af(x). A multiset is empty (resp. finite) if its support is the empty set (resp. finite). If m=(A, f)is a finite multiset over A, then it will be denoted as m={{a1,...,a k}}, where each element aioccurs f(ai)times. Agraph Gis a pair G=(V,E)where Vis the set of vertices and Eis the set of edges, each one of which is a (unordered) pair of (different) vertices. If {u, v}∈E, we say that uis adjacent to v(and also vis adjacent to u). The degree of v∈Vis the number of adjacent vertices to v. Apath of length n≥1from a vertex xto a vertex yin a graph G=(V,E)is a sequence {v0,v 1,...,v n}of vertices such that v0=x,vn=yand {{vi,v i+1}|i= 0,...,n−1}⊆E. If there is a path from uto vin G, we will say that vis reachable from uin Gand it will be denoted by uGv. Two vertices uand vare connected in Gif uGv. A graph is connected if for every pair of different vertices from V, one of them is reachable from the other one. In what follows we assume the reader is already familiar with the basic notions and the terminology underlying P systems. For details, see [19]. 3 Tissue P Systems with Cell Division In the first definition of the model of tissue P systems [16,17] the membrane structure did not change along the computation. Based on the cell-like model of P systems with active membranes, Gh. Păun et al. presented in [22] a new model of tissue P systems with cell division. The biological inspiration is clear: alive tissues are not static network of cells, since cells are duplicated via mitosis in a natural way. The main features of this model, from the computational point of view, are that cells are not polarized (the contrary holds in the cell-like model of P Systems with active membranes, see [19]); the cells obtained by division have the same labels as the original cell and if a cell is divided, its interaction with other cells or with the environment is blocked during the mitosis process. In some sense, this means that while a cell is dividing it closes the communication channels with other cells and with the environment. Formally, a tissue P system with cell division of degree q≥1is a tuple of the form Π=(Γ,w 1,...,w q,E,R,i 0), where: (i) Γis a finite alphabet, whose symbols will be called objects. (ii) w1,...,w qare strings over Γ. (iii) E⊆Γ. (iv) Ris a finite set of rules of the following form: (a) Communication rules:(i, u/v, j),fori, j ∈{0,1,2,...,q},i=j,u, v ∈Γ∗. (b) Division rules:[a]i→[b]i[c]i,wherei∈{1,2,...,q}and a, b, c ∈Γ. (v) i0∈{0,1,2,...,q}. A tissue P system with cell division of degree q≥1can be seen as a set of qcells (each one consisting of an elementary membrane) labelled by 1,2,...,q. We will use 0to refer to the label of the environment, and i0denotes the output region (which can be the region inside a membrane or the environment). The strings w1,...,w qdescribe the multisets of objects placed in the qcells of the system. We interpret that E⊆Γis the set of objects placed in the environment, each one of them in an arbitrary large amount of copies. The communication rule (i, u/v, j)can be applied over two cells iand jsuch that uis contained in cell iand vis contained in cell j. The application of this rule means that the objects of the multisets represented by uand vare interchanged between the two cells. The division rule [a]i→[b]i[c]ican be applied over a cell icontaining object a. The application of this rule divides this cell into other two cells with the same label. All the objects in the original cell are replicated and copied in each of the new cells, with the exception of the object a, which is replaced by the object bin the first new cell and by cin the second one. Rules are used as usual in the framework of membrane computing, that is, in a maximally parallel way. In one step, each object in a membrane can only be used for one rule (non-deterministically chosen when there are several possibilities), but any object which can participate in a rule of any form must do it, i.e, in each step we apply a maximal set of rules. This way of applying rules has only one restriction when a cell is divided, the division rule is the only one which is applied for that cell in that step; the objects inside that cell do not evolve in that step. 4 Recognizer Tissue P Systems with Cell Division NP-completeness has been usually studied in the framework of decision problems. Let us recall that a decision problem is a pair (IX,θ X)where IXis a language over a finite alphabet (whose elements are called instances)andθXis a total boolean function over IX. In order to study the computing efficiency for solving NP-complete decision problems, a variant of tissue P systems with cell division is introduced in [22]: recognizer tissue P systems. The key idea of such recognizer system is the same one as from recognizer P systems with cell-like structure. Recognizer cell-like P systems were introduced in [26] and they are the natural framework to study and solve decision problems within Membrane Computing, since deciding whether an instance has an affirmative or negative answer is equivalent to deciding if a string belongs or not to the language associated with the problem. In the literature, recognizer cell-like P systems are associated in a natural way with P systems with input. The data related to an instance of the decision problem has to be provided to the P system in order to compute the appropriate answer. This is done by codifying each instance as a multiset placed in an input membrane. The output of the computation (yes or no) is sent to the environment. In this way, cell-like P systems with input and external output are devices which can be seen as black boxes, in the sense that the user provides the data before the computation starts, and then waits outside the P system until it sends to the environment the output in the last step of the computation. A recognizer tissue P system with cell division of degree q≥1is a tuple Π=(Γ,Σ,w 1,...,w q,E,R,i in,i o) where •(Γ,w 1,...,w q,E,R,i o)is a tissue P system with cell division of degree q≥1(as defined in the previous section). •The working alphabet Γhas two distinguished objects yes and no,presentinat least one copy in w1,w2, ..., wqbut not present in E. •Σis an (input) alphabet strictly contained in Γ. •iin ∈{1,...,q}is the input cell. •The output region iois the environment. •All computations halt. •If Cis a computation of Π, then either the object yes or the object no (but not both) must have been released into the environment, and only in the last step of the computation. The computations of the system Πwith input w∈Γ∗start from a configuration of the form (w1,w 2,...,w iin w,...,w q;E), that is, after adding the multiset w to the contents of the input cell iin. We say that the multiset wis recognized by Πif and only if the object yes is sent to the environment, in the last step of the corresponding computation. We say that Cis an accepting computation (respectively, rejecting computation) if the object yes (respectively, no) appears in the environment associated to the corresponding halting configuration of C. Definition 4.1 We say that a decision problem X=(IX,θ X)is solvable in polynomial time by a family Π={Π(n): n∈IN }of recognizer tissue P systems with cell division if the following holds: •The family Πis polynomially uniform by Turing machines, that is, there exists a deterministic Turing machine working in polynomial time which constructs the system Π(n)from n∈IN . •There exists a pair (cod, s)of polynomial-time computable functions over IXsuch that: −for each instance u∈IX,s(u)is a natural number and cod(u)is an input multiset of the system Π(s(u)); −the family Πis polynomially bounded with regard to (X,cod, s),thatis,there exists a polynomial function p, such that for each u∈IXevery computation of Π(s(u)) with input cod(u)is halting and, moreover, it performs at most p(|u|) steps; −the family Πis sound with regard to (X,cod,s),thatis,foreachu∈IX,ifthere exists an accepting computation of Π(s(u)) with input cod(u),thenθX(u)=1; −the family Πis complete with regard to (X, cod,s),thatis,foreachu∈IX,if θX(u)=1, then every computation of Π(s(u)) with input cod(u)is an accepting one. In the above definition we have imposed to every P system Π(n)to be confluent, in the following sense: every computation of a system with the same input multiset must always give the same answer. We denote by PMCTD the set of all decision problems which can be solved by means of recognizer tissue P systems with cell division in polynomial time. 5 A Solution for the 3–coloring problem Ak–coloring (k≥1) of an undirected graph G=(V,E)is a function f:V→ {1,...,k}.WesaythatGis k–colorable if there exists a k–coloring, f, such that f(u)=f(v)for every edge {u, v}∈E(the k–coloring fis valid). If we represent the numbers 1,2,...,n as colors, then adjacent vertices must have different colors by a valid k–coloring.. The k–coloring problem is the following: given an undirected graph G,decide whether or not Gis k-colorable; that is, if there exists a valid 3–coloring of G. This problem is related to the famous Four Color Conjecture (proved by Appel and Haken [3,4]). It is a special case of the problem of k-colorability of a graph, in which the range of Cis {1,...,k}with kbeing specified as part of the instance. The NP-completeness of the 3–coloring problem was proved by Stockmeyer [28](see [9]). Next, we will see that the 3–coloring problem can be solved in linear time by a family of recognizer tissue P systems with cell division. Let us consider a graph G=(V,E),whereV={Ai:1≤i≤n}is the set of vertices and E⊆{{Ai,A j}:1≤i<j≤n}is the set of edges. If {Ai,A j}∈E then we denote Aij ={Ai,A j}. We will address the resolution via a brute force algorithm, in the framework of recognizer tissue P systems with cell division, which consists in the following phases: •Generation Stage: The initial cell, labelled by 2, is divided into two new cells; and the division are iterated until we have all possible candidate solutions to the problem (one solution for each membrane). Simultaneously, in the membrane labelled by 1 a counter evolves, and it will determine the moment in which the checking stage starts. •Pre–checking Stage: After obtaining all possible 3–colorings encoded in cells labelled by 2, this stage provides objects Rij ,G ij,B ij in such cells, for every edge Aij. •Checking Stage: Once we obtain some objects Rij,G ij ,B ij in cells labelled by 2, we check if there exists a pair of adjacent vertices with the same color in the corresponding candidate solution. •Output Stage: The system sends to the environment the right answer according D. Díaz-Pernil et al. / Electronic Notes in Theoretical Computer Science 171 (2007) 81–93 87 to the results of the previous stage. Next, we provide a linear-time solution for the 3–coloring problem by a family of recognizer tissue P systems with cell division. Let us recall that the function n, m=((n+m)(n+m+1)/2) + nis primitive recursive and bijective from IN 2onto IN . Also, the inverse function of his polynomial. For each n, m ∈IN , we will consider the system Π(n, m)=(Γ(n, m),Σ(n),w 1,w 2(n),R(n, m),E(n, m),i in,i 0) where: •Γ(n, m)is the set {Ai,R i,T i,B i,G i, Ri, Bi, Gi:1≤i≤n}∪ {ai:1≤i≤3n+log2m+11}∪{ci:1≤i≤2n+1}∪ {di:1≤i≤log2m+1}∪{fi:2≤i≤n+log2m+6}∪ {Aij,P ij, P ij,R ij,B ij,G ij :1≤i<j≤n}∪{b, D, E, e, T, S, N, , yes,no} •Σ(n)={Aij :1≤i<j≤n} •w1={{a1,b,c 1,yes,no}} •w2(n)={{D,A1,...,A n}} •R(n, m)is the set of rules: (i) Division rules: r1,i ≡[Ai]2→[Ri]2[Ti]2for i=1,...,n r2,i ≡[Ti]2→[Bi]2[Gi]2for i=1,...,n (ii) Communication rules: r3,i ≡(1,a i/ai+1,0) for i=1,...,2n+log2m+10 r4,i ≡(1,c i/c2 i+1,0) for i=1,...,2n r5≡(1,c 2n+1/D, 2) r6≡(2,c 2n+1/d1E,0) r7,i ≡(2,d i/d2 i+1,0) for i=1,...,log2m r8≡(2,E/ef 2,0) r9,i ≡(2,f i/fi+1,0) for i=2,...,n+log2m+5 r10,ij ≡(2,d log2m+1Aij/Pij ,0) for 1≤i<j≤n r11,ij ≡(2,P ij /RijPij,0) for 1≤i<j≤n r12,ij ≡(2, Pij/BijGij,0) for 1≤i<j≤n r13,ij ≡(2,R iRij/RiRj,0) for 1≤i<j≤n r14,ij ≡(2,B iBij/BiBj,0) for 1≤i<j≤n r15,ij ≡(2,G iGij/GiGj,0) for 1≤i<j≤n r16,j ≡(2, RjRj/, 0) for 1≤j≤n r17,j ≡(2, BjBj/, 0) for 1≤j≤n r18,j ≡(2, GjGj/, 0) for 1≤j≤n r19 ≡(2,e/λ,0) r20 ≡(2,e f n+log2m+6/T, 0) r21 ≡(2,T/λ,1) r22 ≡(1,bT/S,0) r23 ≡(1,S yes/λ, 0) r24 ≡(1,b a 3n+log2m+11/N, 0) r25 ≡(1,N no/λ, 0) •E(n, m)=Γ(n, m)−{yes,no} •iin =2is the input cell. •i0=0is the output region. 5.1 An Overview of the Computation First of all we define a polynomial encoding of the 3–coloring problem in the family Πconstructed in the previous section. Let u=(V,E)be an instance of the problem, with nvertices and medges. Then we consider a size mapping on the set of instances defined as s(u)=n, m. The codification of the instance will be the multiset cod(u)=E. Next we describe informally how the recognizer tissue P system with cell division Π(s(u)) with input cod(u)works. Let us start with the generation stage. In this stage we have two parallel processes. •On the one hand, in the cell labelled by 1 we have two counters: ai, which will be used in the answer stage and ci, which will be multiplied until step 2n,where4n copies of c2n+1 are obtained. •On the other hand, in the cell labelled by 2, the division rules are applied. For each object Ai(which codifies a vertex of the graph) we get (in two steps) three cells labelled by 2, each of them encoding one of the three colors by means of the objects Ri,G i,B i. After the appropriate divisions, in the step 2nwe get exactly 3ncells encoding all the possible 3–colorings of the graph. In this way, after the 2n–th step the generation stage is finished and the checking stage starts. In this moment, the content of the cell labelled by 1 is {{a2n+1,c 4n 2n+1,b,yes,no}}, and there are 3ncells each of them containing the object D, the objects Aij, and a function from Vto {1,2,3}(we will identify the colors by red,R,green,G,andblue,B). In the step 2n+1,3ncopies of c2n+1 in the cell 1 is traded by 3nobjects D that appears one in each cell labelled by 2. Notice that 4n−3nspare copies of the counter cwill remain in cell 1. When the object c2n+1 arrives to the cell labelled by 2, the communication starts. At the beginning of the process, we pay attention to the counters dand f. The first one will be multiplied until at least mcopies are obtained, so that they can cooperate with the minput symbols Aij that represent the edges. This is achieved in the 2n+log2m+2–th step (for the sake of simplicity, we will denote γ=2n+log2m+2). The object fwill be useful in order to send an object Tto