A path to computational efficiency through membrane computing

摘要

The search for new mechanisms and tools allowing us to tackle the famous P versus NP problem 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 solve intractable (in a classical sense) problems in polynomial time. Assuming that P NP, that concept is equivalent to the capability to solve NP-complete problems in an efficient way. Different frontiers of the efficiency have been given in Membrane Computing in terms of syntactical or semantic ingredients of the models. In particular, in the framework of tissue P systems with cell division using symport/antiport rules, the length of communication rules (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 restricted variant 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. The limitations of efficient computations in such kind of P systems which use non-cooperative communication rules have been previously established. In this paper, a uniform polynomial time solution for the Hamiltonian cycle problem, a well known NP-complete problem, by means of cell-like P systems with membrane division using minimal cooperation in communication rules (at most two objects are involved), is provided. Hence, a new optimal boundary between tractability and NP-hardness, is provided: passing from non-cooperative rules to cooperative rules in cell-like P systems with symport/antiport rules and membrane division amounts to passing from non-efficiency to efficiency. (C) 2019 Elsevier B.V. All rights reserved.