On the Computational Efficiency of Polarizationless Recognizer P Systems with Strong Division and Dissolution

• Autorzy: Zandron C. , Leporati A. , Ferretti C. , Mauri G. , Pérez-Jiménez M.J.
• Języki publikacji: EN

Abstrakty

EN

Recognizer P systems with active membranes have proven to be very efficient computing devices, being able to solve NP-complete decision problems in a polynomial time. However such solutions usually exploit many powerful features, such as electrical charges (polarizations) associated to membranes, evolution rules, communication rules, and strong or weak forms of division rules. In this paper we contribute to the study of the computational power of polarizationless recognizer P systems with active membranes. Precisely, we show that such systems are able to solve in polynomial time the NP-complete decision problem 3-SAT by using only dissolution rules and a form of strong division for non–elementary membranes, working in the maximallly parallel way.

Słowa kluczowe

EN

P systems with active membranes; membrane division; membrane dissolution; NP-complete problems; 3-SAT

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2008
• Tom: Vol. 87, nr 1
• Strony: 79--91
• Opis fizyczny: bibliogr. 24 poz., wykr.

Twórcy

autor

Zandron C.

autor

Leporati A.

autor

Ferretti C.

autor

Mauri G.

autor

Pérez-Jiménez M.J.

• Dipartimento di Informatica, Sistemistica e Comunicazione, Universita degli Studi di Milano – Bicocca, Viale Sarca 336/14, 20126 Milano, Italy,

Bibliografia

• [1] Alhazov, A., Freund, R.: On efficiency of P systems with active membranes and two polarizations, Membrane Computing, Fifth International Workshop, WMC 2004 (G. Mauri, Gh. Păun, M. J. Pérez-Jiménez, G.Rozenberg, A. Salomaa, Eds.), LNCS 3365, Springer-Verlag, Berlin, 2005, 81-94.
• [2] Alhazov, A., Pérez-Jiménez, M. J.: Uniform solution to QSAT using polarizationless active membranes, Proceedings of the Fourth Brainstorming Week on Membrane Computing (M. A. Gutiérrez-Naranjo, Gh. Păun, A. Riscos-Núñez, F. J. Romero-Campero, Eds.), Volume I, Fénix Editora, Sevilla, 2006, 29-40.
• [3] Garey, M. R., Johnson, D. S.: Computers and intractability. A guide to the theory on NP-completeness, W. H. Freeman and Company, 1979.
• [4] 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, 9(9), 2005, 673-678.
• [5] Gutiérrez-Naranjo,M. A., Pérez-Jiménez,M. J., Riscos-Núñez, A., Romero-Campero, F. J.: On the power of dissolution in P systems with active membranes,Membrane Computing, Sixth InternationalWorkshop,WMC 2005 (R. Freund, Gh. Păun, G. Rozenberg, A. Salomaa, Eds.), LNCS 3850, Springer-Verlag, Berlin, 2006, 224-240.
• [6] Gutiérrez-Naranjo, M. A., Pérez-Jiménez, M. J., Riscos-Núñez, A., Romero-Campero, F. J., Romero-Jiménez, A.: Characterizing tractability by cell-like membrane systems, in: Formal models, languages and applications (K. G. Subramanian, K. Rangarajan, M. Mukund, Eds.), Series in Machine Perception and Artificial Intelligence, Vol. 66,World Scientific, 2006, 137-154.
• [7] 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), 1999, 357-367.
• [8] Mauri, G., Pérez-Jiménez, M. J., Zandron, C.: On a Păun conjecture in membrane systems, Second International Work-Conference on the Interplay Between Natural and Artificial Computation, IWINAC 2007 (J.Mira, J. R. álvarez, Eds.), Part I, LNCS 4527, Springer-Verlag, Berlin, 2007, 180-192.
• [9] Obtulowicz, A.: Deterministic P systems for solving SAT problem, Romanian Journal of Information Science and Technology, 4(1-2), 2001, 551-558.
• [10] Papadimitriou, C.H.: Computational complexity, Addison-Wesley, 1994.
• [11] Păun, Gh.: Computing with membranes, Journal of Computer and System Sciences, 1(61), 2000, 108-143. See also Turku Centre for Computer Science - TUCS Report No. 208, 1998.
• [12] Păun, Gh.: Computing with membranes. An introduction, Bulletin of the EATCS, 67, February 1999, 139-152.
• [13] Păun, Gh.: P systems with active membranes: Attacking NP-complete problems, Journal of Automata, Languages and Combinatorics, 6(1), 2001, 75-90.
• [14] Păun, Gh.: Membrane computing. An introduction, Springer-Verlag, Berlin, 2002.
• [15] Păun, Gh.: Further twenty six open problems in membrane computing. Proceedings of the Third Brainstorming Week on Membrane Computing (M. A. Gutiérrez-Naranjo, A. Riscos-Núñez, F. J. Romero-Campero, D.Sburlan, Eds.), Fénix Editora, Sevilla, 2005, 249-262.
• [16] Păun, Gh., Rozenberg, G.: A guide to membrane computing, Theoretical Computer Science, 287(1), 2002, 73-100.
• [17] Pérez-Jiménez, M. J., Riscos-Núñez, A.: A linear-time solution to the KNAPSACK problem using P systems with active membranes,Membrane Computing, Fourth InternationalWorkshop, WMC 2003 (C.Martín-Vide, Gh. Păun, G. Rozenberg, A. Salomaa, Eds.), LNCS 2933, Springer-Verlag, Berlin, 2004, 250-268.
• [18] Pérez-Jiménez, M. J., Riscos-Núñez, A.: Solving the SUBSET SUM problem by active membranes, New Generation Computing, 23(4), 2005, 367-384.
• [19] Pérez-Jiménez,M. J., Romero-Campero, F. J.: Attacking the COMMON ALGORITHMIC PROBLEM by recognizer P systems, Machines, Computations and Universality (M. Margenstern, Ed.), LNCS 3354, Springer-Verlag, Berlin, 2005, 304-315.
• [20] Pérez-Jiménez, M. J., Romero-Jiménez, A., Sancho-Caparrini, F.: A polynomial complexity class in P systems using membrane division, Proceedings of the Fifth Workshop on Descriptional Complexity of Formal Systems, DCFS 2003 (E. Csuhaj-Varjú, C. Kintala, D.Wotschke, G. Vaszil, Eds.), Computer and Automation Research Institute of the Hungarian Academy of Sciences, Budapest, 2003, 284-294.
• [21] Pérez-Jiménez,M. J., Romero-Jiménez, A., Sancho-Caparrini, F.: The P versus NP problem through cellular computing with membranes, Aspects of Molecular Computing (N. Jonoska, Gh. Păun, G. Rozenberg, Eds.), LNCS 2950, Springer-Verlag, Berlin, 2004, 338-352.
• [22] Sosik, P.: The computational power of cell division, Natural Computing, 2(3), 2003, 287-298.
• [23] Zandron, C., Ferretti, C., Mauri, G.: Solving NP-complete problems using P systems with active membranes, Unconventional Models of Computation (I. Antoniou, C.S. Calude, M.J. Dinneen, Eds.), Springer-Verlag, Berlin, 2000, 289-301.
• [24] The P systems Web page: http://ppage.psystems.eu/