The time-space trade-off in membrane computing

Membrane systems (also called P systems) are unconventional, parallel computing devices inspired by the internal working of biological cells. Some variants of membrane systems (in particular, P systems with elementary active membranes) have been known to be able to solve NP-complete problems in polynomial time by trading space for time, exploring in parallel the whole exponential-size space of candidate solutions. Here we provide a formal notion of space complexity for P systems, in order to be able to prove results about the computing power and limitations of P systems with active membranes working in bounded space. As a result, we show that P systems working in polynomial space solve exactly the same problem as Turing machines working in polynomial space. Furthermore, we show that P systems with elementary active membranes running in exponential space not only solve NP-complete problems in polynomial time, but also counting problems and the whole polynomial hierarchy.