Tissue P systems with cell division or cell separation have been proved able to solve NP-complete problems in polynomial time by trading space for time.We show that, when tissue P systems are embedded into the Euclidean space R^3, the power of division and separation decreases due to the geometrical constraints of the space and, as a result, only problems in P can be solved in polynomial time.
Leporati, A., Manzoni, L., Mauri, G., Porreca, A.E., & Zandron, C. (2015). Tissue P systems in the Euclidean space. In M. Gheorghe, I. Petre, M.J. Pérez-Jiménez, G. Rozenberg, & A. Salomaa (a cura di), Multidisciplinary Creativity (pp. 118-128). Bucuresti : Spandugino.
Citazione: | Leporati, A., Manzoni, L., Mauri, G., Porreca, A.E., & Zandron, C. (2015). Tissue P systems in the Euclidean space. In M. Gheorghe, I. Petre, M.J. Pérez-Jiménez, G. Rozenberg, & A. Salomaa (a cura di), Multidisciplinary Creativity (pp. 118-128). Bucuresti : Spandugino. | |
Titolo: | Tissue P systems in the Euclidean space | |
Autori: | Leporati, A; Manzoni, L; Mauri, G; Porreca, AE; Zandron, C | |
Autori: | ||
Presenza di un coautore afferente ad Istituzioni straniere: | No | |
Tipo: | Capitolo o saggio | |
Carattere della pubblicazione: | Scientifica | |
Data di pubblicazione: | 2015 | |
Lingua: | English | |
Titolo del libro: | Multidisciplinary Creativity | |
ISBN: | 9786068401638 | |
Appare nelle tipologie: | 03 - Contributo in libro |