Ponencia
Simulating counting oracles with cooperation
Autor/es | Leporati, Alberto
Manzoni, Luca Mauri, Giancarlo Porreca, Antonio E. Zandron, Claudio |
Coordinador/Director | Research Group on Natural Computing |
Fecha de publicación | 2019 |
Fecha de depósito | 2019-11-21 |
Publicado en |
|
Resumen | 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. |
Cita | 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. |
Ficheros | Tamaño | Formato | Ver | Descripción |
---|---|---|---|---|
109_CountingOracles.pdf | 390.5Kb | [PDF] | Ver/ | |