J 2019

P systems attacking hard problems beyond NP: a survey

SOSÍK, Petr

Basic information

Original name

P systems attacking hard problems beyond NP: a survey

Authors

SOSÍK, Petr

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:

URL

Marked to be transferred to RIV

Yes

RIV identification code

RIV/47813059:19240/19:A0000495

Organization unit

Faculty of Philosophy and Science in Opava

DOI

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

UT WoS

000651468300004

EID Scopus

2-s2.0-85081198009

Keywords in English

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

Tags

SGS112019, ÚI

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.
Displayed: 18/11/2026 16:19