Solving a PSPACE-complete problem by symport/antiport P systems with promoters and membrane division. (English) Zbl 1490.68102
Summary: Symport/antiport P systems with membrane division are parallel computing models, which can solve NP-complete problems in polynomial time. In this paper, promoters are incorporated into symport/antiport P systems with membrane division, and a new kind of P systems, called symport/antiport P systems with promoters and membrane division (SAPD P systems, for short) is proposed. The computational efficiency of SAPD P systems is investigated. We show that a uniform solution to the QSAT problem is given by using only symport rules of length at most 2 and promoters of length at most 1 in a polynomial time (Note that the QSAT problem can be solved by symport/antiport P systems with membrane division using both symport rules and antiport rules of length at most 3 [B. Song et al., “Efficient solutions to hard computational problems by P systems with symport/antiport rules and membrane division”, Biosystems 130, 51–58 (2015; doi:10.1016/j.biosystems.2015.03.002)].
MSC:
| 68Q07 | Biologically inspired models of computation (DNA computing, membrane computing, etc.) |
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
| 68Q25 | Analysis of algorithms and problem complexity |
References:
| [1] | Alhazov, A., & Freund, R. (2005). P systems with one membrane and symport/antiport rules of five symbols are computationally complete. In: Proceedings of Third Brainstorming Week On Membrane Computing, Sevilla, Spain, pp. 19-28. |
| [2] | Alhazov, A.; Rogozhin, Y., Towards A characterization of P systems with minimal symport/antiport and two membranes. Vol. 4361 of lecture notes in computer science, 135-153 (2006), Springer · Zbl 1187.68222 |
| [3] | Alhazov, A.; Pérez-Jiménez, MJ; Durand-Lose, J.; Margenstern, M., Uniform solution of QSAT using polarizationless active membranes, LNCS, 122-133 (2007), Springer · Zbl 1211.68194 |
| [4] | Aman, B.; Ciobanu, G., Efficiently solving the bin packing problem through bio-inspired mobility, Acta Informatica, 54, 4, 435-445 (2017) · Zbl 1371.68079 · doi:10.1007/s00236-016-0264-3 |
| [5] | Ardelean, I., Díaz-Pernil, D., Gutiérrez-Naranjo, M.A., Peña-Cantillana, F., Reina-Molina, R., & Sarchizian, I. (2012) Counting cells with tissue-Like P systems. In: Proceedings of the Tenth Brainstorming Week on Membrane Computing, Sevilla, Spain, pp. 69-78. |
| [6] | Bernardini, F., & Gheorghe, M. (2003) On the power of minimal symport/antiport. In: Proceedings of the 3rd Workshop on Membrane Computing, Tarragona, pp. 72-83. |
| [7] | Bottoni, P.; Martín-Vide, C.; Păun, GH; Rozenberg, G., Membrane systems with promoters/inhibitors, Acta Informatica, 38, 695-720 (2002) · Zbl 1034.68038 · doi:10.1007/s00236-002-0090-7 |
| [8] | Cienciala, L.; Ciencialová, L., Some new results of P colonies with bounded parameters, Natural Computing (2016) · Zbl 1415.68075 · doi:10.1007/s11047-016-9591-0 |
| [9] | Ciobanu, G.; Pan, L.; Păun, GH; Pérez-Jiménez, MJ, P systems with minimal parallelism, Theoretical Computer Science, 378, 117-130 (2007) · Zbl 1118.68066 · doi:10.1016/j.tcs.2007.03.044 |
| [10] | Díaz-Pernil, D.; Peña-Cantillana, F.; Gutiérrez-Naranjo, MA, A parallel algorithm for skeletonizing images by using spiking neural P systems, Neurocomputing, 115, 81-91 (2013) · doi:10.1016/j.neucom.2012.12.032 |
| [11] | Ionescu, M.; Păun, GH; Yokomori, T., Spiking neural P systems, Fundamenta Informaticae, 71, 2-3, 279-308 (2006) · Zbl 1110.68043 |
| [12] | Macías-Ramos, LF; Song, B.; Pan, L.; Pérez-Jiménez, MJ, Membrane fission: A computational complexity perspective, Complexity, 21, 6, 321-334 (2016) · doi:10.1002/cplx.21691 |
| [13] | Martín-Vide, C.; Pazos, J.; Păun, GH; Rodríguez-Patón, A., Tissue P systems, Theoretical Computer Science, 296, 2, 295-326 (2003) · Zbl 1045.68063 · doi:10.1016/S0304-3975(02)00659-X |
| [14] | Pan, L.; Păun, Gh; Song, B., Flat maximal parallelism in P systems with promoters, Theoretical Computer Science, 623, 83-91 (2016) · Zbl 1336.68073 · doi:10.1016/j.tcs.2015.10.027 |
| [15] | Pan, L.; Pérez-Jiménez, MJ, Computational complexity of tissue-like P systems, Journal of Complexity, 26, 3, 296-315 (2010) · Zbl 1195.68050 · doi:10.1016/j.jco.2010.03.001 |
| [16] | Pan, L.; Song, B.; Valencia-Cabrera, L.; Pérez-Jiménez, MJ, The computational complexity of tissue P systems with evolutional symport/antiport rules, Complexity, 3745210, 1-22 (2018) · Zbl 1407.68177 |
| [17] | Papadimitriou, CH, Computational complexity (1994), Addison-Wesley · Zbl 0833.68049 |
| [18] | 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 · doi:10.1007/BF03037362 |
| [19] | Păun, GH, Computing with membranes, Journal of Computer and System Sciences, 61, 1, 108-143 (2000) · Zbl 0956.68055 · doi:10.1006/jcss.1999.1693 |
| [20] | Păun, GH, Membrane computing. An introduction (2002), Springer-Verlag · Zbl 1034.68037 · doi:10.1007/978-3-642-56196-2 |
| [21] | Păun, Gh; Pazos, J.; Pérez-Jiménez, MJ; Rodríguez-Patón, A., Symport/antiport P systems with three objects are universal, Fundamenta Informaticae, 64, 1-4 (2005) · Zbl 1102.68031 |
| [22] | Păun, Gh; Rozenberg, G.; Salomaa, A., The oxford handbook of membrane computing (2010), Oxford University Press · Zbl 1237.68001 |
| [23] | Pérez-Jiménez, MJ; Sosík, P., An optimal frontier of the efficiency of tissue P systems with cell separation, Fundamenta Informaticae, 138, 45-60 (2015) · Zbl 1357.68067 · doi:10.3233/FI-2015-1197 |
| [24] | Peng, H.; Wang, J.; Pérez-Jiménez, MJ; Wang, H.; Shao, J.; Wang, T., Fuzzy reasoning spiking neural p system for fault diagnosis, Information Sciences, 235, 106-116 (2013) · Zbl 1284.68265 · doi:10.1016/j.ins.2012.07.015 |
| [25] | Reina-Molina, R., Díaz-Pernil, D., & Gutiérrez-Naranjo, M.A. (2012) Cell complexes and membrane computing for thinning 2D and 3D images. In: Proceedings of the Tenth Brainstorming Week on Membrane Computing, Sevilla, Spain, pp. 167-186. |
| [26] | Rozenberg, G.; Salomaa, A., Handbook of formal languages (1997), Springer · Zbl 0866.68057 |
| [27] | Song, B.; Pérez-Jiménez, MJ; Pan, L., An efficient time-free solution to QSAT problem using P systems with proteins on membranes, Information and Computation, 256, 287-299 (2017) · Zbl 1376.68041 · doi:10.1016/j.ic.2017.06.005 |
| [28] | Song, B.; Pan, L., The computational power of tissue-like P systems with promoters, Theoretical Computer Science, 641, 43-52 (2016) · Zbl 1344.68080 · doi:10.1016/j.tcs.2016.05.022 |
| [29] | Song, B.; Pérez-Jiménez, MJ; Pan, L., Efficient solutions to hard computational problems by P systems with symport/antiport rules and membrane division, BioSystems, 130, 51-58 (2015) · doi:10.1016/j.biosystems.2015.03.002 |
| [30] | Song, B.; Li, K.; Orellana-Martín, D.; Valencia-Cabrera, L.; Pérez-Jiménez, MJ, Cell-like P systems with evolutional symport/antiport rules and membrane creation, Information and Computation, 275, 104542 (2020) · Zbl 1496.68144 · doi:10.1016/j.ic.2020.104542 |
| [31] | Song, B.; Li, K.; Orellana-Martín, D.; Pérez-Jiménez, MJ; Pérez-Hurtado, I., A survey of nature-inspired computing: Membrane computing, ACM Computing Surveys, 54, 1, 1-31 (2021) · doi:10.1145/3431234 |
| [32] | Song, B.; Zeng, X.; Jiang, M.; Pérez-Jiménez, MJ, Monodirectional tissue P systems with promoters, IEEE Transactions on Cybernetics, 51, 1, 438-450 (2021) · doi:10.1109/TCYB.2020.3003060 |
| [33] | Song, B.; Zhang, C.; Pan, L., Tissue-like P systems with evolutional symport/antiport rules, Information Sciences, 378, 177-193 (2017) · Zbl 1429.68074 · doi:10.1016/j.ins.2016.10.046 |
| [34] | Sosík, P.; Păun, A.; Rodríguez-Patón, A., P systems with proteins on membranes characterize PSPACE, Theoretical Computer Science, 488, 78-95 (2013) · Zbl 1293.68175 · doi:10.1016/j.tcs.2013.03.009 |
| [35] | Zhang, G.; Gheorghe, M.; Pan, L.; Pérez-Jiménez, MJ, Evolutionary membrane computing: A comprehensive survey and new results, Information Sciences, 279, 528-551 (2014) · doi:10.1016/j.ins.2014.04.007 |
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.
