P systems simulating oracle computations

DOI10.1007/978-3-642-28024-5_23MaRDI QIDQ2890301zbMATH OpenOpenAlexDBLPWikidataFDO

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

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)

Recommendations

• Simulating counting oracles with cooperation
• Tissue P systems can be simulated efficiently with counting oracles
• P Systems with Elementary Active Membranes: Beyond NP and coNP
• Membrane division, oracles, and the counting hierarchy
• Simulating elementary active membranes

Cites work

• scientific article; zbMATH DE number 1583885 (Why is no real title available?)
• scientific article; zbMATH DE number 2118901 (Why is no real title available?)
• An efficient simulation of polynomial-space Turing machines by P systems with active membranes
• Complexity classes in models of cellular computing with membranes
• Membrane computing and complexity theory: A characterization of PSPACE
• P systems with active membranes: Attacking NP-complete problems
• PP is as Hard as the Polynomial-Time Hierarchy
• The computational power of cell division in P systems: Beating down parallel computers?
• The computational power of membrane systems under tight uniformity conditions

Cited in

(11)

• Bounding the space in P systems with active membranes
• Simulating counting oracles with cooperation
• P systems attacking hard problems beyond NP: a survey
• Subroutines in P systems and closure properties of their complexity classes
• Simulating R Systems by P Systems
• Seeking computational efficiency boundaries: the Păun's conjecture
• Space complexity equivalence of P systems with active membranes and Turing machines
• Membrane division, oracles, and the counting hierarchy
• A limitation of cell division in tissue P systems by PSPACE
• When object production tunes the efficiency of membrane systems
• Tissue P systems can be simulated efficiently with counting oracles

This page was built for publication: P systems simulating oracle computations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2890301)