On The Semantics of Annihilation Rules in Membrane Computing

Abstract

It is well known that polarizationless recognizer P systems with active membranes, without dissolution, with division of elementary and non-elementary membranes, with antimatter and matter/antimatter annihilation rules can solve all problems in NP when the annihilation rules have (weak) priority over all the other rules. Until now, it was an open problem whether these systems can still solve all NP problems if the priority of the matter/antimatter annihilation rules is removed. In this paper we provide a negative answer to this question: we prove that the class of problems solvable by this model of P systems without priority of the matter/antimatter annihilation rules is exactly P. To the best of our knowledge, this is the rst paper in the literature of P systems where the semantics of applying the rules constitutes a frontier of tractability.