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.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
