Characterizing tractability by cell-like membrane systems

September 27, 2006 19:52 WSPC/Trim Size: 9in x 6in for Review Volume rani-resum CHAPTER 9 CHARACTERIZING TRACTABILITY BY CELL–LIKE MEMBRANE SYSTEMS Miguel A. Guti´errez–Naranjo, Mario J. P´erez–Jim´enez, Agust´ın Riscos-N´u˜nez Francisco J. Romero–Campero, Alvaro Romero–Jim´enez Research Group on Natural Computing Department of Computer Science and Artificial Intelligence, Seville University Avda. Reina Merceds s/n, 41012 Seville, Spain E-mail: {magutier,marper,ariscosn,fran}us.es In this paper we present a polynomial complexity class in the framework of membrane computing. In this context, and using accepting transition P systems, we provide a characterization of the standard computational class Pof problems solvable in polynomial time by deterministic Turing machines. 1. Introduction The Theory of Computation deals with the mechanical solvability of problems, distinguishing clearly between problems for which there are algorithmic procedures solving them, and those for which there are none. But it is very important to clarify the difference between solvability in theory and solvability in practice; that is, studying procedures which can run using an amount of resources likely to be available. Rouhgly speaking, a problem is called tractable if it is mechanically solvable in practice. Computational Complexity Theory tries to classify decision problems according to the amount of resources required for solving them in a mechanical way. A complexity class for a model of computation is a collection of problems that can be solved by some devices of this model with similar computational resources. At the end of 1998, the area of Membrane Computing was initiated by Gh. P˘aun 7coming from the observation that the processes which take place in the complex structure of a living cell can be considered as computations, and providing basic computing models consisting of distributed parallel 1 September 27, 2006 19:52 WSPC/Trim Size: 9in x 6in for Review Volume rani-resum 2M.A. Guti´errez et al. devices processing multisets in the compartments defined by a cell–like hierarchy of membranes. In this paper we present a polynomial complexity class in that framework, allowing us to detect some intrinsic difficulties of the resolution of a problem. In that context, a characterization of the standard computational class Pof tractable problems (that is, problems solvable in polynomial time by deterministic Turing machines) is obtained. The paper is organized as follows: in the next section some preliminary notions are given. In section 3 we define the cellular framework (accepting cell–like membrane systems) in which a computational complexity theory will be developed. Section 4 introduces a polynomial complexity class associated with P systems. Sections 5 and 6 are devoted to characterize the standard class Pthrough cellular computing models. We work in this paper with cell–like membrane systems using symbol– objects. References 1. A. Alhazov, C. Mart´ın–Vide, L. Pan, Solving graph problems by P systems with restricted elementary active membranes, in Aspects of Molecular Computing (N. Jonoska, Gh. P˘aun, G. Rozenberg, eds.), Lecture Notes in Computer Science 2950 (2004), 1–22. 2. M.A. Guti´errez–Naranjo, M.J. P´erez–Jim´enez, A. Riscos–N´u˜nez, A fast P system for finding a balanced 2-partition, Soft Computing (2005), in press. 3. S.N. Krishna, R. Rama, A variant of P systems with active membranes: Solving NP–complete problems, Romanian Journal of Information Science and Technology 2, 4 (1999), 357–367. 4. A. Obtulowicz, Deterministic P systems for solving SAT problem, Romanian Journal of Information Science and Technology 4, 1–2 (2001), 551–558. 5. Gh. P˘aun, P systems with active membranes: Attacking NP–complete problems, Journal of Automata, Languages and Combinatorics 6, 1 (2001), 75–90. 6. Gh. P˘aun, Membrane Computing. An Introduction, Springer-Verlag, Berlin, 2002. 7. P˘aun G. Computing with membranes, Journal of Computer and System Sciences 61, 1 (2000), 108–143, and Turku Center for Computer Science-TUCS Report Nr. 208, 1998. 8. M.J. P´erez–Jim´enez, A. Romero–Jim´enez, F. Sancho–Caparrini, Complexity classes in models of cellular computing with membranes, Natural Computing 2, 3 (2003), 265–285. 9. M.J. P´erez–Jim´enez, A. Riscos–N´u˜nez, A linear time solution to the Knapsack problem using active membranes, in Membrane Computing (C. Mart´ın- Vide, Gh. P˘aun, G. Rozenberg, A. Salomaa, eds.), Lecture Notes in Computer Science 2933 (2004), 250–268. September 27, 2006 19:52 WSPC/Trim Size: 9in x 6in for Review Volume rani-resum Characterizing tractability by cell–like membrane systems 3 10. M.J. P´erez–Jim´enez, F.J. Romero-Campero, An efficient family of P systems for packing items into bins, Journal of Universal Computer Science 10, 5 (2004), 650–670. 11. M.J. P´erez–Jim´enez, F.J. Romero-Campero, Attacking the Common Algorithmic problem by recognizer P systems, in Machines, Computations and Universality, MCU’2004, Revised Papers (M. Margenstern, ed.), Lecture Notes in Computer Science 3354 (2005), 304-315. 12. M.J. P´erez–Jim´enez, A. Riscos–N´u˜nez, Solving the Subset-Sum problem by P systems with active membranes, New Generation Computing (2005), in press. 13. A. Romero-Jim´enez, Complexity and Universality in Cellular Computing Models, PhD. Thesis, University of Seville, Spain, 2003. 14. A. Romero-Jim´enez, M.J. P´erez Jim´enez, Simulating Turing machines by P systems with external output, Fundamenta Informaticae 49, 1–3 (2002), 273–287. 15. C. Zandron, C. Ferreti, G. Mauri, Solving NP-complete problems using P systems with active membranes, in Unconventional Models of Computation, UMC’2K (I. Antoniou, C. Calude, M.J. Dinneen, eds.), Springer-Verlag (2000), 289–301.