Volume 10, Number 1, 167-182, DOI: 10.1007/s11047-010-9189-x

P systems with active membranes: trading time for space

Antonio E. Porreca, Alberto Leporati, Giancarlo Mauri and Claudio Zandron

From the issue entitled "Part I: Special Issue "Modelling Bioprocesses" "Dedicated to Prof.V.Manca on the Occasion of his 60th Birthday" Part II: Special Issue "Interaction between Biology and Computation" Part III: Special Issue "DNA Computing and Molecular Programming" "Selected Papers from the 15th International Conference on DNA Computing and Molecular Programming""

View Related Documents

Abstract

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.

Keywords  Membrane computing – Computational complexity – Register machines

Fulltext Preview

Image of the first page of the fulltext document