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., 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.

Tissue P systems in the Euclidean space

LEPORATI, ALBERTO OTTAVIO;MANZONI, LUCA;MAURI, GIANCARLO;PORRECA, ANTONIO ENRICO;ZANDRON, CLAUDIO
2015

Abstract

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.
Capitolo o saggio
P systems; computational complexity
English
Multidisciplinary Creativity
9786068401638
Leporati, A., Manzoni, L., Mauri, G., Porreca, A., 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.
Leporati, A; Manzoni, L; Mauri, G; Porreca, A; Zandron, C
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10281/133817
Citazioni
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
Social impact