Minimal Cooperation in P Systems with Symport/Antiport: A Complexity Approach

Description

Membrane systems with symport/antiport rules compute by just moving objects among membranes, and not by changing the objects themselves. In these systems the environment plays an active role because, not only it receives objects from the system, but it also sends objects into the system. Actually, in this framework it is commonly assumed that an arbitrarily large number of copies of some objects are initially available in the environment. This special feature has been widely exploited for the design of e cient solutions to computationally hard problems in the framework of tissue like P systems able to create an exponential workspace in polynomial time (e.g. via cell division or cell separation rules). This paper deals with cell-like P systems which use symport/antiport rules as communication rules, and the role played by the minimal cooperation is studied from a computational complexity point of view. Speci cally, the limitations on the e ciency of P systems with membrane separation whose symport/antiport rules involve at most two objects are established. In addition, a polynomial time solution to HAM-CYCLE problem, a well known NP-complete problem, by using a family of such kind of P systems with membrane division, is provided. Therefore, in the framework of cell-like P systems with minimal cooperation in communication rules, passing from membrane separation to membrane division amounts to passing from tractability to NP{hardness.

Abstract

Ministerio de Economía y Competitividad TIN2012-37434

Additional details