A uniform solution to the independent set problem through tissue P systems with cell separation

Abstract

Membrane computing is an emergent branch of natural computing, which is inspired by the structure and the functioning of living cells, as well as the organization of cells in tissues, organs, and other higher order structures. Tissue P systems are a class of the most investigated computing models in the framework of membrane computing, especially in the aspect of efficiency. To generate an exponential resource in a polynomial time, cell separation is incorporated into such systems, thus obtaining so called tissue P systems with cell separation. In this work, we exploit the computational efficiency of this model and construct a uniform family of such tissue P systems for solving the independent set problem, a well-known NP-complete problem, by which an efficient solution can be obtained in polynomial time.

Keywords

membrane computing / tissue P system / cell separation / independent set problem

References

[1] Pǎun G. Computing with membranes. Journal of Computer and System Sciences, 2000, 61(1): 108-143

[2] Pan L, Pǎaun G. Spiking neural P systems with antispikes. International Journal of Computers, Communications & Control, 2009, IV(3): 273-282

[3] Pan L, Pǎun G. Spiking neural P systems: an improved normal form. Theoretical Computer Science, 2010, 411(6): 906-918

[4] Wang J, Hoogeboom H J, Pan L, Pǎun G, Pérez-Jiménez M J. Spiking neural P systems with weights. Neural Computation, 2010, 22(10): 2615-2646

[5] Pan L, Martín-Vide C. Solving multidimensional 0-1 knapsack problem by P systems with input and active membranes. Journal of Parallel and Distributed Computing, 2005, 65(12): 1578-1584

[6] Pan L, Martín-Vide C. Further remark on P systems with active membranes and two polarizations. Journal of Parallel and Distributed Computing, 2006, 66(6): 867-872

[7] Alhazov A, Martín-Vide C, Pan L. Solving a PSPACE-complete problem by recognizing P systems with restricted active membranes. Fundamenta Informaticae, 2003, 58(2): 67-77

[8] Pǎun G, Rozenberg G, Salomaa A. Handbook of Membrane Computing. Oxford: Oxford University Press, 2010

[9] Martín-Vide C, Pazos J, Pǎun G, Rodríguez-Patón A. A new class of symbolic abstract neural nets: tissue P systems. In: Proceedings of the 8th Annual International Conference on Computing and Combinatorics. 2002, 290-299

[10] Martín-Vide C, Pazos J, Pǎun G, Rodríguez-Patón A. Tissue P systems. Theoretical Computer Science, 2003, 296(2): 295-326

[11] Zhang G, Gheorghe M, Wu C. A quantum-inspired evolutionary algorithm based on P systems for knapsack problem. Fundamenta Informaticae, 2008, 87(1): 93-116

[12] Zhang G, Liu C, Rong H. Analyzing radar emitter signals with membrane algorithms. Mathematical and Computer Modelling, 2010, 52(11-12): 1997-2010

[13] Nishida T Y. Membrane algorithms. In: Proceedings of the 6th International Workshop on Membrane Computing. 2005, 55-66

[14] Gutiérrez-Naranjo M A, Pérez-Jiménez M J, Romero-Campero F J. A linear solution for QSAT with membrane creation. In: Proceedings of the 6th International Workshop on Membrane Computing. 2005, 241-252

[15] Pan L, Ishdorj T-O. P systems with active membranes and separation rules. Journal of Universal Computer Science, 2004, 10(5): 630-649

[16] Pǎaun G. P systems with active membranes: attacking NP-complete problems. Journal of Automata, Languages and Combinatorics, 2001, 6(1): 75-90

[17] Pǎaun G, Pérez-Jiménez M J, Riscos-Núñez A. Tissue P system with cell division. International Journal of Computers, Communications & Control, 2008, III(3): 295-303

[18] Pan L, Pérez-Jiménez M J. Computational Complexity of Tissue-like P Systems. Journal of Complexity, 2010, 26(3): 296-315

[19] Díaz-Pernil D, Gutiérrez-Naranjo M A, Pérez-Jiménez M J, Riscos- Núñez A. A linear-time tissue P system based solution for the 3- coloring problem. Electronic Notes in Theoretical Computer Science, 2007, 171(2): 81-93

[20] Díaz-Pernil D, Gutiérrez-Naranjo M A, Pérez-Jiménez M J, Riscos- Núñez A. Solving subset sum in linear time by using tissue P system with cell division. In: Proceedings of the 2nd International Work- Conference on the Interplay between Natural and Artificial Computation. 2007, 170-179

[21] Díaz-Pernil D, Gutiérrez-Naranjo M A, Pérez-Jiménez M J, Riscos-Núñez A. Computational efficiency of cellular division in tissue-like membrane systems. Romanian Journal of Information Science and Technology, 2008, 11(3): 229-241

[22] Díaz-Pernil D, Gutiérrez-Naranjo M A, Pérez-Jiménez M J, Riscos-Núñez A. A linear time solution to the partition problem in a cellular tissue-like model. Journal of Computational and Theoretical Nanoscience, 2010, 7(5): 884-889

[23] Zhang X,Wang S, Niu Y, Pan L. Tissue P systems with cell separation: attacking the partition problem. Science China Information Sciences, 2011, 54(2): 293-304

[24] Lu C, Zhang X. Solving vertex cover problem in tissue P systems with cell separation. International Journal of Computers, Communications & Control, 2010, 5(4): 540-550

[25] Díaz-Pernil D, Gutiérrez-Naranjo M A, Pérez-Jiménez M J, Riscos-Núñez A. Solving the independent set problem by using tissue-like P systems with cell division. In: Proceedings of the 3rd International Work-Conference on the Interplay between Natural and Artificial Computation. 2009, 213-222

[26] Pérez-Jiménez M J, Romero-Jiménez Á, Sancho-Caparrini F. A polynomial complexity class in P systems using membrane division. Journal of Automata, Languages and Combinatorics, 2006, 11(4): 423-434

[27] Pérez-Jiménez M J, Romero-Jiménez Á, Sancho-Caparrini F. Complexity classes in models of cellular computing with membranes. Natural Computing, 2003, 2(3): 265-285

[28] Garey M R, Johnson D S. Computers and Intractability A Guide to the Theory of NP-Completeness. New York: W.H. Freeman and Company, 1979

RIGHTS & PERMISSIONS

2014 Higher Education Press and Springer-Verlag Berlin Heidelberg