Logo del repository
  1. Home
 
Opzioni

Simulating counting oracles with cooperation

Leporati A.
•
Manzoni L.
•
Mauri G.
altro
Zandron C.
2020
  • journal article

Periodico
JOURNAL OF MEMBRANE COMPUTING
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.
DOI
10.1007/s41965-020-00052-0
WOS
WOS:000672021400008
Archivio
http://hdl.handle.net/11368/2994644
info:eu-repo/semantics/altIdentifier/scopus/2-s2.0-85106624291
https://link.springer.com/article/10.1007/s41965-020-00052-0
Diritti
closed access
license:copyright editore
FVG url
https://arts.units.it/request-item?handle=11368/2994644
Soggetti
  • Chargeless P system

  • Counting oracle

  • Minimal cooperation

  • Monodirectional P sys...

  • P systems with active...

Scopus© citazioni
2
Data di acquisizione
Jun 14, 2022
Vedi dettagli
Web of Science© citazioni
3
Data di acquisizione
Mar 23, 2024
google-scholar
Get Involved!
  • Source Code
  • Documentation
  • Slack Channel
Make it your own

DSpace-CRIS can be extensively configured to meet your needs. Decide which information need to be collected and available with fine-grained security. Start updating the theme to match your nstitution's web identity.

Need professional help?

The original creators of DSpace-CRIS at 4Science can take your project to the next level, get in touch!

Realizzato con Software DSpace-CRIS - Estensione mantenuta e ottimizzata da 4Science

  • Impostazioni dei cookie
  • Informativa sulla privacy
  • Accordo con l'utente finale
  • Invia il tuo Feedback