Polarizationless P Systems with Active Membranes: Computational Complexity Aspects

Journal of Automata, Languages and Combinatorics 21 (2016) 1–2, 107 – 123 c Institut für Informatik ·Justus-Liebig-Universität Giessen POLARIZATIONLESS P SYSTEMS WITH ACTIVE MEMBRANES: COMPUTATIONAL COMPLEXITY ASPECTS Luis Valencia-Cabrera David Orellana-Martín Miguel A. Martínez-del-Amor Agustín Riscos-Núñez Mario J. Pérez-Jiménez Research Group on Natural Computing, Department of Computer Science and Artificial Intelligence, Universidad de Sevilla Avda. Reina Mercedes s/n, 41012 Sevilla, Spain {lvalencia, dorellana, mdelamor, ariscosn, marper}@us.es ABSTRACT P systems with active membranes, in their classical definition, make use of noncooperative rules only. However, it is well known that in living cells, proteins interact among them yielding new products. Inspired by this biological phenomenon, the previous framework is reformulated in this paper, allowing cooperation in object evolution rules, while removing electrical charges associated with membranes. More precisely, minimal cooperation in object evolution rules is incorporated in polarizationless P systems with active membranes. In this paper, the term “minimal” means that the left-hand side of such rules consists of at most two symbols, and its length is greater than or equal to the corresponding right-hand side. The computational efficiency of this kind of P systems is studied by providing a uniform polynomial-time solution to SAT problem in such manner that only division rules for elementary membranes are used and dissolution rules are forbidden. Bearing in mind that only tractable problems can be efficiently solved by families of polarizationless P systems with active membranes and without dissolution rules, passing from non-cooperation to minimal cooperation in object evolution rules amounts passing from non-efficiency to efficiency in this framework. This frontier of efficiency provides, as any other borderline does, a possible way to address the Pversus NP problem. Keywords: membrane computing, active membranes, minimal cooperation, mitosis, computational complexity, the Pversus NP problem 1. Introduction A possible way of producing new membranes in living cells is based on the mitosis process. Mitosis is a basic process of each cell life cycle in eukaryotic cells which allows producing two or more cells from one cell that could be considered as the “mother”. Several mechanisms based on cell division were introduced in Membrane Computing [11], a distributed parallel computing paradigm inspired by the way the living cells process chemical substances, energy and information. The processor units 108 L. Valencia,D. Orellana,M. A. Martínez,A. Riscos,M. J. Pérez in the basic model are abstractions of biological membranes, selectively permeable barriers which give cells their outer boundaries (plasma membranes) and their inner compartments (organelles). They control the flow of information between cells, the movement of substances into and out of cells, and they are also involved in the capture and release of energy. Biological membranes play an active part in the life of the cell. In fact, the passing of chemical substances through a biological membrane often requires an interaction between the membrane itself and the protein channels present within it. During this interaction, both the chemical substances and the membrane itself can be modified at least locally. P systems with active membranes [8] incorporate the mitosis based mechanisms by means of membrane division rules. By applying this kind of rules, under the influence of the object triggering it, the membrane is divided into two membranes and that object is replaced in the two new ones by possibly different objects, being the remaining objects duplicated in both the created membranes. These models are computationally universal (they are equivalent in power to deterministic Turing machines) and they have the ability to provide efficient solutions to computationally hard problems, by making use of an exponential workspace created in a polynomial time (often, in linear time). Moreover, PSPACE-complete problems can be efficiently solved by families of P systems with active membranes which use division for elementary and non-elementary membranes. Consequently, the usual framework of P systems with active membranes and polarizations for solving decision problems seems to be too powerful from the computational complexity point of view. P systems with active membranes and without electrical charges were initially studied in [1, 2]. However, this initial approach proposed to replace polarizations by a somehow equivalent or even more powerful ingredient: the ability to change the label of the membranes. Our approach is quite different, since we keep labels unchanged. Bearing in mind that consideration, some computational complexity aspects of these systems are studied when (minimal) cooperation in object evolution rules is allowed, and a new frontier of the efficiency is provided. The paper is organized as follows. Next section briefly describes some preliminaries in order to make the work self-contained. In Section 3, polarizationless P systems with active membranes are introduced, and minimal cooperation in object evolution rules is considered. A uniform polynomial time solution to SAT problem by means of a family of polarizationless P systems with active membranes, with minimal cooperation and without dissolution rules, is presented in Section 4. The paper ends with some open problems and concluding remarks. 2. Preliminaries An alphabet Γis a non-empty set and its elements are called symbols. A string u over Γis an ordered finite sequence of symbols, that is, a mapping from a natural number n∈Nonto Γ. The number nis called the length of the string uand it is denoted by |u|, that is, the length of a string is the number of occurrences of symbols it contains. The empty string (with length 0) is denoted by λ. The set of all strings Polarizationless P Syst. with Active Membr.: Computational Complexity Aspects 109 over an alphabet Γis denoted by Γ∗. A language over Γis a subset of Γ∗. Amultiset over an alphabet Γis an ordered pair (Γ, f)where fis a mapping from Γonto the set of natural numbers N. The support of a multiset m= (Γ, f)is defined as supp(m) = {x∈Γ|f(x)>0}. A multiset is finite (respectively, empty) if its support is a finite (respectively, empty) set. We denote by ∅the empty multiset and we denote by Mf(Γ) the set of all finite multisets over Γ. If m1= (Γ, f1)and m2= (Γ, f2)are multisets over Γ, then the union of m1and m2, denoted by m1+m2, is the multiset (Γ, g), where g(x) = f1(x) + f2(x)for each x∈Γ. Let us recall that a free tree (tree, for short) is a connected, acyclic, undirected graph. A rooted tree is a tree in which one of the vertices (called the root of the tree) is distinguished from the others. In a rooted tree the concepts of ascendants and descendants are defined in a usual way. Given a node x(different from the root), if the last edge on the (unique) path from the root of the tree to the node xis (y, x)(in this case, x6=y), then yis the parent of node xand xis achild of node y. The root is the only node in the tree with no parent. A node with no children is called a leaf (see [4] for details). Finally, let us recall that a decision problem Xis a pair (IX,ΘX)where IXis a language over a finite alphabet and ΘXis a Boolean formula over the set IX(called the set of instances of X). 3. Polarizationless P Systems with Active Membranes Let us briefly recall some definitions of P systems models that will be used in the paper (see [11] for details). The reader is supposed to be familiar with basic elements of membrane computing. Abasic transition P system is a membrane system whose rules are of the following forms: evolution, communication, and dissolution. In these systems the size of the membrane structure does not increase, but an exponential workspace (in terms of number of objects) can be constructed in linear time, e. g. via evolution rules of the type [a→a2]h. Nevertheless, this capability is not enough to efficiently solve NP– complete problems, unless P=NP (see [7] for details). Replication is one of the most important functions of a cell and, in ideal circumstances, a cell produces two identical copies by division. Bearing in mind that the reactions which take place in a cell are related to membranes, division rules for elementary and non-elementary membranes are considered in the so-called P systems with active membranes. This variant was first introduced by Gh. Păun [9] and it has electrical charges associated with membranes, but the rules are non-cooperative and there are not priorities. Nevertheless, the class of all problems solvable in polynomial time in a uniform way by means of families of P systems with active membranes which use division for elementary and non-elementary membranes coincides with PSPACE [15]. 110 L. Valencia,D. Orellana,M. A. Martínez,A. Riscos,M. J. Pérez 3.1. Polarizationless P systems with active membranes: Syntax In this paper, electrical charges are removed, so we deal with polarizationless P systems with active membranes. Definition 1. A polarizationless P system with active membranes of degree qis a tuple Π = (Γ, H, µ, M1, . . . , Mq,R, iout), where •Γis a finite alphabet whose elements are called objects; •His a finite alphabet such that H∩Γ = ∅whose elements are called labels; •µis a labelled rooted tree (called membrane structure) consisting of qnodes injectively labeled by elements of H; • M1, . . . , Mqare multisets over Γ; • R is a finite set of rules, of the following forms: (a0) [ a→u]hfor h∈H,a∈Γ,u∈Mf(Γ) (object evolution rules). (b0)a[ ]h→[b]hfor h∈H,a, b ∈Γand his not the label of the root of µ (send–in communication rules). (c0) [ a]h→b[ ]hfor h∈H,a, b ∈Γ(send–out communication rules). (d0) [ a]h→bfor h∈H\ {iout},a, b ∈Γand his not the label of the root of µ(dissolution rules). (e0) [ a]h→[b]h[c]hfor h∈H\ {iout},a, b, c ∈Γand his the label of an elementary membrane different of the root of µ(division rules for elementary membranes). (f0) [ [ ]h1[ ]h2]h0→[ [ ]h1]h0[ [ ]h2]h0, where h0, h1, h2∈Hand h0is not the label of the root of µ(division rules for for non–elementary membranes). •iout ∈H∪ {env}(if iout ∈Hthen iout is the label of a leaf of µ). A polarizationless P system with active membranes of degree q, Π = (Γ, H, µ, M1, . . . , Mq,R, iout), can be viewed as a set of qmembranes, labelled by elements of H, arranged in a hierarchical structure µgiven by a rooted tree, whose root is called the skin membrane, such that: (a) M1, . . . , Mqrepresent the finite multisets of objects initially placed in the qmembranes of the system; (b) Ris a finite set of rules over Γassociated with the labels; (c) iout ∈H∪ {env}indicates the output region. We use the term region i to refer to membrane iin the case i∈Hand to refer to the “environment” of the system in the case i=env. The leaves of µare called elementary membranes; any other membrane is said to be non-elementary. 3.2. Polarizationless P systems with active membranes: Semantics An instantaneous description or a configuration Ctat an instant tof a polarizationless P system with active membranes is described by the following elements: (a) the Polarizationless P Syst. with Active Membr.: Computational Complexity Aspects 111 membrane structure at instant t, and (b) all multisets of objects over Γassociated with all the membranes present in the system at that moment. An object evolution rule [a→u]h for h∈H,a∈Γ,u∈Mf(Γ), is applicable to a configuration Ctat an instant t, if there exists a membrane labelled by hin Ctwhich contains object a. When applying such a rule, object ais consumed and objects from multiset uare produced in that membrane. A send-in communication rule a[ ]h→[b]h for h∈H,a, b ∈Γ, is applicable to a configuration Ctat an instant t, if there exists a membrane labelled by hin Ctsuch that his not the label of the root of µand its parent membrane contains object a. When applying such a rule, object ais consumed from the parent membrane and object bis produced in the corresponding membrane h. A send-out communication rule [a]h→b[ ]h for h∈H,a, b ∈Γ, is applicable to a configuration Ctat an instant t, if there exists a membrane labelled by hin Ctsuch that it contains object a. When applying such a rule, object ais consumed from such membrane hand object bis produced in the parent of such membrane. A dissolution rule [a]h→b for h∈H,a, b ∈Γ, is applicable to a configuration Ctat an instant t, if there exists a membrane labelled by hin Ct, different from the skin membrane and from the output region, such that it contains object a. When applying such a rule, object ais consumed, membrane his dissolved and its objects are sent to the parent (or the first ancestor that has not been dissolved at the same instant t). A division rule [a]h→[b]h[c]h is applicable to a configuration Ctat an instant t, if there exists an elementary membrane labelled by hin Ct, different from the skin membrane and from the output region, such that it contains object a. When applying a division rule [a]h→[b]h[c]h to a membrane labelled by hin a configuration Ct, under the influence of object a, the membrane with label his divided into two membranes with the same label; in the first copy, object ais replaced by object b, in the second one, object ais replaced by object c; all the other objects are replicated and copies of them are placed in the two new membranes. 112 L. Valencia,D. Orellana,M. A. Martínez,A. Riscos,M. J. Pérez A division rule [ [ ]h1[ ]h2]h0→[ [ ]h1]h0[ [ ]h2]h0 is applicable to a configuration Ctat an instant t, if there exists a membrane labelled by h0in Ct, different from the skin membrane and from the output region, which contains two membranes labelled by h1and h2, respectively. When applying such a division rule to a membrane labelled by h0in a configuration Ct, the membrane with label h0is divided into two membranes with the same label containing, respectively, membrane h1and membrane h2with their contents. Besides, if the membrane labelled by h0contains other membranes than those with the labels h1,h2, then these membranes are duplicated and are part of the contents of both new copies of the membrane h0. In polarizationless P systems with active membranes, the rules are applied according to the following principles: •The rules associated with membranes labelled with hare used for all copies of this membrane. •At one transition step, one object of a membrane can be used by only one rule (chosen in a non–deterministic way). •At one transition step, a membrane can be subject of at most one rule of types (b0)–(f0). Rules of these types can be applied at most once on each membrane at each step. •Object evolution rules can be simultaneously applied to a membrane joint with one rule of types (b0)–(f0). In that case, object evolution rules are applied in a maximally parallel manner. •If at the same time a membrane labelled with his divided by a rule of type (e0) or (f0) and there are objects in this membrane which evolve by means of rules of type (a0), then we suppose that first the evolution rules of type (a0) are used, changing the objects, and then the division is produced. Of course, this process takes only one transition step. •The skin membrane and the output membrane can never divide or dissolve. 3.3. Polarizationless P systems with active membranes and minimal cooperation in object evolution rules Next, minimal cooperation in objects evolution rules is introduced in the framework of polarizationless P system with active membranes. The term “minimal cooperation” is used in the following sense: the left-hand side of such rules consists of at most two symbols and its length is greater than or equal to the right-hand side. Definition 2. A polarizationless P system with active membranes and minimal cooperation in object evolution rules is a polarizationless P system with active membranes such that the object evolution rules are of the following forms: [a→c]h,[a b →c]h,[a b →c d ]h Polarizationless P Syst. with Active Membr.: Computational Complexity Aspects 113 for h∈Hand a, b, c, d ∈Γ. Let us notice that in these systems, send-in communication rules, send-out communication rules, dissolution rules and division rules are non-cooperative rules. In polarizationless P system with active membranes and minimal cooperation, the rules are applied according to the same principles described in Subsection 3.2. 3.4. Recognizer membrane systems In this section, a membrane system designates a P system of one of the different variants considered in the paper. Definition 3. We say that a membrane system Πis a recognizer membrane system if the following holds: (I) The working alphabet Γof Πhas two distinguished objects yes and no. (II) There exists an (input) alphabet Σstrictly contained in Γ. (III) The initial multisets M1, . . . , Mqof Πare multisets over Γ\Σ. (IV) There exists a distinguished membrane called the input membrane. (V) The output region iout is the environment. (VI) All computations halt. (VII) If Cis a computation of Π, then either object yes or object no (but not both) must have been released into the environment, and only at the last step of the computation. In recognizer membrane systems any computation is either an accepting computation (when object yes is released into the environment at the last step) or a rejecting computation (when object no is released into the environment at the last step) For each finite multiset mover the input alphabet Σ, the computation of the system Πwith input mstarts from the configuration obtained by adding the input multiset mto the contents of the input membrane, in the initial configuration of Π. Therefore, in this kind of systems we have an initial configuration associated with each input multiset m(over the input alphabet Σ) . We denote by Π + mthe membrane system Πwith input multiset m. We also use the following notations: • AM0(γ, δ)where γ∈ {−d, +d}and δ∈ {−n, +n}, is the class of all recognizer polarizationless P systems with active membranes. • AM0 mc(γ, δ)where γ∈ {−d, +d}and δ∈ {−n, +n}, is the class of all recognizer polarizationless P systems with active membranes with minimal cooperation in object evolution rules. The meaning of parameters γand δis the following: •if γ= +dthen dissolution rules are permitted, •if γ=−dthen dissolution rules are forbbiden, 114 L. Valencia,D. Orellana,M. A. Martínez,A. Riscos,M. J. Pérez •if δ= +nthen division rules for elementary and non–elementary membranes are permitted, •if δ=−nthen only division rules for elementary membranes are permitted. 3.5. Polynomial complexity classes of recognizer membrane systems Next, let us recall the concept of efficient solvability by means of a family of recognizer membrane systems (see [12] for more details). Definition 4. A decision problem X= (IX,ΘX)is solvable in polynomial time by a family Π={Π(n)|n∈N}of recognizer membrane systems, in a uniform way, denoted by X∈PMCR, if the following statements hold: •the family Πis polynomially uniform by Turing machines, that is, there exists a deterministic Turing machine working in polynomial time which constructs the system Π(n)from n∈N; •there exists a pair (cod, s)of polynomial-time computable functions over the set IXsuch that: ∗for each instance u∈IX,s(u)is a natural number and cod(u)is an input multiset of the system Π(s(u)); ∗for each n∈N,s−1(n)is a finite set; ∗the family Πis polynomially bounded with regard to (X, cod, s), that is, there exists a polynomial function p, such that for each u∈IXevery computation of Π(s(u)) + cod(u)is halting and it performs at most p(|u|) steps; ∗the family Πis sound with regard to (X, cod, s), that is, for each u∈IX, if there exists an accepting computation of Π(s(u))+cod(u), then θX(u)=1; ∗the family Πis complete with regard to (X, cod, s), that is, for each u∈IX, if θX(u)=1, then every computation of Π(s(u)) + cod(u)is an accepting one. The polynomial complexity class PMCRis closed under polynomial-time reduction and under complement [13]. At the beginning of 2005, Gh. Păun proposed a problem (problem Ffrom [10]) which can be formally formulated as follows: “Is the complexity class PMCAM0(+d,−n)equal to P?” That is, in order to provide polynomial time solutions to computationally hard problems by means of families of P systems with active membranes (using only division rules for elementary membranes), can the polarizations be completely avoided? Gh. Păun wrote “my feeling is that this is not possible”, that is, his guess is that PMCAM0(+d,−n)=P. By using the dependency graph technique it has been shown that if dissolution rules are forbidden, then only tractable problems can be solved in an efficient way Polarizationless P Syst. with Active Membr.: Computational Complexity Aspects 115 by families of polarizationless P systems with active membranes even using division rules for elementary and non-elementary membranes, that is, PMCAM0(−d,+n)=P (see [6] for details). In some sense, a partial affirmative answer to Păun’s conjecture is obtained in the case that dissolution rules are forbidden. On the other hand, a family of recognizer polarizationless P systems with active membranes using dissolution rules and division for non–elementary membranes solving QBF-SAT in a uniform way and in a linear time, has been provided (see [3] for details), and thus PSPACE ⊆PMCAM0(+d,+n). In this manner, assuming that P6=NP, we have a partial negative answer to Păun’s conjecture: computationally hard problems can be efficiently solved avoiding polarizations, but the answer is partial in the sense that division rules for non–elementary membranes have been considered. From the previous result we deduce that when dealing with polarizationless P systems with active membranes including non–elementary membranes division, dissolution rules constitute a key ingredient to solve hard problems efficiently. 4. On efficiency of membrane systems from AM0 mc(−d, −n) In this section, we show that the syntactical ingredient of minimal cooperation in polarizationless P systems with active membranes (without dissolution and allowing only division for elementary membranes) is enough to solve computationally hard problems in an efficient way. 4.1. A uniform polynomial time solution to SAT problem in AM0 mc(−d, −n) Next, a polynomial time solution to SAT problem, a well known NP-complete problem [5], by a family Π={Π(t)|t∈N} of recognizer P systems from AM0 mc(−d, −n)is provided. Each system Π(t)will process any Boolean formula ϕin conjunctive normal form with nvariables and p clauses, where t=hn, pi, provided that the appropriate input multiset cod(ϕ)is supplied to the system (through the corresponding input membrane). Let us recall that the polynomial–time computable function (the pair function) hn, pi= ((n+p)(n+p+ 1)/2) + n is a primitive recursive and bijective function from N×Nto N. Then, for each n, p ∈N, we consider the recognizer P system Π(hn, pi) = (Γ,Σ, H, µ, M1,M2,R, iin, iout) from AM0 mc(−d, −n), defined as follows: 122 L. Valencia,D. Orellana,M. A. Martínez,A. Riscos,M. J. Pérez Acknowledgement Luis Valencia-Cabrera acknowledges the support of the projects Grant No. 61033003 and 61320106005 of the National Natural Science Foundation of China. References [1] A. Alhazov, L. Pan, Polarizationless P systems with active membranes. Grammars 7(2004), 141–159. [2] A. Alhazov, L. Pan, Gh. Păun, Trading polarizations for labels in P systems with active membranes. Acta Informaticae 41 (2004) 2–3, 111–144. [3] A. Alhazov, M. J. Pérez-Jiménez, Uniform solution of QSAT using polarizationless active membranes. In: J. Durand-Lose, M. Margenstern (eds.), Machines, Computations, and Universality. LNCS 4664, Springer-Verlag, 2007, 122–133. [4] T. H. Cormen, C. E. Leiserson, R. L. Rivest,An Introduction to Algorithms. The MIT Press, Cambridge, Massachussets, 1994. [5] M. R. Garey, D. S. Johnson,Computers and Intractability. A guide to the theory of NP-completeness. W. H. Freeman and Company, New York, 1979. [6] M. A. Gutiérrez-Naranjo, M. J. Pérez-Jiménez, A. Riscos-Núñez, F. J. Romero-Campero, On the power of dissolution in P systems with active membranes. In: R. Freund, Gh. Păun, G. Rozenberg, A. Salomaa (eds.), Membrane Computing, 6th International Workshop, WMC 2005, Vienna, Austria, July 18–21, 2005, Revised Selected and Invited Papers. LNCS 3850, Springer-Verlag, 2006, 224–240. [7] M. A. Gutiérrez-Naranjo, M. J. Pérez-Jiménez, A. Riscos-Núñez, F. J. Romero-Campero, A. Romero-Jiménez, Characterizing tractability by cell-like membrane systems. In: K. G. Subramanian, K. Rangarajan, M. Mukund (eds.), Formal models, languages and applications. World Scientific, Singapore, 2006, 137–154. [8] Gh. Păun, Attacking NP-complete problems. In: I. Antoniou, C. Calude, M. J. Dinneen (eds.), Unconventional Models of Computation, UMC’2K Springer-Verlag, 2000, 94–115. [9] Gh. Păun, P systems with active membranes: Attacking NP-complete problems. Journal of Automata, Languages and Combinatorics 6(2001) 1, 75–90. [10] Gh. Păun, Further twenty six open problems in membrane computing. In: M. A. Gutiérrez, A. Riscos, F. J. Romero, D. Sburlan (eds.), Proceedings of the Third Brainstorming Week on Membrane Computing. Report RGNC 01/04, Fénix Editora, Sevilla, 2005, 249–262. [11] Gh. Păun, G. Rozenberg, A. Salomaa (eds.), The Oxford Handbook of Membrane Computing. Oxford University Press, Oxford, 2010. [12] M. J. Pérez-Jiménez, An approach to computational complexity in Membrane Computing. In: G. Mauri, Gh. Păun, M. J. Pérez-Jiménez, G. Rozenberg, A. Salomaa (eds.), Membrane Computing, International Workshop, WMC5, Milano, Italy, 2004, Selected Papers. LNCS 3365, Springer-Verlag, 2005, 85–109. [13] M. J. Pérez-Jiménez, A. Romero-Jiménez, F. Sancho-Caparrini, A polynomial complexity class in P systems using membrane division. Journal of Automata, Languages and Combinatorics 11 (2006) 4, 423–434. Polarizationless P Syst. with Active Membr.: Computational Complexity Aspects 123 [14] A. E. Porreca, G. Mauri, C. Zandron, Complexity classes for membrane systems. Informatique théorique et applications,40 (2006) 2, 141–162. [15] P. Sosík, A. Rodríguez-Patón, P systems with active membranes characterize PSPACE. In: Ch. Mao, T. Yokomori (eds.), DNA Computing, 12th International Meeting on DNA Computing, DNA12, Seoul, 2006, Revised Selected Papers. LNCS 4287, Springer-Verlag, 2006, 33–46. (Received: June 2, 2016; revised: August 8, 2016)