期刊
JOURNAL OF MEMBRANE COMPUTING
卷 1, 期 3, 页码 198-208出版社
SPRINGERNATURE
DOI: 10.1007/s41965-019-00017-y
关键词
P system; Membrane computing; Computational complexity; NP; PP; PSPACE
资金
- Ministry of Education, Youth and Sports Of the Czech Republic from the National Programme of Sustainability (NPU II) project IT4Innovations Excellence in Science [LQ1602]
- Silesian University in Opava under the Student Funding Scheme [SGS/11/2019]
In the field of membrane computing, a great attention is traditionally paid to the results demonstrating a theoretical possibility to solve NP-complete problems in polynomial time by means of various models of P systems. A bit less common is the fact that almost all models of P systems with this capability are actually stronger: some of them are able to solve PSPACE-complete problems in polynomial time, while others have been recently shown to characterize the class P-#P (which is conjectured to be strictly included in PSPACE). A large part of these results has appeared quite recently. In this survey, we focus on strong models of membrane systems which have the potential to solve hard problems belonging to classes containing NP. These include P systems with active membranes, P systems with proteins on membranes and tissue P systems, as well as P systems with symport/antiport and membrane division and, finally, spiking neural P systems. We provide a survey of computational complexity results of these membrane models, pointing out some features providing them with their computational strength. We also mention a sequence of open problems related to these topics.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据