Complexity Perspectives on Minimal Cooperation in Cell-like Membrane Systems

Abstract

Cooperation is doubtless a critical ingredient of a computing model. This paper provides an overview on results showing how forbidding cooperation, or allowing it only a minimum degree, influences the computing power. In particular, we restrict ourselves to two types of cell-like membrane systems. On one hand, we analyze the efficiency of polarizationless P systems with active membranes without dissolution rules when minimal cooperation is permitted in object evolution rules. On the other hand, cell-like P systems with symport/antiport rules of minimal length are also addressed. Specifically, assuming that P is not equal to NP, several frontiers of the efficiency are obtained in these two frameworks