Among the computational features that determine the computing power of polarizationless P systems with active membranes, the depth of the membrane hierarchy is one of the least explored. It is known that this model of P systems can solve PSPACE-complete problems when no constraints are given on the depth of the membrane hierarchy, whereas the complexity class P-parallel to(#P) is characterized by monodirectional shallow P systems with minimal cooperation, whose depth is 1. No similar result is currently known for polarizationless systems without cooperation or other additional features. In this paper we show that these P systems, using a membrane hierarchy of depth 2, are able to solve at least all decision problems that are in the complexity class P-parallel to(NP) , the class of problems solved in polynomial time by deterministic Turing machines that are given the possibility to make a polynomial number of parallel queries to oracles for NP problems. (C) 2021 Elsevier B.V. All rights reserved.

Depth-two P systems can simulate Turing machines with NP oracles

Manzoni, L;
2022

Abstract

Among the computational features that determine the computing power of polarizationless P systems with active membranes, the depth of the membrane hierarchy is one of the least explored. It is known that this model of P systems can solve PSPACE-complete problems when no constraints are given on the depth of the membrane hierarchy, whereas the complexity class P-parallel to(#P) is characterized by monodirectional shallow P systems with minimal cooperation, whose depth is 1. No similar result is currently known for polarizationless systems without cooperation or other additional features. In this paper we show that these P systems, using a membrane hierarchy of depth 2, are able to solve at least all decision problems that are in the complexity class P-parallel to(NP) , the class of problems solved in polynomial time by deterministic Turing machines that are given the possibility to make a polynomial number of parallel queries to oracles for NP problems. (C) 2021 Elsevier B.V. All rights reserved.
https://www.sciencedirect.com/science/article/pii/S030439752100671X
File in questo prodotto:
File Dimensione Formato  
1-s2.0-S030439752100671X-main.pdf

non disponibili

Tipologia: Documento in Versione Editoriale
Licenza: Copyright Editore
Dimensione 445.86 kB
Formato Adobe PDF
445.86 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11368/3029201
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 1
social impact