A uniform family of tissue P systems with cell division solving 3-COL in a linear time

A uniform family of tissue P systems with cell division solving 3-COL in a linear time Daniel Díaz-Pernil, Miguel A. Gutiérrez-Naranjo, Mario J. Pérez-Jiménez ∗, Agustín Riscos-Núñez Research Group on Natural Computing, Universidad de Sevilla, Sevilla, Spain Keywords: Membrane computing Tissue P systems Cell division 3-coloring problem a b s t r a c t Several examples of the efficiency of cell-like P systems regarding the solution of NPcomplete problems in polynomial time can be found in the literature(obviously, trading space for time). Recently, different new models of tissue-like P systems have received much 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. 1. Introduction This paper is within the Natural Computing framework and, more precisely, in the study of the structure and functioning of cells as living organisms able to process and generate information. We focus on membranes, which 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]. Assuming this starting point, two different disciplines within Natural Computing can be found in the literature: Membrane Computing and Brane Calculi. 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, and 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 [18]. This emergent cross-disciplinary branch of Natural Computing was introduced by Păun in [17]. It has received important attention from the scientific community since then, with contributions from computer scientists, biologists, formal linguists and complexity theoreticians, enriching each other with results, open problems and promising new research lines. In fact, Membrane Computing was selected by the Institute for Scientific Information, USA, as a fast Emerging Research Front in Computer Science, and [19] was mentioned in [29] as a highly cited paper in October 2003. The computational devices in Membrane Computing are called P systems. 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.1 In recent years, many different models of P systems have been proposed. The most studied variants are characterized by acell-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. ∗Corresponding author. E-mail address: [email protected] (M.J. Pérez-Jiménez). 1A layman-oriented introduction can be found in [20] and further bibliography at [30]. 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 [9] 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 by 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 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 quite different. In fact, there are no theoretical results which prove that these models can simulate each other in polynomial time. Under the hypothesis P6= NP, Zandron et al. [28] 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. [24] obtaining a characterization of the P6= 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 Tissue P Systems(because of their membrane structure). Instead of considering a hierarchical arrangement, membranes are placed in the nodes of a graph. This variant has two biological inspirations (see [16]): 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.2Symport 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 [15,16], several research lines have been developed and other variants have arisen (see, for example, [2,5,7,11,12,26]). One of the most interesting variants of Tissue P systems was presented in [21]. 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 [21], a polynomial-time solution to the NP-complete problem SAT is shown. In this paper we go on with the research in this model 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, including a short overview of the computation and of the necessary resources. We also include the formal verification of the solution. Finally, the main results, some conclusions and new open research lines are presented. 2. Preliminaries 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→Nis a mapping. If m=(A,f)is a multiset then its support is defined as supp(m)= {x∈A|f(x)>0}and its size is defined as Px∈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, and supp(m)= {a1, . . . , ak}, then it will be denoted as m= {{af(a1) 1, . . . , af(ak) k}}. That is, superscripts indicate the multiplicity of each element, and if f(x)=0 for any x∈A, then this element is omitted. 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. In what follows we assume the reader is already familiar with the basic notions and the terminology underlying P systems. For details, see [18]. 3. Tissue P systems with cell division In the first definition of the model of tissue P systems [15,16] the membrane structure did not change along the computation. Based on the cell-like model of P systems with active membranes, Păun et al. presented in [21] a new model 2This way of communication for P systems was introduced in [19]. 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 [18]); 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 its communication channels. Formally, a tissue P system with cell division of degree q≥1 is a tuple of the form Π=(Γ,w1,. . . , wq,E,R,i0), where: (1) Γis a finite alphabet, whose symbols will be called objects. (2) w1, . . . , wqare strings over Γ. (3) E⊆Γis the alphabet of the environment. (4) Ris a finite set of rules of the following form: (a) Communication rules:(i,u/v,j), for i,j∈ {0,1,2, . . . , q},i6= j,u,v∈Γ∗. (b) Division rules:[a]i→ [b]i[c]i, where i∈ {1,2, . . . , q}and a,b,c∈Γ. (5) i0∈ {0,1,2, . . . , q}. A tissue P system with cell division of degree q≥1 can be seen as a set of qcells (each one consisting of an elementary membrane) labelled by 1,2, . . . , q. We shall use 0 as the label of the environment, and i0denotes the output region (which can be a region inside a membrane or the environment). The communication rules determine an implicit net of channels, where the nodes are the cells and the edges indicate if it is possible for pairs of cells to communicate directly. This is a dynamical graph, as new nodes can appear produced by the application of division rules. Note also that the connections depend only on the label of the cell, and thus when a cell is divided, the two new cells will have identical connections. Nevertheless, this graph is just an intuition, we shall not handle it explicitly along the computations. The strings w1, . . . , wqdescribe 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 two new 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 special class of tissue P systems with cell division is introduced in [21]: 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 [25] 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 whether or not a string belongs 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 encoding 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 (see [23] for details). A recognizer tissue P system with cell division of degree q≥1 is a tuple Π=(Γ,Σ,w1,. . . , wq,E,R,iin,i0) where •(Γ,w1, . . . , wq,E,R,io)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, present in at least one copy in some initial multisets w1, ..., wq, but not present in E. •Σis an (input) alphabet strictly contained in Γ. •iin ∈ {1, . . . , q}is the input cell. •The output region i0is 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,w2, . . . , wiin w, . . . , wq;E), that is, after adding the multiset wto 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 or rejecting computation if the object yes or no), respectively, appears in the environment associated with the corresponding halting configuration of C. Definition 1. We say that a decision problem X=(IX,θX)is solvable in polynomial time by a family 5 5 5= {Π(n):n∈N}of recognizer tissue P systems with cell division if the following holds: •The family 5 5 5is polynomially uniform by Turing machines, that is, there exists a deterministic Turing machine working in polynomial time which constructs the system Π(n)from n∈N. •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 5 5 5is 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 5 5 5is 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 5 5 5is 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. In the above definition we assume 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}, where the numbers are interpreted as colors. We say that Gis k-colorable if there exists a k-coloring, f, such that f(u)6= f(v)for every edge {u,v} ∈ E(such a k-coloring fis said to be valid). The 3-coloring problem is the following: given an undirected graph G, decide whether or not Gis 3-colorable; that is, if there exists a valid 3-coloring of G. For the sake of readability, we shall use {R,G,B}instead of {1,2,3}to represent the colors (R, Gand Bstanding for red, green and blue, respectively). This problem is related to the famous Four Color Conjecture (proved by Appel and Haken [3,4]). It is a particular case of the colorability problem: Given an undirected graph Gand a number k, decide whether Gis k-colorable. The NP-completeness of the 3-coloring problem was proved by Stockmeyer [27] (see [8]). Next, we shall prove that the 3-coloring problem can be solved in a linear time by a family of recognizer tissue P systems with cell division. We shall address the resolution via a brute force algorithm, which consists in the following stages: •Generation stage: The initial cell labelled by 2 is divided into two new cells; and the divisions are iterated until a cell has been produced for each possible candidate solution. Simultaneously, in the cell labelled by 1 there is a counter that 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,Gij,Bij in such cells, for every edge Aij. •Checking stage: Objects Rij,Gij,Bij will be used in cells labelled by 2 to check if there exists a pair of adjacent vertices with the same color in the corresponding candidate solution (Rij checks if nodes viand vjare both red, and analogously Gij and Bij for green and blue colors). •Output stage: The system sends to the environment the right answer according to the results of the previous stage. Let us recall that the function hn,mi = ((n+m)(n+m+1)/2)+nis a primitive recursive bijection between N2and N. Moreover, its inverse function is also polynomial. Next, we shall define a family 5 5 5= {Π(i):i∈N}such that each system Π(i)will solve all instances of graphs with nvertices and medges, where i= hn,mi, provided that the appropriate input multiset is provided. For each n,m∈N, we shall consider the system Π(hn,mi)=(Γ(hn,mi), Σ(n), w1,w2(n), R(hn,mi), E(hn,mi), iin,i0) where: •Γ(hn,mi)is the set {Ai,Ri,Gi,Bi,Ti,Ri,GiBi,:1≤i≤n} ∪ {ai:1≤i≤2n+m+ dlog me + 11} ∪ {ci:1≤i≤2n+1} ∪ {di:1≤i≤ dlog me + 1}∪{zi:2≤i≤m+ dlog me + 6} ∪ {Aij,Pij,Pij,Rij,Gij,Bij :1≤i<j≤n}∪{b,D,D,e,T,S,N,[,yes,no}. •Σ(n)= {Aij :1≤i<j≤n} •w1= {{a1,b,c1,yes,no}} •w2(n)= {{D,A1, . . . , An}} •R(hn,mi)is the set of rules: (1) Division rules: r1,i≡ [Ai]2→ [Ri]2[Ti]2for i=1, . . . , n r2,i≡ [Ti]2→ [Gi]2[Bi]2for i=1, . . . , n (2) Communication rules: r3,i≡(1,ai/ai+1,0)for i=1, . . . , 2n+m+ dlog me + 10 r4,i≡(1,ci/c2 i+1,0)for i=1, . . . , 2n r5≡(1,c2n+1/D,2) r6≡(2,c2n+1/d1D,0) r7,i≡(2,di/d2 i+1,0)for i=1, . . . , dlog me r8≡(2,D/e z2,0) r9,i≡(2,zi/zi+1,0)for i=2, . . . , m+ dlog me + 5 r10,ij ≡(2,ddlog me+1Aij/Pij,0)for 1 ≤i<j≤n r11,ij ≡(2,Pij/RijPij,0)for 1 ≤i<j≤n r12,ij ≡(2,Pij/BijGij,0)for 1 ≤i<j≤n 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,e zm+dlog me+6/T,0) r21 ≡(2,T/λ,1) r22 ≡(1,b T/S,0) r23 ≡(1,Syes/λ,0) r24 ≡(1,b a2n+m+dlog me+11/N,0) r25 ≡(1,Nno/λ,0) •E(hn,mi)=Γ(hn,mi)− {yes,no} •iin =2 is the input cell. •i0=0 is 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 family5 5 5constructed 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)= hn,mi. The encoding of the instance will be the multiset cod(u)= {{Aij : {Ai,Aj} ∈ E∧1≤i<j≤n}}. Next we informally describe 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 output stage, and ci, which will be multiplied until step 2n, where 4ncopies of c2n+1are obtained. •On the other hand, in the cell labelled by 2, the division rules are applied. For each object Ai(which encodes the i-th vertex of the graph) we get (in two steps) three cells labelled by 2, each of them encoding one of the three colors (red, green or blue) for this node by means of the objects Ri,Gi,Bi. 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. At this moment, the content of the cell labelled by 1 is {{a2n+1,c4n 2n+1,b,yes,no}}, and there are 3ncells labelled by 2, each of them containing the object D, the objects Aij, and encoding a different coloring function from Vto {R,G,B}. In the step 2n+1, 3ncopies of c2n+1in the cell 1 are traded against 3nobjects D, one from each cell labelled by 2. Notice that 4n−3nspare copies of the counter cwill remain in cell 1. When the object c2n+1arrives to a cell labelled by 2, the communication process starts in that cell. At the beginning of the process, we pay attention to the counters dand z. 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+ dlog me + 2)-th step (for the sake of simplicity, we shall denote γ=2n+ dlog me + 2). The object zwill be used to send an object Tto the cell 1 at the end of this stage. When the mcopies of the object dare obtained, each of them is sent together with an object Aij to the environment, and the corresponding objects Pij are brought in. Then they are interchanged by Rij,Gij,Bij from the environment (this is done in two steps by applying rules r11,ij and r12,ij). In order to know if a 3-coloring is valid we must check for each cell labelled by 2 (encoding a 3-coloring of the graph) if there exist two adjacent vertices with the same color. Let us reason with a color, say red (for green and blue, the process is the same): •If node ihas red color by a 3-coloring encoded in a cell labelled by 2, then the object Riis present in that cell. Then in the step γ+3 the objects Riand Rij produce RiRj(the object Rjis brought from the environment). Simultaneously, in that step the objects Pij produce objects Bij and Gij applying the rules r12,ij. •If the vertex jis also of color red, then the objects RjRjare traded against an object [from the environment. This object will be sent out in the next step, together with object e. •In this way, as soon as the cell finds two adjacent vertices with the same color, it “rejects” its associated coloring by sending out the object e. Conversely, if there is a cell whose coloring is valid, then at the end of the checking stage the object ewill still be present in that cell. Notice that in the generation stage, the processes are carried out in parallel, but in the checking stage, the red color starts to be checked one step before the other two colors. Taking into account that in the worst case there exists a node adjacent with mnodes (mis the number of edges), then after γ+m+3 steps no more rules of the types r13,ij,r14,ij, and r15,ij can be applied for any 1 ≤i<j≤n. The checking stage will finish at the step γ+m+5, when we can ensure that no more rules of the types r16,j,r17,j, and r18,jcan be applied. The output stage starts in the (γ+m+6)-th step. •Affirmative answer: If there exists a valid 3-coloring of the graph, then in some cell labelled by 2 from the configuration Cγ+m+5we have the object eand the object zdlog me+m+6. By applying the rule r20 we produce an object Tin that cell. In the next step, an object Tarrives to the cell 1 by the application of the rule r21. Then, the objects band Tin cell 1 permit that an object Sarrives to cell 1 from the environment (by applying the rule r22). Finally, an object yes is sent out to the environment by the application of the rule r23 in the step γ+m+9=2n+ dlog me + m+11. The obtained configuration is a halting one. •Negative answer: If there is no valid 3-coloring of the graph, then the object edoes not appear in any cell labelled by 2 from the configuration Cγ+m+5, and actually no rule can be applied anymore in these cells. In the next three steps, only the rules for counter ain cell 1 are applied, and hence, at configuration Cγ+m+8we have the objects band a2n+dlog me+m+11 in cell 1. Next, by applying the rule r24 we get from the environment an object N, and in the following step an object no is sent out to the environment (recall that object no is present since the beginning of the computation in cell 1). The computation finishes in the step γ+m+10 =2n+ dlog me + m+12. 5.2. Verification Next, we prove that the family built above solves the 3-COL problem in a linear time, according to Definition 1. First of all, the Definition requires that the defined family is consistent, in the sense that all systems of the family must be recognizer tissue P systems with cell division. By construction (type of rules and working alphabet) it is clear that it is a family of tissue P systems with cell division. In order to show that all members in 5 5 5are recognizer systems it suffices to check that all the computations halt (this will be deduced from the polynomial boundness), and that either an object yes or an object no is sent out exactly in the last step of the computation (this will be deduced from the soundness and completeness). 5.2.1. Polynomial uniformity of the family Next, we show that the family 5 5 5= {Π(hn,mi):n,m∈N}defined above is polynomially uniform by Turing machines. To this aim we are going to prove that it is possible to build Π(hn,mi)in polynomial time with respect to the size of u. It is easy to check that the rules of a system Π(hn,mi)of the family are defined recursively from the values nand m. Besides, the necessary resources to build an element of the family are of a polynomial order, as shown below: •Size of the alphabet: 3n2+9n+2m+3dlog me + 28 ∈θ(n2+m). •Initial number of cells: 2 ∈θ(1). •Initial number of objects: n+m+6∈θ(n+m). •Number of rules: 18n2−9n+2m+3dlog me + 24 ∈θ(n2+m). •Maximal length of a rule: 4. Therefore, a deterministic Turing machine can build Π(hn,mi)in a polynomial time with respect to nand m. Besides, recall that m≤n2, since mis the number of edges in a graph of nvertices. It is also interesting to bear in mind that every instance u=(V,E)is introduced in the initial configuration of its associated cellular system via an input multiset (i.e. an 1-ary representation) and hence, |u| ∈ O(n+m)holds. We would like also to recall that the functions cod and shave been defined above for an instance u=(V,E)of the problem 3-COL as follows: cod(u)= {{Aij : {Ai,Aj} ∈ E∧1≤i<j≤n}}, and s(u)= hn,mi, respectively. Both functions are computable in polynomial time and the pair (cod,s)is a polynomial encoding of I3-COL in Π, since for each instance uof the problem 3-COL we have that cod(u)is an input multiset of the system Π(s(u)). Next, following the indications of Definition 1, we shall prove that the family is polynomially bounded, and also that it is sound and complete with respect to (3-COL,cod,s). 5.2.2. Polynomial boundness of the family In order to ensure that the system Π(s(u)) with input cod(u)is polynomially (indeed, linearly) bounded, it suffices to find the moment in which the computation halts, or at least, an upper bound for it. As we shall show, the number of steps of the computations of any system of the family can always be bounded by a linear function. Nonetheless, we would like to stress that the amount of pre-computed resources for each instance uis polynomial in the size of the instance, since cod(u)needs to be computed and Π(s(u)) needs to be built. Proposition 2. The family 5 5 5= {Π(hn,mi):n,m∈N}is polynomially bounded with respect to (3-COL,cod,s). Proof (Sketch). We will informally go through the stages of the computation in order to estimate a bound for the number of steps. The computation will be studied more in detail when addressing the soundness and completeness proof. Let u=(V,E)be an instance of the problem 3-COL. We shall study what happens during the computation of the system Π(s(u)) with input cod(u)which processes such instance in order to find the halting step, or at least, an upper bound for it. First, the generation stage has exactly 2nsteps, where all the divisions of the cells of the system are performed. The order in which the divisions are performed is nondeterministically chosen in each computation, but in all cases the divisions are carried out in the 2nfirst steps. The pre-checking stage starts with the rule r5. After three more steps, objects z2arrive to all cells 2, and the counter z starts working until it reaches its last (greatest) index, at the (2n+ dlog me + m+5)-th step, and the checking stage ends. The last one is the answer stage. The longest case is obtained when the answer is negative. In this case there is one step where only the counter ais working since no element Thas reached the cell 1. In the next step an object Nis brought from the environment and, at last, in the (2n+ dlog me + m+11)-th step, the object no is sent to the environment. Therefore, there exists a linear bound (with respect to nand m) on the number of steps of the computation.  5.2.3. Soundness and completeness of the family In order to prove the soundness and completeness of the family 5 5 5with respect to (3-COL,cod,s), we shall prove that given an instance uof the problem 3-COL, the system Π(s(u)) with input cod(u)sends out an object yes if and only if the answer to the problem for the considered instance uis affirmative and the object no is sent out otherwise. In both cases the answer will be sent to the environment in the last step of the computation. Proposition 3. The family 5 5 5= {Π(hn,mi):n,m∈N}is sound and complete with respect to (3-COL,cod,s). Proof. In order to complete the proof we shall proceed through a number of auxiliary results.  Remark 4. For the sake of simplicity in the notation, we shall consider a function ψdefined as follows: (f,i)=   Riif f(vi)=R Giif f(vi)=G Biif f(vi)=B for each 3-coloring f: {v1, . . . , vn} → {R,G,B}, and for i=1, . . . , n. Given a computation Cwe denote the configuration at the i-th step as Ci. Moreover, Ci(1)will denote the multiset associated to cell 1 in such configuration. We start with the generation stage (i.e. the first 2nsteps of the computation). It has two parallel processes, each of them in one cell. Lemma 5. Let Cbe an arbitrary computation of the system, then for all ksuch that 0≤k≤n,C2k(1)= {{a2k+1,c4k 2k+1,b,yes,no}} holds. Proof. We shall reason by induction on k. Base Case. We have C0(1)= {{a,c1,b,yes,no}}, and thus the lemma holds for k=0. Case k<n→k+1.Let kbe such that 1 ≤k<nand we have, by inductive hypothesis, C2k(1)= {{a2k+1,c4k 2k+1,b,yes,no}}. In this configuration, only the rules r3,k+1and r4,k+1can be applied to cell 1, and therefore C2k+1(1)= {{a2k+2,c2·4k 2k+2,b,yes,no}}. In the following step, we can only apply to cell 1 the rules r3,k+2and r4,k+2, and we thus obtain C2k+2(1)= {{a2k+3,c2·2·4k 2k+3,b,yes,no}} = {{a2k+3,c4k+1 2k+3,b,yes,no}}. Proposition 6. Let Cbe an arbitrary computation of the system, then: (1) For each coloring f: {v1, . . . , vn}→{R,B,G}there exists only one cell 2in C2nwhose multiset is {{Aij : {vi,vj} ∈ E}} ∪ {{D,ψ(f,1), . . . , ψ(f,n)}} (2) There exist exactly 3ncells labelled by 2in configuration C2n. Proof (Sketch). Let fbe a coloring f: {v1, . . . , vn} → {R,B,G}, and let us denote by Rf1and Rf2the following sets of rules Rf1= {r1,i:f(vi)=R,1≤i≤n} Rf2= {r1,i,r2,i:f(vi)=B∨f(vi)=G,1≤i≤n}. Rf=Rf1∪Rf2is the set of rules needed to produce a cell 2 containing the objects ψ(f,1), . . . , ψ(f,n)that encode the coloring f. More precisely, for each 1 ≤i≤n, if f(vi)=Rthen after applying r1,i∈Rf1we take the cell where Rioccurs, and if f(vi)6= R, then after applying r1,i∈Rf2we take the cell where Tioccurs, and after applying r2,i∈Rf2we take the cell where ψ(f,i) occurs. One can see that |Rf| = q+2(n−q)where q= |Rf1|, and it is clear that rules in Rfcannot be applied in parallel over the same cell, as all of them are division rules. Thus, it takes 2n−qsteps to carry them out sequentially (note that 1 ≤q≤n). Due to the intrinsic non-determinism of the system, a detailed proof falls out of the scope of this paper. Informally, the idea is that rules from Rfmay be applied in different orders within different computations, but it can be shown that in every computation after 2nsteps no more division rules are applied in any cell 2. The design of the rules ensures that each one of the 3npossible colorings will be represented by some cell in the system.  Lemma 7. Let Cbe an arbitrary computation of the system, then for all isuch that 1≤i≤ dlog me + m+8, C2n+i(1)= {{a2n+i+1,c4n−3n 2n+1,D3n,b,yes,no}} holds. Proof. In order to prove the lemma it suffices to observe the following: •C2n(1)= {{a2n+1,c4n 2n+1,b,yes,no}} holds from Lemma 5. •There exist exactly 3ncells labelled by 2 in configuration C2n, each of them containing an object D(follows from previous result). •In the next step of the computation, only rules r5and r3,2n+1are applicable on cell 1, yielding C2n+1(1)= {{a2n+1+1,c4n−3n 2n+1,D3n,b,yes,no}} •During the rest of the checking stage, only rules of type r3,iare applicable on cell 1, and the result follows.  Proposition 8. Let Cbe an arbitrary computation of the system. Then: •For each coloring f: {v1, . . . , vn} → {R,B,G}there exists only one cell 2in C2n+1whose associated multiset is {{Aij : {vi,vj} ∈ E}} ∪ {{c2n+1,ψ(f,1), . . . , ψ(f,n)}}. •There exist exactly 3ncells labelled by 2in configuration C2n+1 Proof. C2n+1is obtained from C2nby the application of the rules r5and r3,n+1and hence, 3nobjects c2n+1in the cell 1 are traded against 3nobjects Dfrom the cells 2 (one from each cell). Then C2n+1(1)= {{a2n+2,c4n−3n 2n+1,D3n,b,yes,no}} and for every f: {v1, . . . , vn}→{R,B,G}there exists only one cell 2 whose associated multiset is {{Aij : {vi,vj} ∈ E}} ∪ {{c2n+1,ψ(f,1), . . . , ψ(f,n)}}. Since no division rule has been applied in this step (actually, they will not be applied anymore along the computation), the number of cells 2 remains the same as in the previous configuration.  Proposition 9. Let Cbe an arbitrary computation of the system. Then: •For each f: {v1, . . . , vn} → {R,B,G}there exists only one cell 2 in C2n+2whose associated multiset is {{Aij : {vi,vj} ∈ E}} ∪ {{d1,D,ψ(f,1), . . . , ψ(f,n)}}. •There exist exactly 3ncells labelled by 2in configuration C2n+2. Proof. It follows from the previous result, taking into account that C2n+2is obtained from C2n+1by applying rules r6and r3,2n+2. Therefore, in cell 1 only the object a2n+2is replaced by a2n+3, and each cell 2 trades an object c2n+1against the objects d1,Dfrom the environment.  Proposition 10. Let Cbe an arbitrary computation of the system. For each i(1≤i≤ dlog me)and for each f: {v1, . . . , vn} → {R,B,G}there exists only one cell 2in C2n+2+iwhose associated multiset is {{Aij : {vi,vj} ∈ E}} ∪ {{d2i i+1,e,zi+1,ψ(f,1), . . . , ψ(f,n)}}. Proof. We shall reason by induction on i. Case i=1. The result follows from the previous Proposition, as C2n+2+1is obtained from C2n+2by applying the rules r3,2n+3, r7,1and r8. Case 1≤i<dlog me → i+1. Let ibe such that 1 ≤i<dlog meand let us suppose that the result holds for i. The configuration C2n+2+i+1is obtained from the configuration C2n+2+ivia the application of the rules r3,2n+2+i,r7,i+1and r9,i. By applying the rule r3,2n+2+ito C2n+2+i, the object a2n+3+i(used as a counter in the cell 1) evolves by adding 1 to the subscript. The application of the rule r7,i+1in all cells 2 replaces each object di+1by d2 i+2. Finally, the rule r9,iis applied in each cell 2 over the object zi+1(used as a counter). Therefore, C2n+3+i(1)= {{a2n+3+i,c4n−3n 2n+1,D3n,b,yes,no}}. Bearing in mind that, by inductive hypothesis, for each f: {v1, . . . , vn} → {R,B,G}there exists only one cell 2 in C2n+2+iwith the multiset {{Aij : {vi,vj} ∈ E}} ∪ {{d2i i+1,e,zi+1,ψ(f,1), . . . , ψ(f,n)}}, then the multiset of such cell 2 in C2n+3+iwill be {{Aij : {vi,vj} ∈ E}} ∪ {{d2i+1 i+2,e,zi+2,ψ(f,1), . . . , ψ(f,n)}}. Proposition 11. Let Cbe an arbitrary computation of the system. For each f: {v1, . . . , vn} → {R,B,G}there exist some unique cells 2in the configurations C2n+dlog me+3and C2n+dlog me+4with the following corresponding multisets: {{Pij : {vi,vj} ∈ E}} ∪ {{e,zdlog me+2,ψ(f,1), . . . , ψ(f,n)}} {{Rij,Pij : {vi,vj} ∈ E}} ∪ {{e,zdlog me+3,ψ(f,1), . . . , ψ(f,n)}}. Proof. The configuration C2n+dlog me+3is obtained from C2n+dlog me+2by applying the rules r3,2n+dlog me+3,r9,dlog me+1,{r10,ij : {vi,vj} ∈ E}. •r3,2n+dlog me+3allows the evolution of the counter a2n+dlog me+3in the cell 1. •r9,dlog me+1allows the evolution of the counter zdlog me+2in each cell 2. • {r10,ij : {vi,vj} ∈ E}allow the replacement of the objects Aij (encoding the edges) by Pij. By an analogous reasoning, we can check that C2n+dlog me+4is obtained from the configuration C2n+dlog me+3by application of the rules r3,2n+dlog me+4,r9,dlog me+2and {r11,ij : {vi,vj} ∈ E}. Proposition 12. Let Cbe an arbitrary computation of the system. Then for each f: {v1, . . . , vn} → {R,B,G}there exist only one cell 2in C2n+dlog me+5whose associated multiset is {{Ri,Rj,Gij,Bij : {vi,vj} ∈ E∧f(vi)=R}} ∪ {{Rij,Gij,Bij : {vi,vj} ∈ E∧f(vi)6= R}} ∪ {{ψ(f,j):1≤j≤n∧f(vj)6= R}} ∪ {{e,zdlog me+4}}. Proof. The configuration C2n+dlog me+5is obtained from C2n+dlog me+4by applying the rules listed below: •r3,2n+dlog me+5allows the evolution of the counter a2n+dlog me+5in the cell 1. •r9,dlog me+3allows the evolution of the counter zdlog me+3in each cell 2. • {r12,ij : {vi,vj} ∈ E}allow the replacement of the objects {Pij : {vi,vj} ∈ E}by {Bij,Gij : {vi,vj} ∈ E}. • {r13,ij : {vi,vj} ∈ E∧f(i)=R}produce, in each cell 2, pairs of objects Ri,Rjfor each {vi,vj} ∈ Esuch that f(i)=R. Objects Rij corresponding to edges {vi,vj} ∈ Esuch that f(i)6= Rwill remain unchanged.  Proposition 13. Let Cbe an arbitrary computation of the system. Then •There exist exactly 3ncells labelled by 2in configuration C2n+dlog me+m+6. •If f: {v1, . . . , vn}→{R,B,G}is not a valid coloring, then there exists only one cell 2in C2n+m+dlog me+6associated with f, and whose associated multiset is {{zm+dlog me+5}} ∪ {{[t−1}} together with an irrelevant multiset of objects, where tis the number of adjacent pairs of nodes with the same color in f.