Solving PSPACE-complete Problems by Polarizationless Recognizer P Systems with Strong Division and Dissolution

Recognizer P systems with active membranes have proven to be able to solve computationally hard problems in a polynomial time. Hence it is interesting to investigate what features, such as electrical charges (polarizations) associated to membranes, evolution rules, communication rules, and strong or weak forms of division rules, are needed to achieve such a computational power. In this paper we show that polarizationless recognizer P systems with active membranes can solve the PSPACE-complete decision problem Quantified 3-sat, working in the maximally parallel way, by using only dissolution rules and a form of controlled strong division for non–elementary membranes.