期刊
JOURNAL OF MEMBRANE COMPUTING
卷 1, 期 2, 页码 85-92出版社
SPRINGERNATURE
DOI: 10.1007/s41965-018-00004-9
关键词
Minimal cooperation; Cell-like P systems; Computational complexity theory
资金
- 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
- National Natural Science Foundation of China [61320106005]
Cooperation is doubtless a relevant ingredient on rewriting rules based computing models. This paper provides an overview on both classical and newest results studying how cooperation among objects influences the ability of cell-like membrane systems to solve computationally hard problems in an efficient way. In this paper, two types of such membrane systems will be considered: (a) polarizationless P systems with active membranes without dissolution rules when minimal cooperation is permitted in object evolution rules; and (b) cell-like P systems with symport/antiport rules of minimal length. Specifically, assuming that P is not equal to NP, several frontiers of the efficiency are obtained in these two computing frameworks, in such manner that each borderline provides a tool to tackle the P versus NP problem.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据