Standardized Proofs of PSPACE-completeness of P Systems with Active Membranes

Abstract

Two proofs have been shown for P systems with active membranes in previ- ously published papers, demonstrating that these P systems can solve in polynomial time exactly the class of problems PSPACE. Consequently, these P systems are equivalent (up to a polynomial time reduction) to Second Machine Class models as the alternating Turing machine or the PRAM computer. These proofs were based on a modified definition of uniform families of P systems. Here we demonstrate that the results remain valid also in the case of standard definitions.