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 |