2019
P systems attacking hard problems beyond NP: a survey
SOSÍK, PetrZákladní údaje
Originální název
P systems attacking hard problems beyond NP: a survey
Autoři
Vydání
Journal of Membrane Computing, Singapore, Springer Singapore, 2019, 2523-8906
Další údaje
Jazyk
angličtina
Typ výsledku
Článek v odborném periodiku
Obor
10200 1.2 Computer and information sciences
Stát vydavatele
Singapur
Utajení
není předmětem státního či obchodního tajemství
Odkazy
Označené pro přenos do RIV
Ano
Kód RIV
RIV/47813059:19240/19:A0000495
Organizační jednotka
Filozoficko-přírodovědecká fakulta v Opavě
UT WoS
EID Scopus
Klíčová slova anglicky
P system; Membrane computing; Computational complexity; NP; PP; PSPACE
Příznaky
Mezinárodní význam, Recenzováno
Návaznosti
LQ1602, projekt VaV.
Změněno: 22. 3. 2022 11:27, Mgr. Kamil Matula, Ph.D.
Anotace
V originále
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.