P systems with active membranes: trading time for space

Research paper by Antonio E. Porreca, Alberto Leporati, Giancarlo Mauri, Claudio Zandron

Indexed on: 25 Mar '10Published on: 25 Mar '10Published in: Natural computing


We consider recognizer P systems having three polarizations associated to the membranes, and we show that they are able to solve the PSPACE-complete problem Quantified 3SAT when working in polynomial space and exponential time. The solution is uniform (all the instances of a fixed size are solved by the same P system) and uses only communication rules: evolution rules, as well as membrane division and dissolution rules, are not used. Our result shows that, as it happens with Turing machines, this model of P systems can solve in exponential time and polynomial space problems that cannot be solved in polynomial time, unless P = SPACE.