Monodirectional P Systems

We investigate the in \nuence that the \now of information in membrane systems \nhas on their computational complexity. In particular, we analyse the behaviour of P systems \nwith active membranes where communication only happens from a membrane towards \nits parent, and never in the opposite direction. We prove that these \\monodirectional \nP systems" are, when working in polynomial time and under standard complexity-theoretic \nassumptions, much less powerful than unrestricted ones: indeed, they characterise classes \nof problems de ned by polynomial-time Turing machines with NP oracles, rather than \nthe whole class PSPACE of problems solvable in polynomial space.