We show how existing P systems with active membranes can be used as modules inside a larger P system; this allows us to simulate subroutines or oracles. As an application of this construction, which is (in principle) quite general, we provide a new, improved lower bound to the complexity class PMCAM(−d,−n) of problems solved by polynomial-time P systems with (restricted) elementary active membranes: this class is proved to contain P^PP and hence, by Toda’s theorem, the whole polynomial hierarchy.

Porreca, A., Leporati, A., Mauri, G., & Zandron, C. (2012). P Systems Simulating Oracle Computations. In Proc. CMC 2011 – 12th Int. Conf. on Membrane Computing (pp.346-358). Berlin : Springer Verlag [10.1007/978-3-642-28024-5_23].

P Systems Simulating Oracle Computations

PORRECA, ANTONIO ENRICO;LEPORATI, ALBERTO OTTAVIO;MAURI, GIANCARLO;ZANDRON, CLAUDIO
2012

Abstract

We show how existing P systems with active membranes can be used as modules inside a larger P system; this allows us to simulate subroutines or oracles. As an application of this construction, which is (in principle) quite general, we provide a new, improved lower bound to the complexity class PMCAM(−d,−n) of problems solved by polynomial-time P systems with (restricted) elementary active membranes: this class is proved to contain P^PP and hence, by Toda’s theorem, the whole polynomial hierarchy.
No
slide + paper
Scientifica
P systems; Oracle Computations; complexity classes
English
Int. Conf. on Membrane Computing
978-3-642-28023-8
Porreca, A., Leporati, A., Mauri, G., & Zandron, C. (2012). P Systems Simulating Oracle Computations. In Proc. CMC 2011 – 12th Int. Conf. on Membrane Computing (pp.346-358). Berlin : Springer Verlag [10.1007/978-3-642-28024-5_23].
Porreca, A; Leporati, A; Mauri, G; Zandron, C
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/10281/42639
Citazioni
  • Scopus 12
  • ???jsp.display-item.citation.isi??? ND
Social impact