Solving the 3-COL Problem by Using Tissue P Systems without Environment and Proteins on Cells

Solving the 3-COL Problem by Using Tissue P Systems without Environment and Proteins on Cells Daniel D´ıaz-Pernil1, Hepzibah A. Christinal2, Miguel A. Guti´errez-Naranjo3 1Research Group on Computational Topology and Applied Mathematics Department of Applied Mathematics - University of Sevilla, 41012, Spain [email protected] 2Karunya University, Coimbatore, Tamilnadu, India [email protected] 3Research Group on Natural Computing Department of Computer Science and Artificial Intelligence University of Sevilla, 41012, Spain [email protected] Summary. The 3-COL problem consists on deciding if the regions of a map can be coloured with only three colors bearing in mind that two adjacent regions must be coloured with different colors. It is a NP problem and it has been previously used in complexity studies in membrane computing to check the ability of a model for solving problems of such complexity class. Recently, tissue P systems with proteins on cells have been presented and its ability to solve NP-problems has been proved, but it remained as an open question to know if such model was still able to solve such problems if the environment was removed. In this paper we provide an affirmative answer to this question by showing a uniform family of tissue P systems without environment and with proteins on cells which solves the 3-COL problem in linear time. 1 Introduction The Pversus NP problem is one of the most important unsolved problem in computer science and it was chosen as one of the seven Millennium Prize Problems [9]. The precise statement of the problem was introduced in 1971 by Stephen Cook [5], although it was essentially mentioned in a personal communication between K. G¨odel and J. von Neumann [8]. Whereas the main question is unsolved (i.e., to decide if Pand NP are or not the same complexity class), many efforts have been oriented in the last years in order to find frontiers of tractability, i.e., to identify some features of the com- 164 D´ıaz-Pernil, Chistinal, Guti´errez-Naranjo putational models such that the corresponding device is able to solve or not NP problems depending if it is endowed or not with such feature. In membrane computing there is an extensive literature devoted to this issue (see [21] and the references therein) and the present paper is a novel contribution in such research line. We consider here a variant of one of the most popular P systems architectures: tissue P systems. Such model was firstly presented in [13, 14] by placing the cells in a general graph instead on a tree-like graph as in the cell-like model. Under the hypothesis P6=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. Under this premise, Gh. P˘aun et al. presented in [24] the model of tissue P systems with cell division, able to solve NP-problems. Since then, many other variants have been presented, e.g., [6, 10, 11, 16, 17]. Recently, tissue P systems with protein on cells have been introduced [25]. Previously, tissue P systems with proteins on membranes had been presented [22] and many of their properties have been explored (see, e.g., [23, 26, 27]). Nonetheless, the model of tissue P systems with protein on cells is quite different to the model with proteins on membranes: In the first one, proteins can move with multisets of objects but they cannot change. In the model with proteins on membranes, they can be changed, but they cannot move between membranes. Tissue P system with proteins on cells is endowed with cell division and its ability for solving NP problems has been proved [15, 22], but it is an open question to know if after dropping some of the features, the model is still able to solve NP problems. In this paper, we prove that the model of tissue P system with proteins on cells can solve NP problems if the environment is removed. The environment in tissue P systems has a singular characteristic which makes it different to any other region: based on a biological inspiration, cells can take from the environment the necessary resources for any computation in a similar way that a cell can take as many oxygen molecules from the atmosphere as it needs. This means that the number of objects in the environment is not important and the designer does not need to take care of it. Avoiding the environment is a strong restriction, since all the resources are inside the cells and nothing is taken from outside. The importance of the environment in other membrane computing models has been previously discussed in the literature (see, e.g. [4, 12, 19, 20]). In this paper we provide a uniform family of P systems with proteins on cells without environment which solves the 3-COL problem in linear time and hence, we prove that such systems are able of solving NP problems even the environment is dropped. The paper is organized as follows: Next we give a formal description of the P system model used in this paper and recall some basics on recognizer P systems. In Section 3 we present the uniform family of P systems which solve the 3-COL problem in linear time and discuss the amount of resources needed. Finally, the paper ends with some conclusions. Solving the 3-COL Problem . . . 165 2 Formal Framework Tissue P systems with proteins on cells and cell division were introduced in [25]. In the same paper, the definition of recognizer tissue P systems [24] is presented in this framework. We adapt these definitions to the case where the environment is not considered. Definition 1. A tissue P system without environment, with protein on cells and cell division of degree q≥1is a tuple of the form Π= (Γ, P, M1/p1, . . . , Mq/pq,R, iin, iout), where: •Γ, P are finite non–empty alphabets such that Γ∩P=∅;Γis the working alphabet and Pis the set of proteins; • Miare finite multisets over Γ,1≤i≤q; •piare elements from P,1≤i≤q; • R is a finite set of rules of the following types: – Communication rules: (i, (pk, u)/(pl, v), j), for i, j ∈ {1, . . . , q},i6=j, pk,pl∈P,u, v ∈Γ∗. The length of a communication rule is the total number of objects and proteins involved in that rule. – Division rules: [pj|a]i→[pk|b]i[pl|c]ifor i∈ {1, . . . , q},pj, pk, pl∈P, a, b, c ∈Γ,i6=iout •iin, iout ∈ {1, . . . , q}. A tissue P system without environment, with protein on cells and cell division can be viewed as a set of qcells, labelled by {1, . . . , q}such that M1, . . . , Mqrepresent the finite multisets of objects initially placed in the qcells of the system and p1, . . . , pqrepresent one and only one copy of protein initially placed on the qcells of the system; iin is the cell where the input is placed in the initial configuration; and iout represents a distinguished cell which will encode the output of the system. A configuration of the P system at any instant is described by all multisets of objects over Γassociated with all the cells present in the system and the proteins presented on all cells. The initial configuration is (M1/p1, . . . , Mq/pq). A communication rule of type (i, (pk, u)/(pl, v), j) is applicable to a configuration at an instant if cell icontains the protein pkand the multiset uof objects, cell j contains the protein pland the multiset vof objects (multisets u,vmay be empty; the empty multiset will be denoted by the symbol λ). When applying such a rule, under the control of the proteins pkon cell iand plon cell j, both the protein pk and the multiset uof objects are sent from cell ito cell j, and simultaneously, the protein pland the multiset vof objects are sent from cell jto cell i. A division rule [pj|a]i→[pk|b]i[pl|c]iis applicable to a configuration at an instant if cell i contains the protein pjand the object a. When applying such a rule, under the influence of protein pjand the object ain cell i, the cell is divided into two cells with the same label; in the first copy of the cell the protein pjis replaced by pk 166 D´ıaz-Pernil, Chistinal, Guti´errez-Naranjo and the object ais replaced by b, in the second copy of the cell the protein pjis replaced by pland the object ais replaced by c; all the remaining objects in the original cell are replicated and distributed in each of the new cells. Rules are used in a maximally parallel way: at each step, all cells which can evolve must evolve and a maximal multiset of rules is applied (no further rule can be added being applicable). As usual in the variant of tissue P systems, this way of applying rules has only one restriction: when a cell is divided, the division rule is the only one which is applied to that cell at that step. The new cells resulting from division could participate in the interaction with other cells by means of communication rules at the next step (if they are not divided once again). 2.1 Recognizer Tissue P Systems with Protein on Cells and Cell Division We recall the main notions related to the theory of recognizer P systems, which can be adapted to this model in a natural way. For a detailed description see, e.g., [18, 21]. A decision problem Xis a pair (IX, θX) such that IXis a language over a finite alphabet (whose elements are called instances) and θXis a total Boolean function over IX. In general, in a P system with input and output of any P system variant we consider a working alphabet Γ, with qmembranes labelled by 1, . . . , q, and initial multisets M1,...,Mqassociated with them; Σ, which is an (input) alphabet strictly contained in Γ; the initial multisets are over Γ−Σ; and iin,iout are the labels of two distinguished membranes (input and output). Let Γbe the working alphabet of Π,µits membrane structure, and M1,...,Mpthe initial multisets of Π. Let mbe a multiset over Σ. The initial configuration of the P system is (µ, M1,...,Miin ∪m, . . . , Mq). Arecognizer P system is a P system with input and output such that: •The working alphabet contains two distinguished elements yes,no. •All its 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 output region (denoted with label iout), and only in the last step of the computation. We say that Cis an accepting computation (respectively, rejecting computation) if the object yes (respectively, no) appears in the output region associated to the corresponding halting configuration of C. A decision problem Xcan be solved in a polynomially uniform way by a family Π={Π(n)}n∈Nof P systems of type Fif the following holds: •There is a deterministic Turing machine Msuch that, for every n∈N, starting Mwith the unary representation of non its input tape, it constructs the P system Π(n) in polynomial time in n. •There is a deterministic Turing machine Nthat started with an instance I∈IX with size non its input tape, it computes a multiset wI(called the encoding of I) over the input alphabet of Π(n) in polynomial time in n. Solving the 3-COL Problem . . . 167 •For every instance I∈IXwith size n, starting Π(n) with wIin its input membrane, every computation of Π(n) halts and sends out to the environment yes if and only if Iis a positive instance of X. According to the standard notation, \ TPDC(k) denotes the class of recognizer tissue P systems without environment with protein on cells and communication rules of length at most kand PMC \ T P DC(k)the set of all decision problems which can be solved by means of such class. This class is closed under polynomial time reduction and under complement. 3 The 3-COL Problem Ak–coloring (k≥1) of an undirected graph G= (V, E) is a function f:V→ {1, . . . , k}, where {1, . . . , k}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). In particular, when k= 3, we have the well-known 3–coloring problem: 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 will 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 [2, 3]). The NP-completeness of the 3–coloring problem was proved by Stockmeyer [28] (see [7]). Next, we will prove that the 3–coloring problem can be solved in a linear time by a family of recognizer tissue P systems without environment and with proteins on cells. As usual, we will address the resolution via a brute force algorithm, which consists in the following stages: •Generation Stage: All the possible 3–coloring are generated, each of them placed in a different cell. By using the division rules, an exponential amount of cells can be obtained in linear time. In parallel, the cell containing initially a copy of the description of the graph is also divided generating as many copies of the graph as 3-colorings. •Checking Stage: If a generated 3–coloring has two objects Kiand Kj(K∈ {R, G, B}) and the graph has an edge Aij linking the nodes iand j, this coloring is not valid. Since the number of cells containing a copy of the description of the graph is large enough, the checking for all the colorings can be done in parallel by pairing cells encoding 3-colorings with cells encoding copies of the graph. This stage takes only one step. •Output Stage: It suffices that one of the possible coloring satisfies the conditions in order to have a positive answer. If such coloring exists, a distinguished protein will be send to the appropriate cell. We can control via a counter the number of steps for it. If such protein occurs in the right cell at the right moment, the system sends yes to the output cell. If such step is reached and the protein has not been released, an object no is sent to the output cell. 168 D´ıaz-Pernil, Chistinal, Guti´errez-Naranjo Each of the P systems of the uniform family Π={Πn}n∈Ndescribed below depends only on one parameter nwhich represents the number of nodes of the graph. Each of these Πnis supplied with the encoding of a concrete instance of a graph with nvertices in order to start the computation. The graph will be encoded by using an input alphabet Σ={Aij : 1 ≤i < j ≤n}, and an object Aij will belong to the input multiset if and only if there is an edge in the graph linking the nodes iand j. For the sake of simplicity we drop the subscript in Πn. Formally, for each n∈N, the tissue P system is defined as Π= (Γ, P, Σ, M1/p1,M2/p2,M3/p3,M4/p4,M5/p5,R, iin, iout), •Γ=Σ∪ {Ai, Ri, Gi, Bi, Ui, Vi: 1 ≤i≤n} ∪ {ai: 0 ≤i≤2n+ 1} ∪ {bi: 0 ≤i≤2n+ 2} ∪ {T, yes,no} •Σ={Aij : 1 ≤i<j≤n} •P={pi,j :i∈ {1,2}j∈ {1,...,2n+ 1} ∪ {qi,j :i∈ {1,2}j∈ {1,...,2n} ∪ {p0} • M1={A1, . . . , An}with the initial protein p1,1in cell 1; • M2={A1, . . . , An}with the initial protein p2,1in cell 2; • M3={a0}with the initial protein p0in cell 3; • M4={b0,yes,no}with the initial protein p0in cell 4; • M5={a1, . . . , a2n+1, b1, . . . , b2n+2}with the initial protein p0in cell 5; • R is the following set of rules: 1. Division rules: For i∈ {1,2}and j∈ {1, . . . , n} r1,i,j ≡[pi,j|Aj]i→[qi,j |Uj]i[qi,j |Vj]i r2,i,j ≡[qi,j|Uj]i→[pi,j+1|Rj]i[pi,j+1|Gj]i r3,i,j ≡[qi,j|Vj]i→[pi,j+1|Bj]i[pi,j+1|T]i 2. Communication rules: r4,i,j,K ≡(1,(p1,2n+1, Aij)/(p2,2n+1, KiKj),2) for i, j ∈ {1, . . . , n},i<j,K∈ {R, G, B} r5,i ≡(3,(p0, ai)/(p0, ai+1),5) for i={0,...,2n} r6,i ≡(4,(p0, bi)/(p0, bi+1),5) for i={0,...,2n+ 1} r7≡(2,(p2,2n+1, λ)/(p0, a2n+1),3) r8≡(4,(p0, b2n+2 yes)/(p2,2n+1, λ),3) r9≡(4,(p0, b2n+2 no)/(p0, λ),3) •iin = 1, is the input cell •iout = 3, is the output cell 3.1 An Overview of the Computation The system is deterministic and it exploits the parallelism intrinsic to membrane computing systems and the specific feature of tissue P system with proteins on Solving the 3-COL Problem . . . 169 cells which fix one and only one protein in each membrane. From the initial configuration, four processes start: 1. Cell 1 is divided by the application of rules r1,1,j,r1,2,j and r1,3,j . The configuration C2nhas 2nmembranes with label 1, each of them containing a copy of the input and a protein p1,2n+1. 2. Cell 2 is divided by the application of rules r2,1,j ,r2,2,j and r2,3,j in parallel with the cell of label 1. The configuration C2nhas 2nmembranes with label 2 all of them with the protein p2,2n+1. Some of these membrane contain one or more copies of the object T. Each of the remaining 3nmembranes contain a 3-coloring, i.e., a multiset of objects C1C2. . . Cnwith C∈ {R, G, B}. 3. Cell 3 interchanges one object with cell 5 during the 2nfirst steps, so at C2n it contains the protein p0and the object a2n. 4. Analogously, cell 4 interchanges one object with cell 5 during the 2nfirst steps, so at C2nit contains the protein p0and the object b2n. At the configuration C2n, cells 1 contain the protein p1,2n+1 and cells 2 contain the protein p2,2n+1. If a cell 2 contain two objects KiKjwith the same color (K∈ {R, G, B}) and there exists an edge Aij in the input, then the rule r4,i,j,K is applied and the corresponding cells interchange their proteins. Since there are enough cells with label 1, the following holds: •If a cell 2 represent a valid coloring, then the rule r4,i,j,K is not applied and the cell has the protein p2,2n+1 at the configuration C2n+1. •Otherwise, if the coloring represented in the cell is not valid, then the rule r4,i,j,K is applied and the cell has the protein p1,2n+1 at the configuration C2n+1. •Moreover, at C2n+1, cell 3 has protein p0and an object a2n+1 and cell 4 has protein p0and and object b2n+1 Let us recall that if there exists at least one valid coloring, then the answer to the 3-COL problem must be affirmative. Let us consider that there exist such valid coloring and then, at C2n+1 there exists (at least) one cell 2 with protein p2,2n+1. In such case the rule 7 applied and at C2n+2 the cell 3 contains the protein p2,2n+1. Otherwise, if none of the cells 2 has the protein p2,2n+1, then the rule 7 is not applied and cell 3 has the protein p0at C2n+2. In such configuration the object b2n+2 has reached cell 4. Finally, depending on the protein p0or p2,2n+1 in cell 3, rule 8 or rule 9 will be applied sending the right answer to cell 3. No more rules can be applied and C2n+3 is a halting configuration. 3.2 Computational Efficiency The amount of resources used in the construction of the P system Πncan be summarized as follows: The working alphabet Γis O(n) with 10n+ 8 objects; the input alphabet is O(n2) with n2−n 2objects; the set of proteins is O(n) with 6n+3 proteins; and the number of rules is O(n2) with 3 2n2+17 2n+6 rules. All the 170 D´ıaz-Pernil, Chistinal, Guti´errez-Naranjo computation halt after 2n+ 3 steps. Finally, the communication rules have length 5 at most. Therefore the main result of this paper holds. Theorem 1. 3-COL ∈PMC \ T P DC(5) Corollary 1. NP ∪co−NP ⊆PMC \ T P DC(5) These results hold from the previous construction and the closure under polynomial-time reduction and under complement of the complexity class. 4 Conclusions Whereas the Pvs. NP is unsolved, the search of new frontiers of tractability allows us to have a deeper knowledge of the problem. In the framework of membrane computing, and in natural computing in general, the use of bio-inspired features in such complexity studies shed a new light on an old problem. In this paper we present a new solution to the 3-COL problem with tissue P systems with proteins on cells and without environment which uses communication rules of length at most 5. By using environment, the solution for the SAT problem proposed in [25] uses communication rules of length at most 4. In [15] the proposed solution for the 3-COL problem also uses communication rules of length at most 4. Although both problems, SAT and 3-COL, are different, it remains open the question if it is possible to find a solution to a NP problem in the model of tissue P systems with proteins on cells by removing the environment and using communication rules of length at most 4. References 1. Alhazov, A., Cojocaru, S., Gheorghe, M., Rogozhin, Y., Rozenberg, G., Salomaa, A. (eds.): Membrane Computing - 14th International Conference, CMC 2013, Chi¸sin˘au, Republic of Moldova, August 20-23, 2013, Revised Selected Papers, Lecture Notes in Computer Science, vol. 8340. Springer (2014) 2. Appel, K., Haken, W.: Every planar map is 4-colorable - 1: Discharging. Illinois Journal of Mathematics 21, 429–490 (1977) 3. Appel, K., Haken, W.: Every planar map is 4-colorable - 2: Reducibility. Illinois Journal of Mathematics 21, 491–567 (1977) 4. Christinal, H.A., D´ıaz-Pernil, D., Guti´errez-Naranjo, M.A., P´erez-Jim´enez, M.J.: Tissue-like p systems without environment. In: Mart´ınez del Amor, M.A., P˘aun, Gh., P´erez Hurtado, I., Riscos-N´u˜nez, A. (eds.) Eighth Brainstorming Week on Membrane Computing. pp. 53–64. F´enix Editora, Sevilla, Spain (2010) 5. Cook, S.A.: The complexity of theorem-proving procedures. In: Proceedings of the Third Annual ACM Symposium on Theory of Computing. pp. 151–158. STOC ’71, ACM, New York, NY, USA (1971) 6. Freund, R., P˘aun, Gh., P´erez-Jim´enez, M.J.: Tissue P systems with channel states. Theoretical Computer Science 330(1), 101–116 (2005) Solving the 3-COL Problem . . . 171 7. Garey, M.R., Johnson, D.S.: Computers and Intractability, A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, New York (1979) 8. Hartmanis, J.: G¨odel, von Neumann and the P =? NP problem. In: Rozenberg, G., Salomaa, A. (eds.) Current Trends in Theoretical Computer Science - Essays and Tutorials, World Scientific Series in Computer Science, vol. 40, pp. 445–450. World Scientific (1993) 9. Jaffe, A.M.: The millennium grand challenge in mathematics. Notices of the American Mathematical Society 53(6), 652 – 660 (2006) 10. Krishna, S.N., Lakshmanan, K., Rama, R.: Tissue P systems with contextual and rewriting rules. In: P˘aun, Gh., Rozenberg, G., Salomaa, A., Zandron, C. (eds.) WMC- CdeA. Lecture Notes in Computer Science, vol. 2597, pp. 339–351. Springer, Berlin Heidelberg (2002) 11. Lakshmanan, K., Rama, R.: On the power of tissue P systems with insertion and deletion rules. In: Alhazov, A., Mart´ın-Vide, C., P˘aun, Gh. (eds.) Preproceedings of the Workshop on Membrane Computing. pp. 304–318. Tarragona (July 17-22 2003) 12. Mac´ıas-Ramos, L.F., P´erez-Jim´enez, M.J., Riscos-N´u˜nez, A., Rius-Font, M., Valencia-Cabrera, L.: The efficiency of tissue P systems with cell separation relies on the environment. In: Csuhaj-Varj´u, E., Gheorghe, M., Rozenberg, G., Salomaa, A., Vaszil, G. (eds.) Membrane Computing - 13th International Conference, CMC 2012, Budapest, Hungary, August 28-31, 2012, Revised Selected Papers. Lecture Notes in Computer Science, vol. 7762, pp. 243–256. Springer (2012) 13. Mart´ın-Vide, C., Pazos, J., P˘aun, Gh., Rodr´ıguez-Pat´on, A.: A new class of symbolic abstract neural nets: Tissue P systems. In: Ibarra, O.H., Zhang, L. (eds.) COCOON. Lecture Notes in Computer Science, vol. 2387, pp. 290–299. Springer, Berlin Heidelberg (2002) 14. Mart´ın-Vide, C., P˘aun, Gh., Pazos, J., Rodr´ıguez-Pat´on, A.: Tissue P systems. Theoretical Computer Science 296(2), 295–326 (2003) 15. Mathu, T., Christinal, H.A., D´ıaz-Pernil, D.: A uniform family of tissue P systems with protein on cells solving 3-coloring in linear time. In: Calude, C.S., Dinneen, M.J. (eds.) Unconventional Computation and Natural Computation - 14th International Conference, UCNC 2015, Auckland, New Zealand, August 30 - September 3, 2015, Proceedings. Lecture Notes in Computer Science, vol. 9252, pp. 239–249. Springer (2015) 16. Pakash, V.: On the power of tissue P systems working in the maximal-one mode. In: Alhazov, A., Mart´ın-Vide, C., P˘aun, Gh. (eds.) Preproceedings of the Workshop on Membrane Computing. pp. 356–364. Tarragona (July 17-22 2003) 17. Pan, L., P´erez-Jim´enez, M.J.: Computational complexity of tissue-like P systems. Journal of Complexity 26(3), 296–315 (2010) 18. P´erez-Jim´enez, M.J.: An approach to computational complexity in membrane computing. In: Mauri, G., P˘aun, Gh., P´erez-Jim´enez, M.J., Rozenberg, G., Salomaa, A. (eds.) Workshop on Membrane Computing. Lecture Notes in Computer Science, vol. 3365, pp. 85–109. Springer (2004) 19. P´erez-Jim´enez, M.J., Riscos-N´u˜nez, A., Rius-Font, M., Romero-Campero, F.J.: A polynomial alternative to unbounded environment for tissue P systems with cell division. International Journal of Computer Mathematics 90(4), 760–775 (2013) 20. P´erez-Jim´enez, M.J., Riscos-N´u˜nez, A., Rius-Font, M., Valencia-Cabrera, L.: The relevance of the environment on the efficiency of tissue P systems. In: Alhazov et al. [1], pp. 308–321