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., Zandron, C. (2016). Trading geometric realism for efficiency in tissue P systems. ROMANIAN JOURNAL OF INFORMATION SCIENCE AND TECHNOLOGY, 19(1-2), 17-30.
Trading geometric realism for efficiency in tissue P systems
LEPORATI, ALBERTO OTTAVIO;MANZONI, LUCA;MAURI, GIANCARLO;PORRECA, ANTONIO ENRICO;ZANDRON, CLAUDIO
2016
Abstract
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.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
