In the framework of P systems, it is known that the construction of exponential number of objects in polynomial time is not
enough to efficiently solve
NP-complete problems. Nonetheless, it could be sufficient to create an exponential number of membranes in polynomial time. Working
with P systems whose membrane structure does not increase in size, it is known that it is not possible to solve computationally
hard problems (unless
P =
NP), basically due to the impossibility of constructing exponential number of membranes, in polynomial time, using only evolution,
communication and dissolution rules. In this paper we show how a family of recognizer tissue P systems with symport/antiport
rules which solves a decision problem can be efficiently simulated by a family of basic recognizer P systems solving the same
problem. This simulation allows us to transfer the result about the limitations in computational power, from the model of
basic cell-like P systems to this kind of tissue-like P systems.
Keywords P systems - Tissue P systems - Recognizer P systems - Symport/antiport rules - Efficient simulation of cellular systems