Membrane Division, Oracles, and the Counting Hierarchy

作者：Leporati Alberto; Manzoni Luca; Mauri Giancarlo; Porreca Antonio E^*; Zandron Claudio

来源：Fundamenta Informaticae, 2015, 138(1-2): 97-111.

DOI：10.3233/FI-2015-1201

• Membrane computing
• counting complexity
• oracles

Polynomial-time P systems with active membranes characterise PSPACE by exploiting membranes nested to a polynomial depth, which may be subject to membrane division rules. When only elementary (leaf) membrane division rules are allowed, the computing power decreases to P-PP = P-#P, the class of problems solvable in polynomial time by deterministic Turing machines equipped with oracles for counting (or majority) problems. In this paper we investigate a variant of intermediate power, limiting membrane nesting (hence membrane division) to constant depth, and we prove that the resulting P systems can solve all problems in the counting hierarchy CH, which is located between P-PP and PSPACE. In particular, for each integer k >= 0 we provide a lower bound to the computing power of P systems of depth k.

• 出版日期2015