期刊
THEORETICAL COMPUTER SCIENCE
卷 777, 期 -, 页码 443-453出版社
ELSEVIER SCIENCE BV
DOI: 10.1016/j.tcs.2018.12.024
关键词
Membrane computing; P system with symport/antiport; Membrane division; Computational complexity
资金
- Ministerio de Economia, Industria y Competitividad (MINECO) of Spain, through the Agencia Estatal de Investigacion (AEI) [TIN2017-89842-P]
- Fondo Europeo de Desarrollo Regional (FEDER) of the European Union
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据