P Systems Simulating Oracle Computations

DOI10.1007/978-3-642-28024-5_23zbMath1350.68113OpenAlexW2250133772WikidataQ57518475 ScholiaQ57518475MaRDI QIDQ2890301

Claudio Zandron, Giancarlo Mauri, Antonio E. Porreca, Alberto Leporati

Publication date: 8 June 2012

Published in: Membrane Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-28024-5_23

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Space complexity equivalence of P systems with active membranes and Turing machines ⋮ A limitation of cell division in tissue P systems by PSPACE ⋮ Bounding the space in P systems with active membranes ⋮ Seeking computational efficiency boundaries: the Păun's conjecture ⋮ Subroutines in P systems and closure properties of their complexity classes ⋮ When object production tunes the efficiency of membrane systems ⋮ P systems attacking hard problems beyond NP: a survey

Cites Work

• The computational power of membrane systems under tight uniformity conditions
• Membrane computing and complexity theory: A characterization of PSPACE
• Complexity classes in models of cellular computing with membranes
• The computational power of cell division in P systems: Beating down parallel computers?
• PP is as Hard as the Polynomial-Time Hierarchy
• An Efficient Simulation of Polynomial-Space Turing Machines by P Systems with Active Membranes
• Unnamed Item
• Unnamed Item
• Unnamed Item