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 [Formula presented]-complete problems when no constraints are given on the depth of the membrane hierarchy, whereas the complexity class P∥#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 [Formula presented], 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 [Formula presented] problems.

Leporati, A., Manzoni, L., Mauri, G., Zandron, C. (2022). Depth-two P systems can simulate Turing machines with NP oracles. THEORETICAL COMPUTER SCIENCE, 908(24 March 2022), 43-55 [10.1016/j.tcs.2021.11.010].

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

Leporati, A
;
Manzoni, L;Mauri, G;Zandron, C
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 [Formula presented]-complete problems when no constraints are given on the depth of the membrane hierarchy, whereas the complexity class P∥#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 [Formula presented], 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 [Formula presented] problems.
Articolo in rivista - Articolo scientifico
Active membranes; NP oracles; P systems;
English
20-nov-2021
2022
908
24 March 2022
43
55
reserved
Leporati, A., Manzoni, L., Mauri, G., Zandron, C. (2022). Depth-two P systems can simulate Turing machines with NP oracles. THEORETICAL COMPUTER SCIENCE, 908(24 March 2022), 43-55 [10.1016/j.tcs.2021.11.010].
File in questo prodotto:
File Dimensione Formato  
Leporati-2022-TCS-VoR.pdf

Solo gestori archivio

Tipologia di allegato: Publisher’s Version (Version of Record, VoR)
Licenza: Tutti i diritti riservati
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/10281/341231
Citazioni
  • Scopus 2
  • ???jsp.display-item.citation.isi??? 2
Social impact