We give a characterisation of the class of problems solved in polynomial time by uniform and semi-uniform families of P systems with active membranes, using matter/antimatter annihilation rules and elementary membrane division. Like several other variants of P systems with elementary division, this class is exactly P^#P, that is, the problems solvable efficiently with access to oracles for counting problems. We also consider the monodirectional case, where objects in the P system can only move from inner regions towards outer regions. In that case, the above model of P systems characterises the class P_∥^#P, where each query is independent of the result of the others; this contrasts with traditional P systems with active membranes, which characterise the (conjecturally proper) subclass P_∥^NP.

The counting power of P systems with antimatter

Manzoni Luca;
2017-01-01

Abstract

We give a characterisation of the class of problems solved in polynomial time by uniform and semi-uniform families of P systems with active membranes, using matter/antimatter annihilation rules and elementary membrane division. Like several other variants of P systems with elementary division, this class is exactly P^#P, that is, the problems solvable efficiently with access to oracles for counting problems. We also consider the monodirectional case, where objects in the P system can only move from inner regions towards outer regions. In that case, the above model of P systems characterises the class P_∥^#P, where each query is independent of the result of the others; this contrasts with traditional P systems with active membranes, which characterise the (conjecturally proper) subclass P_∥^NP.
2017
Pubblicato
https://www.sciencedirect.com/science/article/pii/S0304397517302840
File in questo prodotto:
File Dimensione Formato  
1-s2.0-S0304397517302840-main.pdf

Accesso chiuso

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

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/2947798
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 12
  • ???jsp.display-item.citation.isi??? 9
social impact