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 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.
Trading Geometric Realism for Efficiency in Tissue P Systems
Manzoni Luca;
2016-01-01
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 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.File in questo prodotto:
| File | Dimensione | Formato | |
|---|---|---|---|
|
02-aleporati.pdf
Accesso chiuso
Tipologia:
Documento in Versione Editoriale
Licenza:
Copyright Editore
Dimensione
361.53 kB
Formato
Adobe PDF
|
361.53 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
