Presentation
Simulating counting oracles with cooperation
Author/s | Leporati, Alberto
Manzoni, Luca Mauri, Giancarlo Porreca, Antonio E. Zandron, Claudio |
Editor | Research Group on Natural Computing |
Publication Date | 2019 |
Deposit Date | 2019-11-21 |
Published in |
|
Abstract | 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 ... 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. |
Citation | Leporati, A., Manzoni, L., Mauri, G., Porreca, A.E. y Zandron, C. (2019). Simulating counting oracles with cooperation. En BWMC 2019: Seventeenth Brainstorming Week on Membrane Computing (109-116), Sevilla, España: Escuela Técnica Superior de Ingeniería Informática, Universidad de Sevilla. |
Files | Size | Format | View | Description |
---|---|---|---|---|
109_CountingOracles.pdf | 390.5Kb | [PDF] | View/ | |