P systems attacking hard problems beyond NP: a survey

Result code in 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>

Result on the web

<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>

Result language

angličtina

Original language name

P systems attacking hard problems beyond NP: a survey

Original language description

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.

Czech name

—

Czech description

—

Type

J_imp - Article in a specialist periodical, which is included in the Web of Science database

CEP classification

—

OECD FORD branch

10200 - Computer and information sciences

Project

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

Continuities

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

Publication year

2019

Confidentiality

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

Name of the periodical

Journal of Membrane Computing

ISSN

2523-8906

e-ISSN

—

Volume of the periodical

1

Issue of the periodical within the volume

2

Country of publishing house

SG - SINGAPORE

Number of pages

11

Pages from-to

198-208

UT code for WoS article

000651468300004

EID of the result in the Scopus database

2-s2.0-85081198009