Affiliations: Research Group on Computational Topology and Applied Mathematics, Department of Applied Mathematics - University of Sevilla, 41012, Spain. [email protected] | Research Group on Natural Computing, Department of Computer Science and Artificial Intelligence, University of Sevilla, 41012, Spain. [email protected] | Institute of Mathematics and Computer Science, Academy of Sciences of Moldova, Academiei 5, Chişinău, MD-2028, Republic of Moldova. [email protected] | Faculty of Informatics, Vienna University of Technology, Favoritenstr. 9, 1040 Vienna, Austria. [email protected] | Research Group on Natural Computing, Department of Computer Science and Artificial Intelligence, University of Sevilla, Avda. Reina Mercedes s/n, 41012 Sevilla, Spain. [email protected]
Note: [] Address for correspondence: Research Group on Computational Topology and Applied Mathematics, Department of Applied Mathematics - University of Sevilla, 41012, Spain.
Note: [] A. Alhazov acknowledges project STCU-5384 awarded by the Science and Technology Center in Ukraine.
Note: [] M. A. Gutiérrez-Naranjo acknowledges the support of the project TIN2012-37434 of the Ministerio de Economía y Competitividad of Spain.
Abstract: It is well known that the polynomial complexity class of recognizer P systems with active membranes without polarizations, without dissolution and with division for elementary and non-elementary membranes is exactly the complexity class P (see [9], Theorem 2). In this paper, we prove that if such a P systems model is endowed with antimatter and annihilation rules, then NP problems can be solved, even without non-elementary membrane division. In this way, antimatter is shown to be a frontier of tractability in Membrane Computing.
