Trading Geometric Realism for Efficiency in Tissue P Systems

5noIt 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 R^d, 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 R^d), 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.reservedmixedLeporati Alberto; Manzoni Luca; Mauri Giancarlo; Porreca Antonio E.; Zandron ClaudioLeporati, Alberto; Manzoni, Luca; Mauri, Giancarlo; Porreca Antonio, E.; Zandron, Claudi