Hostname: page-component-78c5997874-94fs2 Total loading time: 0 Render date: 2024-11-20T05:42:12.420Z Has data issue: false hasContentIssue false
  • English
  • Français

The P versus NP Problem from the Membrane Computing View

Published online by Cambridge University Press:  26 February 2014

Mario J. Pérez-Jiménez
Mario J. Pérez-Jiménez*
Affiliation:
Research Group on Natural Computing, Department of Computer Science and Artificial Intelligence, University of Sevilla, Avda. Reina Mercedes s/n, 41012 Sevilla, Spain. E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

In the last few decades several computing models using powerful tools from Nature have been developed (because of this, they are known as bio-inspired models). Commonly, the space-time trade-off method is used to develop efficient solutions to computationally hard problems. According to this, implementation of such models (in biological, electronic, or any other substrate) would provide a significant advance in the practical resolution of hard problems. Membrane Computing is a young branch of Natural Computing initiated by Gh. Păun at the end of 1998. It is inspired by the structure and functioning of living cells, as well as from the organization of cells in tissues, organs, and other higher order structures. The devices of this paradigm, called P systems or membrane systems, constitute models for distributed, parallel and non-deterministic computing. In this paper, a computational complexity theory within the framework of Membrane Computing is introduced. Polynomial complexity classes associated with different models of cell-like and tissue-like membrane systems are defined and the most relevant results obtained so far are presented. Different borderlines between efficiency and non-efficiency are shown, and many attractive characterizations of the P ≠ NP conjecture within the framework of this bio-inspired and non-conventional computing model are studied.

Type
Sea, North, History, Narrative, Energy, Climate: Papers from the 2012 Academia Europaea Bergen Meeting
Information
European Review , Volume 22 , Issue 1 , February 2014 , pp. 18 - 33
Copyright
Copyright © Academia Europaea 2014 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

