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.
Leporati, A., Zandron, C., Ferretti, C., Mauri, G. (2009). Solving PSPACE-complete Problems by Polarizationless Recognizer P Systems with Strong Division and Dissolution. In C. Batini (a cura di), Report n. 2009-02 (numero monografico) (pp. 93-98). Starrylink Editrice.
Solving PSPACE-complete Problems by Polarizationless Recognizer P Systems with Strong Division and Dissolution
LEPORATI, ALBERTO OTTAVIO;ZANDRON, CLAUDIO;FERRETTI, CLAUDIO;MAURI, GIANCARLO
2009
Abstract
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.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
