J 2019

P systems attacking hard problems beyond NP: a survey

SOSÍK, Petr

Základní údaje

Originální název

P systems attacking hard problems beyond NP: a survey

Autoři

SOSÍK, Petr

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

URL

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ě

DOI

https://doi.org/10.1007/s41965-019-00017-y

UT WoS

000651468300004

EID Scopus

2-s2.0-85081198009

Klíčová slova anglicky

P system; Membrane computing; Computational complexity; NP; PP; PSPACE

Štítky

SGS112019, ÚI

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.
Zobrazeno: 18. 11. 2026 15:59