Many variants of P systems with active membranes are able to solve traditionally intractable problems. Sometimes they also characterize well known complexity classes, depending upon the computational features they use. In this paper we continue the investigation of the importance of (minimal) cooperative rules to increase the computational power of P systems. In particular, we prove that monodirectional shallow chargeless P systems with active membranes and minimal cooperation working in polynomial time precisely characterise P∥^#P , the complexity class of problems solved in polynomial time by deterministic Turing machines with a polynomial number of parallel queries to an oracle for a counting problem.

Leporati, A., Manzoni, L., Mauri, G., Porreca, A., & Zandron, C. (2020). Simulating counting oracles with cooperation. JOURNAL OF MEMBRANE COMPUTING, 2(4), 303-310 [10.1007/s41965-020-00052-0].

Simulating counting oracles with cooperation

Leporati, Alberto;Manzoni, Luca;Mauri, Giancarlo;Porreca, Antonio E.;Zandron, Claudio
2020

Abstract

Many variants of P systems with active membranes are able to solve traditionally intractable problems. Sometimes they also characterize well known complexity classes, depending upon the computational features they use. In this paper we continue the investigation of the importance of (minimal) cooperative rules to increase the computational power of P systems. In particular, we prove that monodirectional shallow chargeless P systems with active membranes and minimal cooperation working in polynomial time precisely characterise P∥^#P , the complexity class of problems solved in polynomial time by deterministic Turing machines with a polynomial number of parallel queries to an oracle for a counting problem.
Articolo in rivista - Articolo scientifico
Scientifica
P systems with active membranes; Counting oracles; Minimal cooperation; Monodirectional P systems; Chargeless P systems;
English
Leporati, A., Manzoni, L., Mauri, G., Porreca, A., & Zandron, C. (2020). Simulating counting oracles with cooperation. JOURNAL OF MEMBRANE COMPUTING, 2(4), 303-310 [10.1007/s41965-020-00052-0].
Leporati, A; Manzoni, L; Mauri, G; Porreca, A; Zandron, C
File in questo prodotto:
Non ci sono file associati a questo prodotto.

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: http://hdl.handle.net/10281/300660
Citazioni
  • Scopus 2
  • ???jsp.display-item.citation.isi??? 2
Social impact