It has been recently proved that polynomial-time tissue P systems with cell division are only able to solve decision problems in the complexity class P when their cell structure is embedded into the Euclidean space Rd, for d ∈ N. In this paper we show that if the space has an appropriate shape and is polynomial-time navigable (but not embeddable in Rd), then it is possible to even solve PSPACE-complete problems. This means that the computational power of tissue P systems can be varied from P to PSPACE by just operating on the properties of the space in which they are located.
Leporati, A., Manzoni, L., Mauri, G., Porreca, A.E., & Zandron, C. (2016). Trading geometric realism for efficiency in tissue P systems. ROMANIAN JOURNAL OF INFORMATION SCIENCE AND TECHNOLOGY, 19(1-2), 17-30.
Citazione: | Leporati, A., Manzoni, L., Mauri, G., Porreca, A.E., & Zandron, C. (2016). Trading geometric realism for efficiency in tissue P systems. ROMANIAN JOURNAL OF INFORMATION SCIENCE AND TECHNOLOGY, 19(1-2), 17-30. |
Tipo: | Articolo in rivista - Articolo scientifico |
Carattere della pubblicazione: | Scientifica |
Presenza di un coautore afferente ad Istituzioni straniere: | No |
Titolo: | Trading geometric realism for efficiency in tissue P systems |
Autori: | Leporati, A; Manzoni, L; Mauri, G; Porreca, AE; Zandron, C |
Autori: | |
Data di pubblicazione: | 2016 |
Lingua: | English |
Rivista: | ROMANIAN JOURNAL OF INFORMATION SCIENCE AND TECHNOLOGY |
Appare nelle tipologie: | 01 - Articolo su rivista |