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 PMC AM(-d,-n)_{\mathcal{AM}(-{\rm d},-{\rm 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.

Fulltext Preview

Image of the first page of the fulltext document