A path to computational efficiency through membrane computing

Abstract

The search for new mechanisms and tools allowing us to tackle the famousPversusNPproblem from new perspectives is an important task, due to the relevance of that problem.The concept of efficiency of computing models is associated with the ability to solveintractable (in a classical sense) problems in polynomial time. Assuming that P =NP, that concept is equivalent to the capability to solveNP-complete problems in an efficient way.Different frontiers of the efficiency have been given in Membrane Computing in terms ofsyntactical or semantic ingredients of the models. In particular, in the framework of tissueP systems with cell division using symport/antiport rules, the length of communicationrules (passing from length 1 to length 2) provides an optimal borderline of the efficiency. Cell-like P systems with symport/antiport rules and membrane division is a restrictedvariant of such tissue P systems in both its structure (rooted tree versus undirected graph)and in the way membranes communicate with each other and with the environment. Thelimitations of efficient computations in such kind of P systems which use non-cooperativecommunication rules have been previously established. In this paper, a uniform polynomialtime solution for the Hamiltonian cycle problem, a well knownNP-complete problem,by means of cell-like P systems with membrane division using minimal cooperation incommunication rules (at most two objects are involved), is provided. Hence, a new optimalboundary between tractability andNP-hardness, is provided: passing from non-cooperativerules to cooperative rules in cell-like P systems with symport/antiport rules and membranedivision amounts to passing from non-efficiency to efficiency.