Published November 21, 2019 | Version v1
Publication

Simulating counting oracles with cooperation

Description

We prove that monodirectional shallow chargeless P systems with active membranes and minimal cooperation working in polynomial time precisely characterise P#P k , 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.

Additional details

Identifiers

URL
https://idus.us.es/handle//11441/90400
URN
urn:oai:idus.us.es:11441/90400