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 |