2019
P systems attacking hard problems beyond NP: a survey
SOSÍK, PetrBasic information
Original name
P systems attacking hard problems beyond NP: a survey
Authors
Edition
Journal of Membrane Computing, Singapore, Springer Singapore, 2019, 2523-8906
Other information
Language
English
Type of outcome
Article in a journal
Field of Study
10200 1.2 Computer and information sciences
Country of publisher
Singapore
Confidentiality degree
is not subject to a state or trade secret
References:
Marked to be transferred to RIV
Yes
RIV identification code
RIV/47813059:19240/19:A0000495
Organization unit
Faculty of Philosophy and Science in Opava
UT WoS
EID Scopus
Keywords in English
P system; Membrane computing; Computational complexity; NP; PP; PSPACE
Tags
International impact, Reviewed
Links
LQ1602, research and development project.
Changed: 22/3/2022 11:27, Mgr. Kamil Matula, Ph.D.
Abstract
In the original language
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.