Tissue P Systems with Small Cell Volume

• Autorzy: Leporati A. , Manzoni L. , Mauri G. , Porreca A. E. , Zandron C.

Identyfikatory

DOI

10.3233/FI-2017-1565

• Języki publikacji: EN

Abstrakty

EN

Traditionally, P systems allow their membranes or cells to grow exponentially (or even more) in volume with respect to the size of the multiset of objects they contain in the initial configuration. This behaviour is, in general, biologically unrealistic, since large cells tend to divide in order to maintain a suitably large surface-area-to-volume ratio. On the other hand, it is usually the number of cells that needs to grow exponentially with time by binary division in order to solve NP-complete problems in polynomial time. In this paper we investigate families of tissue P systems with cell division where each cell has a small volume (i.e., sub-polynomial with respect to the input size), assuming that each bit of information contained in the cell, including both those needed to represent the multiset of objects and the cell label, occupies a unit of volume. We show that even a constant volume bound allows us to reach computational universality for families of tissue P systems with cell division, if we employ an exponential-time uniformity condition on the families. Furthermore, we also show that a sub-polynomial volume does not suffice to solve NP-complete problems in polynomial time, unless the satisfiability problem for Boolean formulae can be solved in sub-exponential time, and that solving an NP-complete problem in polynomial time with logarithmic cell volume implies P = NP.

Słowa kluczowe

EN

membrane computing; tissue P system; computability; space complexity

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2017
• Tom: Vol. 154, nr 1/4
• Strony: 261--275
• Opis fizyczny: Bibliogr. 15 poz., rys.

Twórcy

autor

Leporati A.

• Dipartimento di Informatica, Sistemistica e Comunicazione, Università degli Studi di Milano-Bicocca, Viale Sarca 336/14, 20126 Milano, Italy

autor

Manzoni L.

• Dipartimento di Informatica, Sistemistica e Comunicazione, Università degli Studi di Milano-Bicocca, Viale Sarca 336/14, 20126 Milano, Italy

autor

Mauri G.

• Dipartimento di Informatica, Sistemistica e Comunicazione, Università degli Studi di Milano-Bicocca, Viale Sarca 336/14, 20126 Milano, Italy

autor

Porreca A. E.

• Dipartimento di Informatica, Sistemistica e Comunicazione, Università degli Studi di Milano-Bicocca, Viale Sarca 336/14, 20126 Milano, Italy

autor

Zandron C.

• Dipartimento di Informatica, Sistemistica e Comunicazione, Università degli Studi di Milano-Bicocca, Viale Sarca 336/14, 20126 Milano, Italy

Bibliografia

• [1] Alhazov A, Leporati A, Mauri G, Porreca AE, Zandron C. Space complexity equivalence of P systems with active membranes and Turing machines, Theoretical Computer Science, 2014;529:2014, 69–81. URL https://doi.org/10.1016/j.tcs.2013.11.015.
• [2] Burkhard HD. Ordered firing in Petri nets, Elektronische Informationsverarbeitung und Kybernetik (Journal of Information Processing and Cybernetics), 1981;17(2-3):71–86. URL http://dx.doi.org/10.18452/9413.
• [3] Desel J, ReisigW. Place/transition Petri nets, Lectures on Petri nets I: Basic models (W. Reisig, G. Rozenberg, Eds.), vol. 1491 of Advances in Petri Nets, Springer, 1998, pp. 122–173. doi:10.1007/3-540-65306-6_15.
• [4] Frisco P. P systems, Petri nets, and program machines, in: Membrane Computing, 6th International Workshop, WMC 2005 (R. Freund, Gh. Pǎun, G. Rozenberg, A. Salomaa, Eds.), vol. 3850 of Lecture Notes in Computer Science, Springer, 2006, pp. 209–223. doi:10.1007/11603047_15.
• [5] Gutiérrez-Escudero R, Pérez-Jiménez MJ, Rius-Font M. Characterizing tractability by tissue-like P systems in: Membrane Computing 10th International Workshop, WMC2009 (Gh. Pǎun, M. J. Pérez-Jiménez, A. Riscos-Nuñez, G. Rozenberg, A. Salomaa, Eds.), vol. 5957 of Lecture Notes in Computer Science, Springer, 2010, pp. 289–300. doi:10.1007/978-3-642-11467-0_21.
• [6] Impagliazzo R, Paturi R. On the complexity of k-SAT, Journal of Computer and System Sciences, 2001;62(2):367–375. URL https://doi.org/10.1006/jcss.2000.1727.
• [7] Leporati A, Manzoni L, Mauri G, Porreca AE, Zandron C. Constant-space P systems with active membranes, Fundamenta Informaticae, 2014;134(1–2):111–128. doi:10.3233/FI-2014-1094.
• [8] Leporati A, Manzoni L, Mauri G, Porreca AE, Zandron C. Tissue P systems can be simulated efficiently with counting oracles, in: Membrane Computing, 16th International Conference, CMC 2015 (G. Rozenberg, A. Salomaa, J. M. Sempere, C. Zandron, Eds.), vol. 9504 of Lecture Notes in Computer Science, Springer, 2015, pp. 251–261. doi:10.1007/978-3-319-28475-0_17.
• [9] Martín-Vide C, Pǎun Gh, Pazos J, Rodríguez-Patón A. Tissue P systems, Theoretical Computer Science, 2003;296(2):295–326. doi:10.1016/S0304-3975(02)00659-X.
• [10] Minsky M. Computation: Finite and Infinite Machines, Prentice-Hall, 1967.
• [11] Murphy N, Woods D. The computational power of membrane systems under tight uniformity conditions, Natural Computing, 2011;10(1):613–632. doi:10.1007/s11047-010-9244-7.
• [12] Pan L, Pérez-Jiménez MJ. Computational complexity of tissue-like P systems, Journal of Complexity, 2010;26(3):296–315. URL https://doi.org/10.1016/j.jco.2010.03.001.
• [13] Pǎun Gh. P systems with active membranes: Attacking NP-complete problems, Journal of Automata, Languages and Combinatorics, 2001;6(1):75–90.
• [14] Pǎun Gh, Pérez-Jiménez MJ, Riscos-Núñez A. Tissue P systems with cell division, International Journal of Computers, Communications & Control, 2008;3(3):295–303.
• [15] Zandron C, Ferretti C, Mauri G. Solving NP-complete problems using P systems with active membranes, in: Unconventional Models of Computation, UMC’2K, Proceedings of the Second International Conference (I. Antoniou, C. S. Calude, M. J. Dinneen, Eds.), Springer, 2001, pp. 289–301. doi:10.1007/978-1-4471-0313-4_21.