Solving 3-COL with Tissue P Systems

Solving 3-COL with Tissue P Systems Daniel D´ıaz-Pernil, Miguel A. Guti´errez-Naranjo, Mario J. P´erez-Jim´enez Dpto. de Ciencias de la Computaci´on e Inteligencia Artificial E.T.S. Ingenier´ıa Inform´atica. Universidad de Sevilla Avda. Reina Mercedes s/n, 41012, Sevilla, Espa˜na {sbdani, magutier, marper}@us.es Summary. In the literature, several examples of the efficiency of cell-like P systems in order to solve NP-complete problems in polynomial time can be found. Recently, various 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, the 3-COL problem, and discuss the possibilities of tissue-like P systems to solve hard problems. 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]. Membrane Computing is a branch of Natural Computing which starts from the assumption that the processes taking place in the compartmental structure of a living cell can be interpreted as computations. This is a new cross-disciplinary field with contributions by computer scientists, biologists, formal linguists and complexity theoreticians, enriching each others with results, open problems and promising new research lines. One of the topics in that field is the study of the computational power and efficiency of devices with multisets distributed along the regions of a membrane structure, and with rules for rewriting or moving the elements of such multisets. This emergent branch of Natural Computing was introduced by Gh. P˘aun in [21]. Since then it has received important attention from the scientific community. 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] was mentioned in [28] as a highly cited paper in October 2003. The devices of this model are called P systems. Roughly speaking, a P system consists of a membrane structure, in the compartments of which one places 18 D. D´ıaz-Pernil, M.A. Guti´errez-Naranjo, M.J. P´erez-Jim´enez multisets of objects which evolve according to given rules in a synchronous nondeterministic maximally parallel manner1. In the last years, many different models of P systems have been proposed. If the different models are classified according to the membrane structure, the most studied variant is characterized by a cell-like membrane structure, where the communication channels are from a membrane to the surrounding one. In this model we have a set of nested membranes where the graph of neighborhood relation is a tree. 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 [9] and references therein). These solutions are obtained by generating an exponential amount on workspace in polynomial time and using parallelism to check simultaneously all the candidates to solution. 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 [13] (membrane creation). Both ways of generating new membranes have given rise to different variants of P systems: 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 P6=NP, Zandron et al. [27] 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´erez-Jim´enez et al. [17] obtaining a characterization of the P6=NP conjecture by the polynomial time unsolvability of an NP-complete problem by language accepting P systems (without membrane division rules). We shall focus here on a second 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, all of them at the same level. This variant has two starting points (see [15]): 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 rules2. 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 [14, 15], several research lines have been developed and other variants have arisen (see, for example, [2, 5, 6, 11, 12, 23]). One of the most interesting variants of tissue P systems was presented in [19]. This paper combines the definitions of tissue P systems and P systems with 1A layman-oriented introduction can be found in [22] and further bibliography at [29]. 2This way of communication for P systems was introduced in [20]. Solving 3-COL with Tissue P Systems 19 active membranes and consider tissue P systems (with the communication done through symport/antiport rules) with cell division rules of the same form as in P systems with active membranes, but without using polarizations. One of the main features of these tissue P systems with cell division is related to their computational efficiency. In [19], a polynomial-time solution to the NP- complete 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-COL 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-COL 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 the string is the length of the string. 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. A language over Σis a subset from Σ?. Let Dbe a set. A multiset over Dis a pair3hD, fiwhere f:D→Nis a mapping. If A=hA, fiis a multiset, its support,supp(A) is defined as supp(A) = {x∈A|f(x)>0}and its size denoted by |A|is defined as |A|=X a∈A f(a). A multiset is empty (resp. finite) if its support is the empty set (resp. finite). The set of all the multisets on Dis denoted by M(D). If m= (A, f) is a finite multiset on A, then it will be denoted as m= {{a1, . . . , am}}, where the elements aioccurs f(ai) times. Adirected graph Gis a pair G= (V, E) where Vis a set and E⊆V×V. If (u, v)∈Eor (v, u)∈E, we will say that uis adjacent to v. The degree of v∈V is the number of adjacent vertices to v. Apath of length nfrom a vertex xto a vertex yin a directed graph G= (V, E) is a sequence {v0, v1, . . . , vn}of vertices such that v0=x,vn=yand {(vi, vi+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. The vertices u and vare connected in Gif uÃGvor vÃGu. The directed graph is connected if 3A detailed presentation of multisets can be found, for example, in [26]. 20 D. D´ıaz-Pernil, M.A. Guti´errez-Naranjo, M.J. P´erez-Jim´enez 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 [24]. 3 Tissue P Systems with Cell Division In the first works on tissue P systems the membrane structure does not change along the computation [14, 15]. Based on the cell-like model of P systems with active membranes, in [19] a new model of tissue P systems is presented, with cells able to divide. The biological inspiration is clear. Alive tissues are not static network of cells. Cell are duplicated via mitosis in a natural way. As computational model, the main features of this model are that cells are not polarized (the contrary holds in the cell-like model of P systems with active membranes, see [24]); the cells obtained by division have the same labels as the father cell and if a cell is divided, the interaction of the cell with other cells or with the environment is blocked during the mitosis process. In some sense, this means that a cell which divides, first cuts all its communication channels with the other cells and with the environment. Formally, a tissue P system with cell division is a construction of the form Π= (Γ, w1, . . . , wm, E, R, io), where: 1. m≥1 is the initial degree of the system. At the beginning, the system has m cells, labeled by 1,2, . . . , m. 2. Γis a finite alphabet, whose symbols will be called objects. 3. w1, . . . , wmare strings over Γ, describing the multisets of objects placed in the mcells of the system. 4. E⊆Γis the set of objects placed in the environment in an arbitrary large amount of copies. 5. Ris a finite set of evolution rules of the following form: (a) Communication rules: (i, x/y, j), for i, j ∈ {0,1,2, . . . , m}, i 6=j,x, y ∈ Γ∗, where 1,2, . . . , m are the labels of the cells of the system (0 is the label of the environment); when the rule (i, x/y, j) is applied, the objects of the multiset represented by xare sent from the region ito the region j and simultaneously, the objects of the multiset represented by yare sent from the region jto the region i. (b) Division rules: [a]i→[b]i[c]i, where i∈ {1,2, . . . , m}and a, b, c ∈Γ; when an object aappears in a cell labeled by i, the cell divides into other two membranes 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. 6. iois the output cell. Solving 3-COL with Tissue P Systems 21 Rules are applied 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 evolve by a rule of any form must do it, i.e., in each step we apply a maximal set of rules and no other rule can be added. This way of applying rules has only one restriction: when a cell is divided, the division rule is the only which is applied for that cell in that step; the objects inside that cell do not evolve in the step when the cell is divided. 4 Recognizer tP Systems Usually, NP-completeness has been 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 a similar way to other P system models, some special features have to be imposed for studying the efficiency of such systems in order to solve NP-complete problems. In order to study the computing efficiency for solving NP-complete decision problems in [19] a variant of tissue P systems with membrane division is introduced: recognizer tissue P systems with input. The key idea of such recognizer system is the same as for recognizer P systems with cell-like structure. Recognizer P systems were introduced in [18] and are the natural framework to study and solve decision problems, 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 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, 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 is a tuple Π= (O, Σ, w1, . . . , wm, E, R, iin, io), where: •(O, w1, . . . , wm, E, R, iin) is a tissue P system. •The working alphabet Ohas two distinguished objects yes and no, present in at least one copy in w1,w2, . . . , wnbut not present in E. 22 D. D´ıaz-Pernil, M.A. Guti´errez-Naranjo, M.J. P´erez-Jim´enez •Σis an (input) alphabet strictly contained in O. •iin ∈ {1, . . . , m}is the input cell. •The output region is 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. Another important feature of P systems is the non-determinism. When designing a family of recognizer P systems, one has to be aware of that, because all possible non-deterministic computations must produce the same answer. Definition 1. AP system with input is a tuple (Π, Σ, iΠ), where: (a) Πis a P system, with working alphabet Γ, with pmembranes labeled by 1, . . . , p, and initial multisets w1, . . . , wpassociated with them; (b) Σis an (input) alphabet strictly contained in Γ; the initial multisets are over Γ−Σ; and (c) iΠis the label of a distinguished (input) membrane. The computations of the system Πstart from configurations of the form (w1, w2, . . . , winw, . . . , wm;E), where w∈Γ∗(that is, after adding the multiset wto the contents of the input cell). We say that the multiset wis recognized by Πif and only if the object yes is sent to the environment. 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 2. Let Fbe a class of recognizer P systems. We say that a decision problem X= (IX, θX)is solvable in polynomial time by a family Π= (Π(n))n∈N, of F, and we denote this by X∈PMCF, if the following holds: •The family Πis polynomially uniform by Turing machines, that is, there exists a deterministic Turing machine constructing Π(n)from n∈Nin polynomial time. •There exists a pair (cod, s)of polynomial-time computable functions over IX such 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), 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, moreover, it performs at most p(|u|)steps; −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; −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. Solving 3-COL with Tissue P Systems 23 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 must always give the same answer. The set of all decision problems which can be solved by means of recognizer tP systems with cell division in a number of steps bounded by a mapping fform the complexity4class MCT D(f). We are interested in polynomial time solutions, therefore we consider the class PMCT D, obtained as the union of the classes MCT D(f), for all polynomials f. 5 A Solution to 3-COL Let Gbe a graph with V(G) as set of vertices and E(G) as set of edges. A k-coloring of a graph Gis a function C:V(G)→ {1, . . . , k}such that for all v, w ∈V(G), if C(v) = C(w), then ((v, w)6∈ E(G). The k−COL problem is to determine the number of such k-colorings for 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-COL problem was proved by Stockmeyer [25] (see [8]). Next, we will see that the 3-COL problem can be solved by tissue P systems with cellular division in linear time. Let us consider a graph G= (U, V ), where U={ui|1≤i≤n}is the set of vertices and V={vj|vj=uj1uj2∧1≤j≤m∧1≤j1< j2≤n}is the set of edges. Let us consider (n, (Aij)n) in order to denote a generic instance of the problem, with nthe size of the graph G, i.e., the number of vertices in Gand let Abe the set of the edges in the graph G, with (Aij)n= (Aij :AiAj∈V∧1≤i < j ≤n). 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, labeled by 2, is divided into two new cells. These cells are divided again, and so on. After several divisions we have an element Ri,Bior Gifor each element Ai. Hence, after an appropriate number of divisions, in each cell labeled with 2 we will have a candidate solution to the problem. Simultaneously, in the membrane labeled by 1 a counter evolves to determine the moment in which the checking stage starts. 4More precise definitions of complexity classes in terms of membrane computing can be found in [16]. 24 D. D´ıaz-Pernil, M.A. Guti´errez-Naranjo, M.J. P´erez-Jim´enez •Checking Stage: After the generation stage, the checking stage begins. For each cell labeled by 2, we check if there exists a pair of adjacent vertices with the same color. If this happens, an element [is brought from the environment. Otherwise, the object [is not brought in. •Output Stage: The system sends to the environment the right answer according to the previous stage. 1. Answer Yes: There exists a cell labeled by 2 such that it does not contain an object [. In this case, an object Tis sent to the cell labeled by 1 and an object Yes is sent to the environment. 2. Answer No: It is the converse case. If all the cells labeled by 2 contain an object [, then the cell labeled by 1 does not receive any object T, and an object No is sent to the environment. Next, we provide a linear time solution of 3-COL by a family of recognizer tissue P systems with membrane division. Let us consider a size mapping on the set of instances of the problem. Let sbe the mapping s:I3−COL →Nwhere I3−COL is the set of all instances u= (n, (Aij)n) of the 3-COL problem and s(u) = n. Obviously, sis linear time computable. For each n∈N, we will consider the system Π(n) = (Γ(n), Σ(n),R(n),E(n),M1(n),M2(n), i(n), o(n)), where: •Γ(n) = {Ai, Ri, Ti, Bi, Gi, Ri, Bi, Gi|1≤i≤n}∪{ai|1≤i≤2n+dlog2me+ 12}∪{ci|1≤i≤2n+1}∪{di|1≤i≤ dlog2me+1}∪{fi|2≤i≤ dlog2me+ 7} ∪ {Pij, Pij, Rij , Bij, Gij |1≤i < j ≤n}∪{b, D, E, e, T, S, N, [, yes,no}, •Σ(n) = {Aij |1≤i < j ≤n}, • M1(n) = a1, b, c1,yes,no, • M2(n) = D, A1, . . . , An, • R(n) is the set of rules: 1. Division rules: r1,i = [Ai]2→[Ri]2[Ti]2for i= 1, . . . , n, r2,i = [Ti]2→[Bi]2[Gi]2for i= 1, . . . , n, 2. Communication rules: r3,i = (1, ai/ai+1,0) for i= 1, . . . , 2n+dlog2me+ 11, r4,i = (1, ci/c2 i+1,0) for i= 1 . . . , 2n, r5= (1, c2n+1/D, 2), r6= (2, c2n+1/d1E, 0), r7,i = (2, di/d2 i+1,0) for i= 1, . . . , dlog2me, r8= (2, E/e f2,0), r9,i = (2, fi/fi+1,0) for i= 2, . . . , dlog2me+ 6, r10,ij = (2, ddlog2me+1Aij/Pij ,0) for 1 ≤i < j ≤n, r11,ij = (2, Pij/Rij Pij,0) for 1 ≤i < j ≤n, r12,ij = (2, Pij/BijGij ,0) for 1 ≤i < j ≤n, Solving 3-COL with Tissue P Systems 25 r13,ij = (2, RiRij/RiRj,0) for 1 ≤i < j ≤n, r14,ij = (2, BiBij/BiBj,0) for 1 ≤i < j ≤n, r15,ij = (2, GiGij/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, fdlog2me+7e/T, 0), r21 = (2, T/λ, 1), r22 = (1, b T/S, 0), r23 = (1, Syes/λ, 0), r24 = (1, a2n+dlog2me+12b/N, 0), r25 = (1, Nno/λ, 0), • E(n) = Γ− {yes,no}, •i(n) = 2 is the input cell, •o(n) = env is the output cell. 5.1 An overview of the computation First of all we define a polynomial encoding of the 3-COL problem in the family Πconstructed in the previous section. Given an instance uof the problem, u= (n, (Aij)n), with size s(u) = nthe codification of the instance will be the multiset cod(u) = {{Aij |1≤i < j ≤n}}. 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. Recall that if a division rule is triggered, the communication rules do not work. In this stage we have two parallel processes. •On the one hand, in the cell labeled by 1 we have two counters: ai, which will be used in the answer stage and ci, which will be multiplied until step 2n, where 4ncopies are obtained. •On the other hand, in the cell labeled by 2, the division rules are applied. For each object Ai(which codifies a vertex of the graph) we get three cells labeled by 2, each of them encoding one of the three colors. After the appropriate divisions, in the step 2nwe get exactly 3ncells encoding all the possible 3-colorings of the graph In this way, in the step 2nthe generation step is finished and the checking stage starts. One of the copies of the counter cin the cell 1 is traded by each object Dthat appears in each cell labeled by 2. Therefore, in the cell 1, there remain 4n−3n copies of the counter c. When the object c2n+1 arrives to the cell labeled by 2, the communication starts. At the beginning of the process, we pay attention to the counters dand f. The former, d, will be multiplied until at least mcopies are obtained. At this point, we