Abstract
In this paper we present a theory of computational complexity in the framework of membrane computing. Polynomial complexity classes in recognizer membrane systems and capturing the classical deterministic and non-deterministic modes of computation, are introduced. In this context, a characterization of the relation P = NP is described.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Alhazov, A., Freund, R., Păun, G.: P systems with active membranes and two polarizations. In: Păun, G., Riscos, A., Romero, A., Sancho, F. (eds.) Proceedings of the Second Brainstorming Week on Membrane Computing, Report RGNC 01/04, pp. 20–35 (2004)
Alhazov, A., Ishdorj, T.-O.: Membrane operations in P systems with active membranes. In: Păun, G., Riscos, A., Romero, A., Sancho, F. (eds.) Proceedings of the Second Brainstorming Week on Membrane Computing, Report RGNC 01/04, pp. 37–52 (2004)
Alhazov, A., Martín–Vide, C., Pan, L.: Solving graph problems by P systems with restricted elementary active membranes. In: Jonoska, N., Păun, G., Rozenberg, G. (eds.) Aspects of Molecular Computing. LNCS, vol. 2950, pp. 1–22. Springer, Heidelberg (2003)
Alhazov, A., Pan, L., Păun, G.: Trading polarizations for labels in P systems with active membranes. Acta Informatica (to appear)
Castellanos, J., Păun, G., Rodríguez–Patón, A.: P systems with worm–objects. In: IEEE 7th International Conference on String Processing and Information Retrieval, SPIRE 2000, La Coruña, Spain, pp. 64–74 (2000)
Cordón–Franco, A., Gutiérrez–Naranjo, M.A., Pérez–Jiménez, M.J., Sancho–Caparrini, F.: Implementing in Prolog an effective cellular solution for the Knapsack problem. In: Martín-Vide, C., Mauri, G., Păun, G., Rozenberg, G., Salomaa, A. (eds.) WMC 2003. LNCS, vol. 2933, pp. 140–152. Springer, Heidelberg (2004)
Czeiler, E.: Self–activating P systems. In: Păun, G., Rozenberg, G., Salomaa, A., Zandron, C. (eds.) WMC 2002. LNCS, vol. 2597, pp. 234–246. Springer, Heidelberg (2003)
Garey, M.R., Johnson, D.S.: Computers and Intractability. A Guide to the Theory of NP-Completeness. W.H. Freeman and Company, New York (1979)
Gutiérrez–Naranjo, M.A., Pérez–Jiménez, M.J., Riscos–Núñez, A.: A fast P system for finding a balanced 2-partition. Soft Computing (in press)
Head, T., Yamamura, M., Gal, S.: Aqueous computing: writing on molecules. In: Proceedings of the Congress on Evolutionary Computation 1999, pp. 1006–1010. IEEE Service Center, Piscataway (1999)
Ito, M., Martín–Vide, C., Păun, G.: Characterization of Parikh sets of ET0L languages in terms of P systems. In: Ito, M., Păun, G., Yu, S. (eds.) Words, Semigroups, and Transducers, pp. 239–254. World Scientific, Singapore (2001)
Krishna, S.N., Rama, R.: A variant of P systems with active membranes: Solving NP–complete problems. Romanian Journal of Information Science and Technology 2(4), 357–367 (1999)
Krishna, S.N., Rama, R.: P systems with replicated rewriting. Journal of Automata, Languages and Combinatorics 6(1), 345–350 (2001)
Krishna, S.N., Rama, R.: Breaking DES using P systems. Theoretical Computer Science 299(1-3), 495–508 (2003)
Madhu, M., Kristhivasan, K.: P systems with membrane creation: Universality and efficiency. In: Margenstern, M., Rogozhin, Y. (eds.) MCU 2001. LNCS, vol. 2055, pp. 276–287. Springer, Heidelberg (2001)
Obtulowicz, A.: Deterministic P systems for solving SAT problem. Romanian Journal of Information Science and Technology 4(1–2), 551–558 (2001)
Obtułowicz, A.: On P Systems with Active Membranes Solving the Integer Factorization Problem in a Polynomial Time. In: Calude, C.S., Pun, G., Rozenberg, G., Salomaa, A. (eds.) Multiset Processing. LNCS, vol. 2235, pp. 267–285. Springer, Heidelberg (2001)
Obtulowicz, A.: Note on some recursively family of P systems with active membranes (2004) (Submitted)
Pan, L., Alhazov, A., Ishdorj, T.-O.: Further remarks on P systems with active membranes, separation, merging, and release rules. In: Păun, G., Riscos, A., Romero, A., Sancho, F. (eds.) Proceedings of the Second Brainstorming Week on Membrane Computing, Report RGNC 01/04, pp. 316–324 (2004)
Pan, L., Ishdorj, T.-O.: P systems with active membranes and separation rules. Journal of Universal Computer Science 10(5), 630–649 (2004)
Pan, L., Martín–Vide, C.: C. Solving multiset 0–1 knapsack problem by P systems with input and active membranes. In: Păun, G., Riscos, A., Romero, A., Sancho, F. (eds.) Proceedings of the Second Brainstorming Week on Membrane Computing, Report RGNC 01/04, pp. 342–353 (2004)
Păun, A.: On P systems with membrane division. In: Antoniou, I., Calude, C.S., Dinneen, M.J. (eds.) Unconventional Models of Computation, pp. 187–201. Springer, London (2000)
Păun, G.: Computing with membranes. Journal of Computer and System Sciences 61(1), 108–143 (2000); and Turku Center for Computer Science-TUCS Report Nr. 208 (1998)
Păun, G.: Computing with membranes: Attacking NP–complete problems. In: Antoniou, I., Calude, C.S., Dinneen, M.J. (eds.) Unconventional Models of Computation, pp. 94–115 (2000)
Păun, G.: P systems with active membranes: Attacking NP–complete problems. Journal of Automata, Languages and Combinatorics 6(1), 75–90 (2001)
Păun, G.: Membrane Computing. An Introduction. Springer, Berlin (2002)
Păun, G., Pérez–Jiménez, M.J., Riscos–Núñez, A.: P systems with tables of rules. In: Karhumäki, J., Maurer, H., Păun, G., Rozenberg, G. (eds.) Theory Is Forever. LNCS, vol. 3113, pp. 235–249. Springer, Heidelberg (2004)
Păun, G., Rozenberg, G.: A guide to membrane computing. Theoretical Computer Science 287, 73–100 (2002)
Păun, G., Suzuki, Y., Tanaka, H., Yokomori, T.: On the power of membrane division in P systems. Theoretical Computer Science 324(1), 61–85 (2004)
Pérez–Jiménez, M.J., Riscos–Núñez, A.: Solving the Subset-Sum problem by P systems with active membranes. New Generation Computing (in press)
Pérez–Jiménez, M.J., Riscos–Núñez, A.: A linear time solution to the Knapsack problem using active membranes. In: Martín-Vide, C., Mauri, G., Păun, G., Rozenberg, G., Salomaa, A. (eds.) WMC 2003. LNCS, vol. 2933, pp. 250–268. Springer, Heidelberg (2004)
Pérez–Jiménez, M.J., Romero-Campero, F.J.: Trading polarizations for bi-stable catalysts in P systems with active membranes. In this volume
Pérez–Jiménez, M.J., Romero-Campero, F.J.: An efficient family of P systems for packing items into bins. Journal of Universal Computer Science 10(5), 650–670 (2004)
Pérez–Jiménez, M.J., Romero-Campero, F.J.: Attacking the Common Algorithmic problem by recognizer P systems. In: Margenstern, M. (ed.) MCU 2004. LNCS, vol. 3354, p. 27. Springer, Heidelberg (2005)
Pérez–Jiménez, M.J., Romero-Jiménez, A., Sancho-Caparrini, F.: Teoría de la Complejidad en Modelos de Computación con Membranas. Ed. Kronos, Sevilla (2002)
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), 265–285 (2003)
Pérez–Jiménez, M.J., Romero–Jiménez, A., Sancho–Caparrini, F.: Solving VALIDITY problem by active membranes with input. In: Cavaliere, M., Martín-Vide, C., Păun, G. (eds.) Proceedings of the Brainstorming Week on Membrane Computing, Report GRLMC 26/03, pp. 279–290 (2003)
Pérez–Jiménez, M.J., Romero–Jiménez, A., Sancho–Caparrini, F.: The P versus NP problem through cellular computing with membranes. In: Jonoska, N., Păun, G., Rozenberg, G. (eds.) Aspects of Molecular Computing. LNCS, vol. 2950, pp. 338–352. Springer, Heidelberg (2003)
Riscos-Núñez, A.: Programación celular: Resolución eficiente de problemas numéricos NP–completos. PhD. Thesis, University of Seville, Spain (2004)
Romero-Jiménez, A.: Complexity and Universality in Cellular Computing Models, PhD. Thesis, University of Seville, Spain (2003)
Romero-Jiménez, A., Pérez–Jiménez, M.J.: Simulating Turing machines by P systems with external output. Fundamenta Informaticae 49(1-3), 273–287 (2002)
Sosik, P.: The computational power of cell division. Natural Computing 2(3), 287–298 (2003)
Zandron, C., Ferreti, C., Mauri, G.: Solving NP-complete problems using P systems with active membranes. In: Antoniou, I., Calude, C., Dinneen, M.J. (eds.) Unconventional Models of Computation, UMC 2000, pp. 289–301. Springer, Berlin (2000)
Zandron, C., Mauri, G., Ferreti, C.: Universality and normal forms on membrane systems. In: Freund, R., Kelemenova, A. (eds.) Proceedings International Workshop on Grammar Systems, Bad Ischl, Austria, July 2000, pp. 61–74 (2000)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Pérez-Jiménez, M.J. (2005). An Approach to Computational Complexity in Membrane Computing. In: Mauri, G., Păun, G., Pérez-Jiménez, M.J., Rozenberg, G., Salomaa, A. (eds) Membrane Computing. WMC 2004. Lecture Notes in Computer Science, vol 3365. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-31837-8_5
Download citation
DOI: https://doi.org/10.1007/978-3-540-31837-8_5
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-25080-7
Online ISBN: 978-3-540-31837-8
eBook Packages: Computer ScienceComputer Science (R0)