Affiliations: Dipartimento di Informatica, Sistemistica e
Comunicazione, Università degli Studi di Milano – Bicocca, Viale
Sarca 336/14, 20126 Milano, Italy.
{zandron,leporati,ferretti,mauri}@disco.unimib.it | 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: Dipartimento di Informatica,
Sistemistica e Comunicazione, Università degli Studi di Milano –
Bicocca, Viale Sarca 336/14, 20126 Milano, Italy
Abstract: Recognizer P systems with active membranes have proven to be very
efficient computing devices, being able to solve NP-complete decision problems
in a polynomial time. However such solutions usually exploit many powerful
features, such as electrical charges (polarizations) associated to membranes,
evolution rules, communication rules, and strong or weak forms of division
rules. In this paper we contribute to the study of the computational power of
polarizationless recognizer P systems with active membranes. Precisely, we show
that such systems are able to solve in polynomial time the NP-complete decision
problem 3-SAT by using only dissolution rules and a form of strong division for
non-elementary membranes, working in the maximallly parallel way.
Keywords: P systems with active membranes, membrane division, membrane dissolution, NP-complete problems, 3-SAT
