Membrane Division, Oracles, and the Counting Hierarchy

DOI10.3233/FI-2015-1201zbMath1357.68064MaRDI QIDQ2805449

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

Publication date: 11 May 2016

Published in: Fundamenta Informaticae (Search for Journal in Brave)

zbMATH Keywords

membrane computingcounting complexityoracles

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (19)

The computational power of tissue-like P systems with promoters ⋮ Characterising the complexity of tissue P systems with fission rules ⋮ The counting power of P systems with antimatter ⋮ Active P-colonies ⋮ Evaluating space measures in P systems ⋮ Shallow Non-confluent P Systems ⋮ The computational complexity of tissue P systems with evolutional symport/antiport rules ⋮ A Turing machine simulation by P systems without charges ⋮ Bounding the space in P systems with active membranes ⋮ Simulating counting oracles with cooperation ⋮ The computational power of cell-like P systems with one protein on membrane ⋮ Alternative space definitions for P systems with active membranes ⋮ A toolbox for simpler active membrane algorithms ⋮ Subroutines in P systems and closure properties of their complexity classes ⋮ Characterizing PSPACE with shallow non-confluent P systems ⋮ P systems attacking hard problems beyond NP: a survey ⋮ Monodirectional tissue P systems with channel states ⋮ Monodirectional P systems ⋮ Depth-two P systems can simulate Turing machines with \textbf{NP} oracles

This page was built for publication: Membrane Division, Oracles, and the Counting Hierarchy