Research Group on Natural Computing

In the framework of cell–like membrane systems it is well known that the
construction of exponential number of objects in polynomial time is not enough to ef-
ficiently solve NP–complete problems. Nonetheless, it may be sufficient to create an
exponential number of membranes in polynomial time. In the framework of recognizer
polarizationless P systems with active membranes, the construction of an exponential
workspace expressed in terms of number of membranes and objects may not suffice to
efficiently solve computationally hard problems.
In this paper we study the computational efficiency of recognizer tissue P systems
with communication (symport/antiport) rules and division rules. Some results have been
already obtained in this direction: (a) using communication rules and forbidding division
rules, only tractable problems can be efficiently solved; (b) using communication rules
with length three and division rules, NP–complete problems can be efficiently solved. In
this paper we show that the allowed length of communication rules plays a relevant role
from the efficiency point of view of the systems.