×

A uniform family of tissue P systems with cell division solving 3-COL in a linear time. (English) Zbl 1151.68016

Summary: Several examples of the efficiency of cell-like P systems regarding the solution of NP-complete 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.

MSC:

68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
68Q25 Analysis of algorithms and problem complexity
05C15 Coloring of graphs and hypergraphs
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alberts, B.; Johnson, A.; Lewis, J.; Raff, M.; Roberts, K.; Walter, P., The Molecular Biology of the Cell (2002), Garland Publ. Inc.: Garland Publ. Inc. London
[2] Alhazov, A.; Freund, R.; Oswald, M., (Tissue P Systems with Antiport Rules ans Small Numbers of Symbols and Cells. Tissue P Systems with Antiport Rules ans Small Numbers of Symbols and Cells, Lecture Notes in Computer Science, vol. 3572 (2005)), 100-111 · Zbl 1132.68386
[3] Appel, K.; Haken, W., Every planar map is 4-colorable - 1: Discharging, Illinois Journal of Mathematics, 21, 429-490 (1977) · Zbl 0387.05009
[4] Appel, K.; Haken, W., Every planar map is 4-colorable - 2: Reducibility, Illinois Journal of Mathematics, 21, 491-567 (1977) · Zbl 0387.05010
[5] Bernardini, F.; Gheorghe, M., Cell communication in tissue P systems and cell division in population P systems, Soft Computing, 9, 9, 640-649 (2005) · Zbl 1101.68574
[6] Cardelli, L., (Brane Calculi. Brane Calculi, Lecture Notes in Computer Science, vol. 3082 (2005)), 257-278
[7] Freund, R.; Păun, Gh.; Pérez-Jiménez, M. J., Tissue P systems with channel states, Theoretical Computer Science, 330, 101-116 (2005) · Zbl 1078.68061
[8] Garey, M. R.; Johnson, D. S., Computers and Intractability A Guide to the Theory of NP-Completeness (1979), W.H. Freeman and Company · Zbl 0411.68039
[9] Gutiérrez-Naranjo, M. A.; Pérez-Jiménez, M. J.; Romero-Campero, F. J., (A Linear Solution for QSAT with Membrane Creation. A Linear Solution for QSAT with Membrane Creation, Lecture Notes in Computer Science, vol. 3850 (2006)), 241-252 · Zbl 1135.68411
[10] Ionescu, M.; Păun, Gh.; Yokomori, T., Spiking neural P systems, Fundamenta Informaticae, 71, 2-3, 279-308 (2006) · Zbl 1110.68043
[11] Krishna, S. N.; Lakshmanan, K.; Rama, R., (Tissue P Systems with Contextual and Rewriting Rules. Tissue P Systems with Contextual and Rewriting Rules, Lecture Notes in Computer Science, vol. 2597 (2003)), 339-351 · Zbl 1023.68049
[12] K. Lakshmanan, R. Rama, On the power of tissue P systems with insertion and deletion rules, in: A. Alhazov, C. Martín-Vide and Gh. Păun (Eds.), Preproceedings of the Workshop on Membrane Computing, Tarragona, Report RGML 28/03, 2003, pp. 304-318; K. Lakshmanan, R. Rama, On the power of tissue P systems with insertion and deletion rules, in: A. Alhazov, C. Martín-Vide and Gh. Păun (Eds.), Preproceedings of the Workshop on Membrane Computing, Tarragona, Report RGML 28/03, 2003, pp. 304-318
[13] Luisi, P. L., (Fleishaker, G. R.; etal., The Chemical Implementation of Autopoiesis. The Chemical Implementation of Autopoiesis, Self-Production of Supramolecular Structures (1994), Kluwer: Kluwer Dordrecht)
[14] (Maass, W.; Bishop, C., Pulsed Neural Networks (1999), MIT Press: MIT Press Cambridge) · Zbl 0935.68087
[15] Martín Vide, C.; Pazos, J.; Păun, Gh.; Rodríguez Patón, A., (A New Class of Symbolic Abstract Neural Nets: Tissue P Systems. A New Class of Symbolic Abstract Neural Nets: Tissue P Systems, Lecture Notes in Computer Science, vol. 2387 (2002)), 290-299 · Zbl 1077.68645
[16] Martín Vide, C.; Pazos, J.; Păun, Gh.; Rodríguez Patón, A., Tissue P systems, Theoretical Computer Science, 296, 295-326 (2003) · Zbl 1045.68063
[17] Păun, Gh., Computing with membranes, Journal of Computer and System Sciences, 61, 1, 108-143 (2000) · Zbl 0956.68055
[18] Păun, Gh., Membrane Computing. An Introduction (2002), Springer-Verlag: Springer-Verlag Berlin · Zbl 1034.68037
[19] Păun, A.; Păun, Gh., The power of communication: P systems with symport/antiport, New Generation Computing, 20, 3, 295-305 (2002) · Zbl 1024.68037
[20] Păun, Gh.; Pérez-Jiménez, M. J., Recent computing models inspired from biology: DNA and membrane computing, Theoria, 18, 46, 72-84 (2003) · Zbl 1041.68041
[21] Gh. Păun, M.J. Pérez-Jiménez, A. Riscos-Núñez, Tissue P system with cell division, in: Gh. Păun, A. Riscos-Núñez, A. Romero-Jiménez and F. Sancho-Caparrini (Eds.), Second Brainstorming Week on Membrane Computing, Sevilla, Report RGNC 01/2004, 2004, pp. 380-386; Gh. Păun, M.J. Pérez-Jiménez, A. Riscos-Núñez, Tissue P system with cell division, in: Gh. Păun, A. Riscos-Núñez, A. Romero-Jiménez and F. Sancho-Caparrini (Eds.), Second Brainstorming Week on Membrane Computing, Sevilla, Report RGNC 01/2004, 2004, pp. 380-386
[22] Păun, Gh.; Sakakibara, Y.; Yokomori, T., P systems on graphs of restricted forms, Publicationes Mathematicae Debrecen, 60, 635-660 (2002) · Zbl 1006.68048
[23] M.J. Pérez-Jiménez, A. Romero-Jiménez, F. Sancho-Caparrini, Teoría de la Complejidad en Modelos de Computación Celular con Membranas. Editorial Kronos, Sevilla, 2002; M.J. Pérez-Jiménez, A. Romero-Jiménez, F. Sancho-Caparrini, Teoría de la Complejidad en Modelos de Computación Celular con Membranas. Editorial Kronos, Sevilla, 2002
[24] Pérez-Jiménez, M. J.; Romero-Jiménez, A.; Sancho-Caparrini, F., The P versus NP problem through cellular computing with membranes, (Lecture Notes in Computer Science, vol. 2950 (2004)), 338-352 · Zbl 1200.68117
[25] M.J. Pérez-Jiménez, A. Romero-Jiménez, F. Sancho-Caparrini, A polynomial complexity class in P systems using membrane division, in: E. Csuhaj-Varjú, C. Kintala, D. Wotschke and Gy. Vaszyl (Eds.), Proceedings of the 5th Workshop on Descriptional Complexity of Formal Systems, DCFS 2003, 2003, pp. 284-294; M.J. Pérez-Jiménez, A. Romero-Jiménez, F. Sancho-Caparrini, A polynomial complexity class in P systems using membrane division, in: E. Csuhaj-Varjú, C. Kintala, D. Wotschke and Gy. Vaszyl (Eds.), Proceedings of the 5th Workshop on Descriptional Complexity of Formal Systems, DCFS 2003, 2003, pp. 284-294 · Zbl 1145.68426
[26] V.J. Prakash, On the power of tissue P systems working in the maximal-one mode, in: A. Alhazov, C. Martín-Vide and Gh. Păun (Eds.), Preproceedings of the Workshop on Membrane Computing, Tarragona, Report RGML 28/03, 2003, pp. 356-364; V.J. Prakash, On the power of tissue P systems working in the maximal-one mode, in: A. Alhazov, C. Martín-Vide and Gh. Păun (Eds.), Preproceedings of the Workshop on Membrane Computing, Tarragona, Report RGML 28/03, 2003, pp. 356-364
[27] Stockmeyer, L. J., Planar 3-colorability is NP-complete, SIGACT News, 5, 3, 19-25 (1973)
[28] Zandron, C.; Ferretti, C.; Mauri, G., Solving NP-complete problems using P systems with active membranes, (Antoniou, I.; Calude, C. S.; Dinneen, M. J., Unconventional Models of Computation. Unconventional Models of Computation, UMC’2K (2000), Springer-Verlag), 289-301 · Zbl 0967.68074
[29] ISI web page. http://esi-topics.com/erf/october2003.html; ISI web page. http://esi-topics.com/erf/october2003.html
[30] P systems web page. http://psystems.disco.unimib.it/; P systems web page. http://psystems.disco.unimib.it/
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.