Skip to main content
SpringerLink
Log in

Seeking computational efficiency boundaries: the Păun’s conjecture

  • Regular Paper
  • Published:
Journal of Membrane Computing Aims and scope Submit manuscript

Abstract

In 2005, Gh. Păun raised an interesting question concerning the role of electrical charges in P systems with active membranes from a complexity point of view. Specifically, he formulated a question about the computational efficiency of polarizationless P systems with dissolution rules and division rules only for elementary membranes. Several approaches have been carried out, and some partial answers have been given. This is probably the most important open problem in computational complexity theory in the framework of Membrane Computing. The study of the efficiency of membrane systems has been a very fruitful area, providing not only the above-stated partial answers, but also several frontiers of efficiency to tackle the P vs NP problem. In this work, a survey on classical and current results on complexity aspects is given, emphasizing on the frontiers of efficiency and the ingredients taken into account for each of them.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Notes

  1. Terms uniform and semi-uniform are used similarly to how they are used in circuit complexity [50].

References

  1. Alhazov, A., Freund, R., Păun, Gh. (2004) P systems with active membranes and two polarizations. In Gh. Păun, A. Riscos-Núñez, Á. Romero-Jiménez, F. Sancho-Caparrini (eds.) Proceedings of the Second Brainstorming Week on Membrane Computing, Sevilla, 2-7 February 2004, Research Group on Natural Computing, TR 01/2004, University of Seville, pp. 20-36.

  2. Alhazov, A., & Pérez-Jiménez, M.J. (2007). Uniform solution of QSAT using polarizationless active membranes. In J. Durand-Lose and M. Margenstern (eds.) Machines, Computations, and Universality. Lecture Notes in Computer Science, 4664, 122-133.

  3. Gutiérrez-Escudero, R., Pérez-Jiménez, M. J., & Rius-Font, M. (2010). Characterizing tractability by tissue-like P systems. Lecture Notes in Computer Science, 5957(5957), 289–300.

    Article  Google Scholar 

  4. Gutiérrez-Naranjo, M. Á., Pérez-Jiménez, M. J., & Riscos-Núñez, A. (2005). A fast P system for finding a balanced 2-partition. Soft Computing, 9(9), 673–678.

    Article  Google Scholar 

  5. Gutiérrez, M.Á., Pérez-Jiménez, M.J., Riscos-Núñez, A., & Romero-Campero, F.J. (2006). On the power of dissolution in P systems with active membranes. In R. Freund, Gh. Paun, Gr. Rozenberg, A. Salomaa (eds.) Membrane Computing, 6th International Workshop, WMC 2005, Vienna, Austria, July 18-21, 2005, Revised Selected and Invited Papers. Lecture Notes in Computer Science, 3850, pp. 224-240.

  6. Gutiérrez-Naranjo, M. Á., Pérez-Jiménez, M. J., Riscos-Núñez, A., Romero-Campero, F. J., & Romero-Jiménez, Á. (2006). Characterizing tractability by cell-like membrane systems. In K. G. Subramanian, K. Rangarajan, & M. Mukund (Eds.), Formal models, languages and applications (pp. 137–154). Singapore: World Scientific.

    Chapter  Google Scholar 

  7. Ionescu, M., Păun, Gh, & Yokomori, T. (2006). Spiking neural P systems. Fundamenta Informaticae, 71(2–3), 279–308.

    MathSciNet  MATH  Google Scholar 

  8. Leporati, A., Manzoni, L., Mauri, G., Porreca, A.E., & Zandron, C. (2014). Simulating elementary active membranes. In M. Gheorghe et al. (eds.) Membrane Computing, 15th International Conference, CMC 2014, Revised Selected Papers, Lecture Notes in Computer Science, 8961, pp. 284-299.

  9. Leporati, A., Manzoni, L., Mauri, G., Porreca, A. E., & Zandron, C. (2018). Solving a special case of the P conjecture using dependency graphs with dissolution. In M. Gheorghe, et al. (Eds.), Membrane Computing, 18th International Conference (pp. 196–213). CMC 2017, Springer.

  10. Macías-Ramos, L.F., Pérez-Jiménez, M.J., Riscos, A., Rius, M., & Valencia-Cabrera, L. (2013). The efficiency of tissue P systems with cell separation relies on the environment. In E. Csuhaj-Varjú, M. Gheorghe, G. Rozenberg, A. Salomaa, G. Vaszil (eds.) Membrane Computing- 13th International Conference CMC 2012 Budapest, Hungary, August 28-31, 2012, Revised Selected Papers. Lecture Notes in Computer Science, 7762, pp. 243-256.

  11. Macías-Ramos, L. F., Pérez-Jiménez, M. J., Riscos-Núñez, A., & Valencia-Cabrera, L. (2015). Membrane fission versus cell division: when membrane proliferation is not enough. Theoretical Computer Science, 608, 57–65.

    Article  MathSciNet  Google Scholar 

  12. Macías-Ramos, L. F., Song, B., Valencia-Cabrera, L., Pan, L., & Pérez-Jiménez, M. J. (2016). Membrane fission: a computational complexity perspective. Complexity, 21(6), 321–334.

    Article  MathSciNet  Google Scholar 

  13. Macías-Ramos, L.F., Song, B., Song, T., Pan, L., & Pérez-Jiménez, M.J. (2017). Limits on efficient computation in P systems with symport/antiport. In C. Graciani, Gh. Păun, A. Riscos-Núñez, L. Valencia-Cabrera (eds.) Proceedings of the Fifteenth Brainstorming Week on Membrane Computing, January 31, February 3, Sevilla, Spain, pp. 147-160.

  14. Martín Vide, C., Pazos, J., Păun, Gh., & Rodríguez Patón, A. (2002). A New Class of Symbolic Abstract Neural Nets: Tissue P Systems. Lecture Notes in Computer Science 2387, 290-299.

  15. Martín Vide, C. Pazos, J., Păun, Gh. & Rodríguez Patón, A. (2003). Tissue P systems. Theoretical Computer Science, 296, 295-326.

  16. Orellana-Martín, D., Valencia-Cabrera, L., Song, B., Pan, L., & Pérez-Jiménez, M.J. (2018). Narrowing Frontiers with Evolutional Communication rules and Cell Separation. In D. Orellana, Gh. Păun, A. Riscos, L. Valencia (eds.), Proceedings of the Sixteenth Brainstorming Week on Membrane Computing, Sevilla, Spain, January 30 - February 2, pp. 123-162.

  17. Orellana-Martín, D., Valencia-Cabrera, L., Song, B., Pan, L., & Pérez-Jiménez, M. J. (2020). P systems with symport/antiport rules: When do the surroundings matter? Theoretical Computer Science, 805, 206–217.

    Article  MathSciNet  Google Scholar 

  18. Orellana-Martín, D., Valencia-Cabrera, L., Song, B., Pan, L., & Pérez-Jiménez, M.J. Tuning frontiers of efficiency in tissue P systems with evolutional communication rules. Complexity, to be published.

  19. Orellana-Martín, D., Valencia-Cabrera, L., Riscos-Núñez, A., & Pérez-Jiménez, M. J. (2019). A path to computational efficiency through membrane computing. Theoretical Computer Science, 777, 443–453.

    Article  MathSciNet  Google Scholar 

  20. Pan, L., & Ishdorj, T.-O. (2004). P systems with active membranes and separation rules. Journal of Universal Computer Science, 10(5), 630–649.

    MathSciNet  Google Scholar 

  21. Pan, L., & Pérez-Jiménez, M. J. (2010). Computational complexity of tissue-like P systems. Journal of Complexity, 26(3), 296–315.

    Article  MathSciNet  Google Scholar 

  22. Pan, L., Pérez-Jiménez, M.J., Riscos, A., & Rius, M. (2012). New frontiers of the efficiency in tissue P systems. L. Pan, Gh. Paun, T. Song (eds.) Pre-proceedings of Asian Conference on Membrane Computing (ACMC 2012), Huazhong University of Science and Technology, Wuhan, China, October 15-18, pp. 61-73.

  23. Papadimitriou, C. H. (1994). Computational complexity. USA: Addison-Wesley Publishing Company.

    MATH  Google Scholar 

  24. Pan, L., Song, B., Valencia-Cabrera, L., & Pérez-Jiménez, M.J. (2018 ). The Computational Complexity of Tissue P Systems with Evolutional Symport/Antiport Rules. Complexity, 2018(3745210), 21 pages, (https://doi.org/10.1155/2018/3745210).

  25. Păun, Gh. (2002). Membrane computing. an introduction. Berlin: Springer-Verlag.

    Book  Google Scholar 

  26. Păun, A., & Păun (2001). On the Membrane Computing based on splicing. In C. Martín-Vide, V. Mitrana (eds.) Where Mathematics, Computer Science, Linguistics and Biology Meet: Essays in honour of Gheorghe Păun, 54, 409-422

  27. Păun, A., & Păun, Gh. (2002). The power of communication: P systems with symport/antiport. New Generation Computing, 20(3), 295–305.

    Article  Google Scholar 

  28. Păun, Gh. (2000). Computing with membranes. Journal of Computer and Systems Science, 61(1), 108–143.

    Article  MathSciNet  Google Scholar 

  29. Păun, Gh. (2001). P systems with active membranes: attacking NP-complete problems. Journal of Automata, Languages and Combinatorics, 6, 75–90.

    MathSciNet  MATH  Google Scholar 

  30. Păun, Gh. (2005). Further twenty six open problems in membrane computing. In M.Á. Gutiérrez-Naranjo, A. Riscos-Núñez, F.J. Romero-Campero, D. Sburlan (eds.) Proceedings of the Third Brainstorming Week on Membrane Computing, Fénix Editora, Sevilla, pp. 249-262.

  31. Păun, Gh, Sakakibara, Y., & Yokomori, T. (2002). P systems on graphs of restricted forms. Publicationes Mathematicae, 60, 635–660.

    MathSciNet  MATH  Google Scholar 

  32. Păun, Gh., Yokomori, T. (1999). Membrane Computing based on splicing. In E. Winfree, D.K. Guidford (eds.) DNA based Computers V. DIMACS, Series Discrete Mathematics Theoretical Computer Science, 54, 217-231.

  33. Păun, A., Păun, Gh, & Rozenberg, G. (2002). Computing by communication in networks of membranes. International Journal of Foundations of Computer Science, 13(6), 779–798.

    Article  MathSciNet  Google Scholar 

  34. Păun, Gh., Pérez-Jiménez, M.J., & Riscos-Núñez, A. (2008). Tissue P system with cell division. International Journal of Computers, Communications & Control, Vol. III, 3, 295-303.

  35. Pérez-Jiménez, M.J., & Riscos-Núñez, A. (2004). A linear-time solution to the Knapsack problem using P systems with active membranes. In C. Martín-Vide, Gh. Păun, G. Rozenberg, A. Salomaa (eds.) Membrane Computing International Workshop, WMC 2003, Tarragona, Spain, July 17-22, 2003, Revised Papers. Lecture Notes in Computer Science, 2933, 250-268.

  36. Pérez-Jiménez, M. J., & Riscos-Núñez, A. (2005). Solving the Subset-Sum problem by active membranes. New Generation Computing, 23(4), 367–384.

    MATH  Google Scholar 

  37. Pérez-Jiménez, M. J., Riscos-Núñez, A., Rius-Font, M., & Romero-Campero, F. J. (2013). A polynomial alternative to unbounded environment for tissue P systems with cell division. International Journal of Computer Mathematics, 90(4), 760–775.

    Article  MathSciNet  Google Scholar 

  38. Pérez-Jiménez, M.J., Romero-Jiménez, Á., & Sancho-Caparrini, F. (2002). Decision P systems and the \({\bf P} \ne {\bf NP}\) conjecture. Lecture Notes in Computer Science, 2597 (2003), 388-399. A preliminary version in Gh. Păun, C. Zandron (eds.) Pre-proceedings of Workshop on Membrane Computing 2002, MolCoNet project-IST-2001-32008, Publication No. 1, Curtea de Arges, Romanian, August 19-23, pp. 345-354.

  39. Pérez-Jiménez, M. J., Romero-Jiménez, Á., & Sancho-Caparrini, F. (2003). Complexity classes in models of cellular computing with membranes. Natural Computing, 2(3), 265–285.

    Article  MathSciNet  Google Scholar 

  40. Pérez-Jiménez, M. J., & Sosík, P. (2015). An Optimal Frontier of the Efficiency of Tissue P Systems with Cell Separation. Fundamenta Informaticae, 138(1–2), 45–60.

    Article  MathSciNet  Google Scholar 

  41. Pérez-Jiménez, M.J., Romero-Campero, F.J. (2005). Trading polarizations for bi-stable catalysts in P systems with active membranes. In G. Mauri, Gh. Păun, M.J. Pérez-Jiménez, Gr. Rozenberg, A. Salomaa (eds.) Membrane Computing, 5th International Workshop, WMC5, Revised Selected and Invited Papers. Lecture Notes in Computer Science, 3365, 373-388.

  42. Porreca, Antonio E., Leporati, Alberto, Mauri, Giancarlo, Zandron. P., Claudio (2011). systems with elementary active membranes: Beyond NP and coNP. In Marian Gheorghe, Thomas Hinze, Gheorghe Pǎun, Grzegorz Rozenberg,Arto Salomaa (eds.), Membrane Computing, 11th International Conference, CMC 2010,Lecture Notes in Computer Science, 6501, pages 338-347.

  43. Porreca, A.E., Murphy, N., & Pérez-Jiménez, M.J. (2012). An optimal frontier of the efficiency of tissue P systems with cell division. In M. García-Quismondo, L.F. Macías-Ramos, Gh. Paun, I. Pérez Hurtado, L. Valencia-Cabrera (eds.) Proceedings of the Tenth Brainstorming Week on Membrane Computing, Volume II, Seville, Spain, January 30- February 3, 2012, Report RGNC 01/2012, Fénix Editora, pp. 141-166.

  44. Porreca, A.E. (2008). Computational Complexity Classes for Membrane Systems, Master Degree Thesis, Università di Milano-Bicocca, Italy.

  45. Porreca, A.E., Leporati, A., Mauri, G., & Zandron, C. (2012). P systems simulating oracle computations. In M. Gheorghe, Gh. Păun, G. Rozenberg, A. Salomaa, S. Verlan (eds.) Membrane Computing 12th International Conference, CMC 2011, Fontainebleau, France, August 23-26, 2011, Revised Selected Papers. Lecture Notes in Computer Science, 7184, 346-358.

  46. Sosík, P., & Rodríguez-Patón, A. (2007). Membrane computing and complexity theory: a characterization of PSPACE. Journal of Computer and System Sciences, 73(1), 137–152.

    Article  MathSciNet  Google Scholar 

  47. Song, B., Zhang, C., Pan, L. (2017). Tissue-like P systems with evolutional symport/antiport rules. Information Sciences, 378, 177-193 (https://doi.org/10.1016/j.ins.2016.10.046).

  48. Valencia-Cabrera, L., Song, B., Macías-Ramos, L.F., Pan, L., Riscos-Núñez, A., Pérez-Jiménez, M.J. (2015). Computational efficiency of P systems with symport/antiport rules and membrane separation. In L.F. Macías, Gh. Păun, A. Riscos, L. Valencia (eds) Proceedings of the Thirteenth Brainstorming Week on Membrane Computing, 2-6 February, Sevilla, Spain, pp. 325-370.

  49. Valencia-Cabrera, L., Song, B., Macías-Ramos, L.F., Pan, L., Riscos-Núñez, A., Pérez-Jiménez, M.J. (2015). Minimal cooperation in P systems with symport/antiport: A complexity approach. In L.F. Macías, Gh. Păun, A. Riscos, L. Valencia (eds) Proceedings of the Thirteenth Brainstorming Week on Membrane Computing, 2-6 February, Sevilla, Spain, pp. 301-323

  50. Vollmer, H. (1999). Introduction to circuit complexity—a uniform approach. Springer,. https://doi.org/10.1007/978-3-662-03927-4.

    Article  MATH  Google Scholar 

  51. Zandron, C., Ferretti, C., & Mauri, G. (2000). Solving NP-complete problems using P systems with active membranes. In I. Antoniou, et al. (Eds.), Unconventional Models of Computation (pp. 289–301). Berlin: Springer-Verlag.

    Google Scholar 

Download references

Acknowledgements

This work was supported in part by the research project TIN2017-89842-P, cofinanced by Ministerio de Economía, Industria y Competitividad (MINECO) of Spain, through the Agencia Estatal de Investigación (AEI), and by Fondo Europeo de Desarrollo Regional (FEDER) of the European Union.

Author information

Authors and Affiliations

  1. Research Group on Natural Computing Dept. of Computer Science and Artificial Intelligence, Universidad de Sevilla E.T.S.I. Informática, Avda. Reina Mercedes s/n, 41012, Sevilla, Spain

    David Orellana-Martín & Agustín Riscos-Núñez

Authors
  1. David Orellana-Martín
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Agustín Riscos-Núñez
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to David Orellana-Martín.

Ethics declarations

Conflict of interest

The authors declare that they have no conflict of interest.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Orellana-Martín, D., Riscos-Núñez, A. Seeking computational efficiency boundaries: the Păun’s conjecture. J Membr Comput 2, 323–331 (2020). https://doi.org/10.1007/s41965-020-00058-8

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s41965-020-00058-8

Keywords

Mathematics Subject Classification

Search

Navigation