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