On Efficiency of P Systems with Symport/Antiport and Membrane Division

Abstract

Classical membrane systems with symport/antiport rules observe the con- servation law, in the sense that they compute by changing the places of objects with respect to the membranes, and not by changing the objects themselves. In these systems the environment plays an active role because the systems not only send objects to the environment, but also bring objects from the environment. In the initial configuration of a system, there is a special alphabet whose elements appear in an arbitrary large number of copies. The ability of these computing devices to have infinite copies of some objects has been widely exploited in the design of efficient solutions to computationally hard problems. This paper deals with computational aspects of P systems with symport/antiport and membrane division rules where there is not an environment having the property mentioned above. Specifically, we establish the relationships between the polynomial complexity class associated with P systems with symport/antiport, membrane division rules, and with or without environment. As a consequence, we prove that the role of the environment is irrelevant in order to solve NP–complete problems in an efficient way.