Membrane Division, Oracles, and the Counting Hierarchy

• Autorzy: Leporati A. , Manzoni L. , Mauri G. , Porreca A. E. , Zandron C.

Identyfikatory

DOI

10.3233/FI-2015-1201

• Języki publikacji: EN

Abstrakty

EN

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 Turingmachines 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 PPP and PSPACE. In particular, for each integer k ≥ 0 we provide a lower bound to the computing power of P systems of depth k.

Słowa kluczowe

EN

membrane computing; counting complexity; oracles

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2015
• Tom: Vol. 138, nr 1/2
• Strony: 97--111
• Opis fizyczny: Biblioiogr. 11 poz.

Twórcy

autor

Leporati A.

• Dipartimento di Informatica, Sistemistica e Comunicazione Universit`a degli Studi di Milano-Bicocca Viale Sarca 336/14, 20126 Milano, Italy

autor

Manzoni L.

• Dipartimento di Informatica, Sistemistica e Comunicazione Universit`a degli Studi di Milano-Bicocca Viale Sarca 336/14, 20126 Milano, Italy

autor

Mauri G.

• Dipartimento di Informatica, Sistemistica e Comunicazione Universit`a degli Studi di Milano-Bicocca Viale Sarca 336/14, 20126 Milano, Italy

autor

Porreca A. E.

• Dipartimento di Informatica, Sistemistica e Comunicazione Universit`a degli Studi di Milano-Bicocca Viale Sarca 336/14, 20126 Milano, Italy

autor

Zandron C.

• Dipartimento di Informatica, Sistemistica e Comunicazione Universit`a degli Studi di Milano-Bicocca Viale Sarca 336/14, 20126 Milano, Italy

Bibliografia

• [1] Alhazov, A., Martín-Vide, C., Pan, L.: Solving a PSPACE-complete problem by recognizing P systems with restricted active membranes, Fundamenta Informaticae, 58(2), 2003, 67–77.
• [2] Hemaspaandra, L. A., Ogihara, M.: The Complexity Theory Companion, Texts in Theoretical Computer Science, Springer, 2002.
• [3] Leporati, A., Manzoni, L., Mauri, G., Porreca, A. E., Zandron, C.: Simulating elementary active membranes, with an application to the P conjecture, in: 15th International Conference on Membrane Computing, Proceedings (M. Gheorghe, P. Sosík, ˇS. Vavrečková, Eds.), 2014, 251–266.
• [4] Murphy, N., Woods, D.: The computational power of membrane systems under tight uniformity conditions, Natural Computing, 10(1), 2011, 613–632.
• [5] Păun, Gh.: P systems with active membranes: Attacking NP-complete problems, Journal of Automata, Languages and Combinatorics, 6(1), 2001, 75–90.
• [6] Pérez-Jiménez, M. J., Romero-Jiménez, A., Sancho-Caparrini, F.: Complexity classes in models of cellular computing with membranes, Natural Computing, 2(3), 2003, 265–284.
• [7] Porreca, A. E., Leporati, A., Mauri, G., Zandron, C.: P systems simulating oracle computations, in: Membrane Computing, 12th International Conference, CMC 2011 (M. Gheorghe, Gh. P˘aun, A. Salomaa, G. Rozenberg, S. Verlan, Eds.), vol. 7184 of Lecture Notes in Computer Science, Springer, 2012, 346–358.
• [8] Porreca, A. E., Murphy, N.: First steps towards linking membrane depth and the Polynomial Hierarchy, in: Eight BrainstormingWeek on Membrane Computing (M. A.Martínez-del-Amor,Gh. Păun, I. Pérez-Hurtado, A. Riscos-Nuňez, Eds.), number 1/2010 in RGNC Reports, Fénix Editora, 2010, 255–266.
• [9] Sosík, P., Rodríguez-Patón,A.: Membrane computing and complexity theory: A characterization of PSPACE, Journal of Computer and System Sciences, 73(1), 2007, 137–152.
• [10] Zandron, C., Ferretti, C., Mauri, G.: Solving NP-complete problems using P systems with active membranes, in: Unconventional Models of Computation, UMC’2K, Proceedings of the Second International Conference (I. Antoniou, C. S. Calude, M. J. Dinneen, Eds.), Springer, 2001, 289–301.
• [11] Zandron, C., Leporati, A., Ferretti, C., Mauri, G., Pérez-Jiménez, M. J.: On the computational efficiency of polarizationless recognizer P systems with strong division and dissolution, Fundamenta Informaticae, 87, 2008, 79–91.