Polarizationless P Systems with Active Membranes: Computational Complexity Aspects

Abstract

P systems with active membranes, in their classical definition, make use of noncooperative rules only. However, it is well known that in living cells, proteins interact among them yielding new products. Inspired by this biological phenomenon, the previous framework is reformulated in this paper, allowing cooperation in object evolution rules, while removing electrical charges associated with membranes. More precisely, minimal cooperation in object evolution rules is incorporated in polarizationless P systems with active membranes. In this paper, the term “minimal” means that the left-hand side of such rules consists of at most two symbols, and its length is greater than or equal to the corresponding right-hand side. The computational efficiency of this kind of P systems is studied by providing a uniform polynomial-time solution to SAT problem in such manner that only division rules for elementary membranes are used and dissolution rules are forbidden. Bearing in mind that only tractable problems can be efficiently solved by families of polarizationless P systems with active membranes and without dissolution rules, passing from non-cooperation to minimal cooperation in object evolution rules amounts passing from non-efficiency to efficiency in this framework. This frontier of efficiency provides, as any other borderline does, a possible way to address the P versus NP problem.