P systems attacking hard problems beyond NP: a survey

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F47813059%3A19240%2F19%3AA0000495" target="_blank" >RIV/47813059:19240/19:A0000495 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.1007/s41965-019-00017-y" target="_blank" >https://doi.org/10.1007/s41965-019-00017-y</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/s41965-019-00017-y" target="_blank" >10.1007/s41965-019-00017-y</a>

Jazyk výsledku

angličtina

Název v původním jazyce

P systems attacking hard problems beyond NP: a survey

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

P systems attacking hard problems beyond NP: a survey

Popis výsledku anglicky

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.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10200 - Computer and information sciences

Projekt

<a href="/cs/project/LQ1602" target="_blank" >LQ1602: IT4Innovations excellence in science</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>S - Specificky vyzkum na vysokych skolach

Rok uplatnění

2019

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Journal of Membrane Computing

ISSN

2523-8906

e-ISSN

—

Svazek periodika

1

Číslo periodika v rámci svazku

2

Stát vydavatele periodika

SG - Singapurská republika

Počet stran výsledku

11

Strana od-do

198-208

Kód UT WoS článku

000651468300004

EID výsledku v databázi Scopus

2-s2.0-85081198009