Limits on Efficient Computation in P Systems with Symport/Antiport Rules

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 with 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 rules and membrane division rules or membrane separation rules. Specifically, we study the limitations of such P systems when the only communication rules allowed have length 1.Ministerio de Ciencia e Innovación TIN2012-3743