We prove that polynomial-time tissue P systems with cell division or cell separation can be simulated efficiently by Turing machines with oracles for counting problems. This shows that the corresponding complexity classes are included in P#P, thus improving, under standard complexity theory assumptions, the previously known upper bound PSPACE.
Leporati, A., Manzoni, L., Mauri, G., Porreca, A., Zandron, C. (2015). Tissue P systems can be simulated efficiently with counting oracles. In 16th International Conference on Membrane Computing, CMC 2015; Valencia; Spain; 17-21 August 2015 (pp.251-261). Springer Verlag [10.1007/978-3-319-28475-0_17].
Tissue P systems can be simulated efficiently with counting oracles
LEPORATI, ALBERTO OTTAVIOPrimo
;MANZONI, LUCASecondo
;MAURI, GIANCARLO;PORRECA, ANTONIO ENRICOPenultimo
;ZANDRON, CLAUDIO
2015
Abstract
We prove that polynomial-time tissue P systems with cell division or cell separation can be simulated efficiently by Turing machines with oracles for counting problems. This shows that the corresponding complexity classes are included in P#P, thus improving, under standard complexity theory assumptions, the previously known upper bound PSPACE.
| File | Dimensione | Formato | |
|---|---|---|---|
|
Paper.pdf
accesso aperto
Descrizione: Preprint
Dimensione
379.9 kB
Formato
Adobe PDF
|
379.9 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
