×

P systems attacking hard problems beyond NP: a survey. (English) Zbl 1431.68035

Summary: In the field of membrane computing, a great attention is traditionally paid to the results demonstrating a theoretical possibility to solve NP-complete problems in polynomial time by means of various models of P systems. A bit less common is the fact that almost all models of P systems with this capability are actually stronger: some of them are able to solve PSPACE-complete problems in polynomial time, while others have been recently shown to characterize the class \(\mathbf{P^{\#\mathbf{P}}}\) (which is conjectured to be strictly included in PSPACE). A large part of these results has appeared quite recently. In this survey, we focus on strong models of membrane systems which have the potential to solve hard problems belonging to classes containing NP. These include P systems with active membranes, P systems with proteins on membranes and tissue P systems, as well as P systems with symport/antiport and membrane division and, finally, spiking neural P systems. We provide a survey of computational complexity results of these membrane models, pointing out some features providing them with their computational strength. We also mention a sequence of open problems related to these topics.

MSC:

68Q07 Biologically inspired models of computation (DNA computing, membrane computing, etc.)
68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alhazov, A., Freund, R., Oswald, M. (2005). Tissue P systems with antiport rules and small numbers of symbols and cells. In: C. De Felice, A. Restivo (Eds.) Developments in Language Theory, DLT 2005, Lecture Notes in Computer Science (vol. 3572, pp. 54-78). Berlin: Springer · Zbl 1132.68386
[2] Alhazov, A., Leporati, A., Mauri, G., Porreca, A. E., & Zandron, C. (2014). Space complexity equivalence of P systems with active membranes and turing machines. Theoretical Computer Science, 529, 69-81. · Zbl 1358.68096 · doi:10.1016/j.tcs.2013.11.015
[3] Alhazov, A., Martín-Vide, C., & Pan, L. (2003). Solving a PSPACE-complete problem by P systems with restricted active membranes. Fundamenta Informaticae, 58(2), 67-77. · Zbl 1085.68048
[4] Alhazov, A., & Pérez-Jiménez, M. (2007). Uniform solution of QSAT using polarizationless active membranes. In: J. Durand-Lose, M. Margenstern (Eds.) Machines, Computations, and Universality, 5th International Conference, MCU 2007, Lecture Notes in Computer Science (vol. 4664, pp. 122-133). Springer. · Zbl 1211.68194
[5] Bernardini, F., & Gheorghe, M. (2005). Cell communication in tissue P systems and cell division in population P systems. Soft Computing, 9(9), 640-649. · Zbl 1101.68574 · doi:10.1007/s00500-004-0393-4
[6] Cavaliere, M. (2013). Time-free solutions to hard computational problems. In: M. Gheorghe, G. Păun, M.J. Pérez-Jiménez, G. Rozenberg (Eds.) Research Frontiers of Membrane Computing: Open Problems and Research Topics, International Journal of Foundations of Computer Science (vol. 24 (5), pp. 579-582). World Scientific (2013). Section 11
[7] Cavaliere, M., & Sburlan, D. (2005). Time-independent P systems. In: G. Mauri, G. Paun, M.J. Pérez-Jiménez, G. Rozenberg, A. Salomaa (Eds.) Membrane Computing, 5th International Workshop, WMC 2004, Lecture Notes in Computer Science (vol. 3365, pp. 239-258). Springer · Zbl 1117.68355
[8] Chandra, A.K., & Stockmeyer, L.J. (1976). Alternation. In: 17th Annual Symposium on Foundations of Computer Science, Houston, Texas, USA, 25-27 October 1976, pp. 98-108. IEEE Computer Society. https://doi.org/10.1109/SFCS.1976.4 · Zbl 0473.68043
[9] Csuhaj-Varjú, E., Gheorghe, M., Rozenberg, G., Salomaa, A., & Vaszil, G. (Eds.). (2013). Membrane Computing—13th International Conference, CMC13, Lecture Notes in Computer Science (vol. 7762). Springer · Zbl 1258.68007
[10] Díaz-Pernil, D., Pérez-Jiménez, M. J., & Romero-Jiménez, Á. (2009). Efficient simulation of tissue-like P systems by transition cell-like P systems. Natural Computing, 8(4), 797-806. · Zbl 1185.68335 · doi:10.1007/s11047-008-9102-z
[11] Eleftherakis, G., Kefalas, P., Paun, G., Rozenberg, G., & Salomaa, A. (eds.) (2007). Membrane Computing, 8th International Workshop, WMC 2007, Lecture Notes in Computer Science (vol. 4860). Springer · Zbl 1132.68008
[12] Freund, R., Păun, G., & Pérez-Jiménez, M. (2005). Tissue P systems with channel states. Theoretical Computer Science, 330, 101-116. · Zbl 1078.68061 · doi:10.1016/j.tcs.2004.09.013
[13] Gutiérrez-Escudero, R., Pérez-Jiménez, M., & Rius-Font, M. Characterizing tractability by tissue-like P systems. In: Păun et al. [53], pp. 289-300 · Zbl 1273.68124
[14] Ionescu, M., Păun, G., & Yokomori, T. (2006). Spiking neural P systems. Fundamenta Informaticae, 71(2—-3), 279-308. · Zbl 1110.68043
[15] Ishdorj, T. O., Leporati, A., Pan, L., Zeng, X., & Zhang, X. (2010). Deterministic solutions to QSAT and Q3SAT by spiking neural P systems with pre-computed resources. Theoretical Computer Science, 411(25), 2345-2358. · Zbl 1208.68172 · doi:10.1016/j.tcs.2010.01.019
[16] Krishna, S., Lakshmanan, K., & Rama, R. (2003). Tissue P systems with contextual and rewriting rules. In: Paun, G., Rozenberg, G., Salomaa, A., Zandron C. (Eds.) Membrane Computing, Lecture Notes in Computer Science (vol. 2597, pp. 339-351). Springer, Berlin · Zbl 1023.68049
[17] Krishna, S.N. (2007). On the computational power of flip-flop proteins on membranes. In: S.B. Cooper, B. Löwe, A. Sorbi (Eds.) Computation and Logic in the Real World, Lecture Notes in Computer Science (vol. 4497, pp. 695-704). Springer · Zbl 1151.68417
[18] Lakshmanan, K.; Rama, R.; Subramanian, K. (ed.); Rangarajan, K. (ed.); Mukund, M. (ed.), The computational efficiency of insertion-deletion tissue P systems, 235-245 (2006), New York · doi:10.1142/9789812773036_0016
[19] van Leeuwen, J. (Ed.). (1990). Handbook of Theoretical Computer Science, Vol. A: Algorithms and Complexity. Amsterdam: Elsevier. · Zbl 0712.68054
[20] Leporati, A. (2014). Computational complexity of P systems with active membranes. In: A. Alhazov, S. Cojocaru, M. Gheorghe, Y. Rogozhin, G. Rozenberg, A. Salomaa (Eds.) Fourteenth International Conference on Membrane Computing, CMC14, Lecture Notes in Computer Science (vol. 8340). Berlin: Springer. · Zbl 1407.68173
[21] Leporati, A., Ferretti, C., Mauri, G., Pérez-Jiménez, M., & Zandron, C. (2009). Complexity aspects of polarizationless membrane systems. Natural Computing, 8(4), 703-717. · Zbl 1185.68339 · doi:10.1007/s11047-008-9100-1
[22] Leporati, A., Manzoni, L., Mauri, G., Porreca, A.E., & Zandron, C. (2014). Simulating elementary active membranes, with an application to the P conjecture. In: M. Gheorghe, G. Rozenberg, A. Salomaa, P. Sosík, C. Zandron (Eds.) Membrane Computing—15th International Conference, CMC15, Lecture Notes in Computer Science (vol. 8961, pp. 284-299). Springer. · Zbl 1457.68102
[23] Leporati, A., Manzoni, L., Mauri, G., Porreca, A. E., & Zandron, C. (2015). Membrane division, oracles, and the counting hierarchy. Fundamental Information, 138(1-2), 97-111. · Zbl 1357.68064
[24] Leporati, A., Manzoni, L., Mauri, G., Porreca, A. E., & Zandron, C. (2017). Characterising the complexity of tissue P systems with fission rules. Journal of Computer and System Sciences, 90, 115-128. · Zbl 1374.68218 · doi:10.1016/j.jcss.2017.06.008
[25] Leporati, A., Manzoni, L., Mauri, G., Porreca, A.E., & Zandron, C. (2017). Shallow non-confluent P systems. In: A. Leporati, G. Rozenberg, A. Salomaa, C. Zandron (Eds.) Membrane Computing: 17th International Conference, CMC 2016, Lecture Notes in Computer Science (vol. 10105, pp. 307-316). Cham: Springer · Zbl 1483.68124
[26] Leporati, A., Manzoni, L., Mauri, G., Porreca, A.E., & Zandron, C. (2018) Solving qsat in sublinear depth. In: T. Hinze, J. Behre (Eds.) Proceedings of the Nineteenth International Conference on Membrane Computing (CMC19) (pp. 149-162). Berlin: Pro Business. · Zbl 1522.68215
[27] Leporati, A., Manzoni, L., Mauri, G., Porreca, A. E., & Zandron, C. (2018). Subroutines in P systems and closure properties of their complexity classes. Theoretical Computer Science. https://doi.org/10.1016/j.tcs.2018.06.012. · Zbl 1497.68195 · doi:10.1016/j.tcs.2018.06.012
[28] Leporati, A., Manzoni, L., Mauri, G., Porreca, A. E., & Zandron, C. (2018). A survey on space complexity of P systems with active membranes. International Journal of Advances in Engineering Sciences and Applied Mathematics, 10(3), 221-229. · doi:10.1007/s12572-018-0227-8
[29] Leporati, A., Zandron, C., Ferretti, C., & Mauri, G. (2007). On the computational power of spiking neural P systems. In M. Gutiérrez-Naranjo, G. Păun, A. Romero-Jiménez, & A. Riscos-Núnez (Eds.), Fifth Brainstorming Week on Membrane Computing (pp. 227-245). Sevilla: Fenix Editora. · Zbl 1137.68396
[30] Liu, X., Suo, J., Leung, S., Liu, J., & Zeng, X. (2015). The power of time-free tissue P systems: Attacking NP-complete problems. Neurocomputing, 159(1), 151-156. · doi:10.1016/j.neucom.2015.01.072
[31] Macías-Ramos, L.F., Pérez-Jiménez, M.J., Riscos-Núñez, A., Rius-Font, M., & Valencia-Cabrera, L. The efficiency of tissue P systems with cell separation relies on the environment. In: Csuhaj-Varjú et al. [9] (pp. 243-256). · Zbl 1388.68050
[32] Martín Vide, C., Pazos, J., Păun, G., & Rodríguez Patón, A. (2002). A new class of symbolic abstract neural nets: Tissue P systems. In: O. Ibarra, L. Zhang (Eds.) Computing and Combinatorics, Lecture Notes in Computer Science (vol. 2387, pp. 573-679). Berlin: Springer. · Zbl 1077.68645
[33] Martín Vide, C., Pazos, J., Păun, G., & Rodríguez Patón, A. (2003). Tissue P systems. Theoretical Computer Science, 296, 295-326. · Zbl 1045.68063 · doi:10.1016/S0304-3975(02)00659-X
[34] Mauri, G., Leporati, A., Manzoni, L., Porreca, A.E., & Zandron, C. (2015). Complexity classes for membrane systems: A survey. In: A.H. Dediu, E. Formenti, C. Martín-Vide, B. Truthe (Eds.) Language and Automata Theory and Applications: 9th International Conference, LATA 2015, Lecture Notes in Computer Science (vol. 8977, pp. 56-69). Springer. · Zbl 1451.68115
[35] Murphy, N., & Woods, D. Active membrane systems without charges and using only symmetric elementary division characterise P. In: Eleftherakis et al. [11] (pp. 367-384). · Zbl 1137.68400
[36] Murphy, N., & Woods, D. (2011). The computational power of membrane systems under tight uniformity conditions. Natural Computing, 10(1), 613-632. · Zbl 1214.68159 · doi:10.1007/s11047-010-9244-7
[37] Murphy, N., & Woods, D. (2014). Uniformity is weaker than semi-uniformity for some membrane systems. Fundamenta Informaticae, 134(1-2), 129-152. · Zbl 1315.68129
[38] Orellana-Martín, D., Martínez-del Amor, M. Á., Pérez-Hurtado, I., Riscos-Núñez, A., Valencia-Cabrera, L., & Pérez-Jiménez, M. J. (2018). When object production tunes the efficiency of membrane systems. Theoretical Computer Science. https://doi.org/10.1016/j.tcs.2018.04.013. · Zbl 1395.68128 · doi:10.1016/j.tcs.2018.04.013
[39] Pan, L., & Ishdorj, T. O. (2004). P systems with active membranes and separation rules. Journal of Universal Computer Science, 10(5), 630-649.
[40] Pan, L., Păun, G., & Pérez-Jiménez, M. J. (2011). Spiking neural P systems with neuron division and budding. Science China Information Sciences, 54(8), 1596. · Zbl 1267.68158 · doi:10.1007/s11432-011-4303-y
[41] Pan, L., Song, B., Valencia-Cabrera, L., & Pérez-Jiménez, M. J. (2018). The computational complexity of tissue P systems with evolutional symport/antiport rules. Complexity. https://doi.org/10.1155/2018/3745210. · Zbl 1407.68177 · doi:10.1155/2018/3745210
[42] Păun, A., & Rodríguez-Patón, A. On flip-flop membrane systems with proteins. In: Eleftherakis et al. [11]. (pp. 414-427). · Zbl 1137.68402
[43] Pérez-Jiménez, M. A computational complexity theory in membrane computing. In: Păun et al. [53] (pp. 125-148). · Zbl 1273.68185
[44] Pérez-Jiménez, M., Romero-Jiménez, A., & Sancho-Caparrini, F. (2003). Complexity classes in models of cellular computing with membranes. Natural Computing, 2, 265-285. · Zbl 1048.68043 · doi:10.1023/A:1025449224520
[45] Pérez-Jiménez, M. J., & Sosík, P. (2015). An optimal frontier of the efficiency of tissue P systems with cell separation. Fundamental Information, 138(1-2), 45-60. · Zbl 1357.68067
[46] Porreca, A., Leporati, A., Mauri, G., & Zandron, C. (2011). P systems with elementary active membranes: beyond NP and coNP. In: M. Gheorghe, T. Hinze, G. Păun, G. Rozenberg, A. Salomaa (eds.) Membrane Computing—11th International Conference, CMC11, Lecture Notes in Computer Science (vol. 6501, pp. 383-392). Springer. · Zbl 1259.68064
[47] Porreca, A.E., Leporati, A., Mauri, G., & Zandron, C. (2012). P systems simulating oracle computations. In: M. Gheorghe, G. Păun, G. Rozenberg, A. Salomaa, S. Verlan (eds.) Membrane Computing—12th International Conference, CMC12, Lecture Notes in Computer Science (vol. 7184, pp. 346-358). Springer. · Zbl 1350.68113
[48] Porreca, A. E., Mauri, G., & Zandron, C. (2010). Non-confluence in divisionless P systems with active membranes. Theoretical Computer Science, 411(6), 878-887. · Zbl 1191.68325 · doi:10.1016/j.tcs.2009.07.032
[49] Porreca, A.E., Murphy, N., & Pérez-Jiménez, M.J. (2012). An optimal frontier of the efficiency of tissue P systems with cell division. In: García-Quismondo, M. et al. (ed.) Proceedings of the Tenth Brainstorming Week on Membrane Computing (vol. II, pp. 141-166). Fénix Editora, Sevilla.
[50] Păun, A., & Popa, B. (2006). P systems with proteins on membranes. Fundamenta Informaticae, 72(4), 467-483. · Zbl 1099.68031
[51] Păun, A., & Popa, B. (2006) P systems with proteins on membranes and membrane division. In: O. Ibarra, Z. Dang (Eds.) Developments in Language Theory, DLT 2006, Lecture Notes in Computer Science (vol. 4036, pp. 292-303). Berlin: Springer. · Zbl 1227.68027
[52] Păun, A., & Păun, G. (2002). The power of communication: P systems with symport/antiport. New Generation Computer, 20(3), 295-306. · Zbl 1024.68037 · doi:10.1007/BF03037362
[53] Păun, G., Pérez-Jiménez, M., Riscos-Núnez, A., Rozenberg, G., & Salomaa, A. (eds.) (2010). Membrane Computing, 10th International Workshop, WMC 2009, Lecture Notes in Computer Science (vol. 5957). Berlin: Springer. · Zbl 1179.68004
[54] Păun, G., Rozenberg, G., & Salomaa, A. (Eds.). (2010). The Oxford Handbook of Membrane Computing. Oxford: Oxford University Press. · Zbl 1237.68001
[55] Păun, G. (2001). P systems with active membranes: attacking NP-complete problems. Journal of Automata, Languages, and Combinatorics, 6(1), 75-90. · Zbl 0970.68066
[56] Song, B., Pérez-Jiménez, M. J., & Pan, L. (2015). Efficient solutions to hard computational problems by P systems with symport/antiport rules and membrane division. Biosystems, 130, 51-58. · doi:10.1016/j.biosystems.2015.03.002
[57] Song, B., Pérez-Jiménez, M. J., & Pan, L. (2017). An efficient time-free solution to QSAT problem using P systems with proteins on membranes. Information and Computation, 256, 287-299. · Zbl 1376.68041 · doi:10.1016/j.ic.2017.06.005
[58] Song, B., Song, T., & Pan, L. (2017). A time-free uniform solution to subset sum problem by tissue P systems with cell division. Mathematical Structures in Computer Science, 27(1), 17-32. · Zbl 1364.68207 · doi:10.1017/S0960129515000018
[59] Song, T., Macas-Ramos, L. F., Pan, L., & Pérez-Jiménez, M. J. (2014). Time-free solution to SAT problem using P systems with active membranes. Theoretical Computer Science, 529, 61-68. · Zbl 1358.68103 · doi:10.1016/j.tcs.2013.11.014
[60] Sosík, P. Limits of the power of tissue P systems with cell division. In: Csuhaj-Varjú et al. [9] (pp. 390-403). · Zbl 1388.68057
[61] Sosík, P., & Cienciala, L. (2012). Tissue P systems with cell separation: upper bound by PSPACE. In: A.H. Dediu, C. Martín-Vide, B. Truthe (Eds.) Theory and Practice of Natural Computing, TPNC 2012, Lecture Notes in Computer Science (vol. 7505, pp. 201-215). Springer. · Zbl 1374.68222
[62] Sosík, P., & Rodríguez-Patón, A. (2007). Membrane computing and complexity theory: A characterization of PSPACE. Journal of Computer and System Sciences, 73(1), 137-152. · Zbl 1178.68260 · doi:10.1016/j.jcss.2006.10.001
[63] Sosík, P. (2011). Selected topics in computational complexity of membrane systems. In: J. Kelemen, A. Kelemenová (Eds.) Computation, Cooperation and Life, Lecture Notes in Computer Science (vol. 6610, pp. 125-137). Springer. · Zbl 1330.68081
[64] Sosík, P., Păun, A., & Rodríguez-Patón, A. (2013). P systems with proteins on membranes characterize pspace. Theoretical Computer Science, 488, 78-95. · Zbl 1293.68175 · doi:10.1016/j.tcs.2013.03.009
[65] Sosík, P., Rodríguez-Patón, A., & Ciencialová, L. (2013). Polynomial time bounded computations in spiking neural P systems. Neural Network World, 23(1), 31-48. IF=0,412. · Zbl 1259.68074 · doi:10.14311/NNW.2013.23.003
[66] Valsecchi, A., Porreca, A., Leporati, A., Mauri, G., & Zandron, C. An efficient simulation of polynomial-space turing machines by P systems with active membranes. In: Păun et al. [53] (pp. 461-478). · Zbl 1273.68138
[67] Zandron, C., Leporati, A., Ferretti, C., Mauri, G., & Pérez-Jiménez, M. (2008). On the computational efficiency of polarizationless recognizer P systems with strong division and dissolution. Fundamenta Informaticae, 87(1), 79-91. · Zbl 1154.68053
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.