1.Pérez-Jiménez, M. J., Romero-Jiménez, A. and Sancho-Caparrini, F. (2006) A polynomial complexity class in P systems using membrane division. Journal of Automata, Languages and Combinatorics, 11(4), pp. 423–434.Google Scholar
2.Pérez-Jiménez, M. J., Romero-Jiménez, A. and Sancho-Caparrini, F. (2003) Complexity classes in models of cellular computing with membranes. Natural Computing, 2(3), pp. 265–285.Google Scholar
3.Păun, Gh., Pérez-Jiménez, M. J. and Riscos-Núñez, A. (2008) Tissue P Systems with cell division. International Journal of Computers, Communications and Control, 3(3), pp. 295–303.Google Scholar
4.Gutiérrez-Naranjo, M. A., Pérez-Jiménez, M. J., Riscos-Núñez, A., Romero-Campero, F. J. and Romero-Jiménez, A. (2006) Characterizing tractability by cell–like membrane systems. In: K. G. Subramanian, K. Rangarajan, M. Mukund (eds) Formal models, languages and applications (Singapore: World Scientific), pp. 137–154.Google Scholar
5.Păun, Gh. (2001) P systems with active membranes: attacking NP–complete problems. Journal of Automata, Languages and Combinatorics, 6(1), pp. 75–90.Google Scholar
6.Zandron, C., Ferretti, C. and Mauri, G. (2000) Solving NP-complete problems using P systems with active membranes. In: I. Antoniou, C. S. Calude and M. J. Dinneen (Eds) Unconventional Models of Computation (Berlin: Springer), pp. 289–301.Google Scholar
7.Porreca, A. E. (2008) Computational complexity classes for membrane systems. Master Degree Thesis, Università di Milano-Bicocca, Italy.Google Scholar
8.Pérez-Jiménez, M. J. and Riscos-Núñez, A. (2004) A linear–time solution to the Knapsack problem using P systems with active membranes. Lecture Notes in Computer Science, 2933, pp. 250–268.CrossRefGoogle Scholar
9.Pérez-Jiménez, M. J. and Riscos-Núñez, A. (2005) Solving the Subset-Sum problem by active membranes. New Generation Computing, 23(4), pp. 367–384.Google Scholar
10.Gutiérrez-Naranjo, M. A., Pérez-Jiménez, M. J. and Riscos-Núñez, A. (2005) A fast P system for finding a balanced 2-partition. Soft Computing, 9(9), pp. 673–678.Google Scholar
11.Alhazov, A., Martín-Vide, C. and Pan, L. (2004) Solving graph problems by P systems with restricted elementary active membranes. Lecture Notes in Computer Science, 2950, pp. 1–22.Google Scholar
12.Pérez-Jiménez, M. J. and Romero-Campero, F. J. (2004) An efficient family of P systems for packing items into bins. Journal of Universal Computer Science, 10(5), pp. 650–670.Google Scholar
13.Pérez-Jiménez, M. J. and Romero-Campero, F. J. (2005) Attacking the Common Algorithmic Problem by recognizer P systems. Lecture Notes in Computer Science, 3354, pp. 304–315.Google Scholar
14.Alhazov, A., Martín-Vide, C. and Pan, L. (2003) Solving a PSPACE-complete problem by recognizing P systems with restricted active membranes. Fundamenta Informaticae, 58, pp. 67–77.Google Scholar
15.Porreca, A. E., Mauri, G. and Zandron, C. (2006) Complexity classes for membrane systems. Informatique théorique et applications, 40(2), pp. 141–162.Google Scholar
16.Păun, Gh. (2005) Further twenty six open problems in membrane computing. In: M.A. Gutiérrez-Naranjo, A. Riscos-Núñez, F.J. Romero-Campero and D. Sburlan (eds) Third Brainstorming Week on Membrane Computing (Sevilla: Fénix Editora), pp. 249–262.Google Scholar
17.Gutiérrez-Naranjo, M. A., Pérez-Jiménez, M. J., Riscos-Núñez, A. and Romero-Campero, F. J. (2006) On the power of dissolution in P systems with active membranes. Lecture Notes in Computer Science, 3850, pp. 224–240.CrossRefGoogle Scholar
18.Alhazov, A., Pan, L. and Păun, Gh. (2004) Trading polarizations for labels in P systems with active membranes. Acta Informaticae, 41(2–3), pp. 111–144.Google Scholar
19.Díaz-Pernil, D., Gutiérrez-Naranjo, M. A., Pérez-Jiménez, M. J. and Romero-Jiménez, A. (2009) Efficient simulation of tissue-like P systems by transition cell-like P systems. Natural Computing, 8(4), pp. 797–806.Google Scholar
20.Gutiérrez-Escudero, R., Pérez-Jiménez, M. J. and Rius–Font, M. (2010) Characterizing tractability by tissue-like P systems. Lecture Notes in Computer Science, 5957, pp. 289–300.Google Scholar
21.Porreca, A. E., Murphy, N. and 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. Păun, I. Pérez-Hurtado and L. Valencia-Cabrera (eds) Proceedings of the Tenth Brainstorming Week on Membrane Computing, Volume II (Seville: Fénix Editora), pp. 141–166.Google Scholar
22.Pan, L. and Pérez-Jiménez, M. J. (2010) Computational complexity of tissue–like P systems. Journal of Complexity, 26(3), pp. 296–315.Google Scholar
23.Pan, L., Pérez-Jiménez, M. J., Riscos-Núñez, A. and Rius-Font, M. (2012) New frontiers of the efficiency in tissue P systems. In: L. Pan, Gh. Păun and T. Song (eds) Pre-proceedings of Asian Conference on Membrane Computing (Wuhan: Huazhong University of Science and Technology), pp. 61–73.Google Scholar
24.Pérez-Jiménez, M. J. and Sosík, P. (2013) An optimal frontier of the efficiency of tissue P systems with cell separation. Computational Complexity. Submitted.Google Scholar
25.Pérez-Jiménez, M. J., Riscos-Núñez, A., Rius-Font, M. and 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), pp. 760–775.Google Scholar
26.Macías, L. F., Pérez-Jiménez, M. J., Riscos-Núñez, A. and Rius-Font, M. (2013) The efficiency of tissue P systems with cell separation relies on the environment. Lecture Notes in Computer Science, 7762, pp. 243–256.Google Scholar