A Gap in the Space Hierarchy of P Systems with Active Membranes

We prove that uniform families of P systems with active membranes using logarithmic workspace, in addition to a polynomial number of read-only input objects, can efficiently simulate polynomial-space Turing machines, and thus characterise the complexity class PSPACE. Since PSPACE was already known to be characterised by P systems working in polynomial space, this theorem implies, perhaps counter-intuitively, that the latter systems are exponentially wasteful, and a large part of the computation can be carried out by P systems just by moving the objects between their regions, without the need to rewrite them. This result also provides the rst scenario where P systems are not equivalent to Turing machines with respect to their space complexity.