Minimal cooperation in polarizationless P systems with active membranes

Minimal cooperation in polarizationless P systems with active membranes Luis Valencia-Cabrera, David Orellana-Mart´ın, Agust´ın Riscos-N´u˜nez, Mario J. P´erez-Jim´enez Research Group on Natural Computing Department of Computer Science and Artificial Intelligence Universidad de Sevilla Avda. Reina Mercedes s/n, 41012 Sevilla, Spain E-mail: {lvalencia, dorellana, ariscosn, marper}@us.es Summary. P systems with active membranes is a well developed framework in the field of Membrane Computing. Using evolution, communication, dissolution and division rules, we know that some kinds of problems can be solved by those systems, but taking into account which ingredients are used. All these rules are inspired by the behavior of living cells, who “compute” with their proteins in order to obtain energy, create components, send information to other cells, kill themselves (in a process called apoptosis), and so on. But there are other behaviors not captured in this framework. As mitosis is simulated by division rules (for elementary and non-elementary membranes), meiosis, that is, membrane fission inspiration is captured in separation rules. It differs from the first in the sense of duplication of the objects (that is, in division rules, we duplicate the objects not involved in the rule, meanwhile in separation rules we divide the content of the original membrane into the new membranes created). Evolution rules simulate the transformation of components in membranes, but it is well known that elements interact with another ones in order to obtain new components. Cooperation in evolution rules is considered. More specifically, minimal cooperation (in the sense that only two objects can interact in order to create one or two objects). Key words: Membrane Computing, Active membranes, Minimal cooperation, Mitosis, Computational Complexity, The Pversus NP problem. 1 Introduction Membrane Computing is a distributed parallel computing paradigm inspired by the way the living cells process chemical substances, energy and information. The processor units 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 328 L. Valencia, D. Orellana, A. Riscos, M.J. P´erez between cells and 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 a chemical substance through a biological membrane is often implemented by an interaction between the membrane itself and the protein channels present in it. During this interaction, both the chemical substance and the membrane can be modified, at least locally. Mitosis is a process by which two or more cells are produced/generated from one cell that could be considered as the “mother”. Several cell division inspired mechanisms were introduced in Membrane Computing. Specifically, P systems with active membranes [9] incorporates 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 new objects, while the remaining objects are duplicated in both newly created membranes. These models are 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 nonelementary membranes. This paper deals with P systems with active membranes where electrical charges are removed. The paper is organized as follows. Next section briefly describes some preliminaries in order to make the work self-contained. In Section 3, syntax and semantics of polarizationless P systems with active membranes by using membrane division rules or membrane separation rules are introduced, and minimal cooperation in object evolution rules is considered. Definition of Recognizer membrane systems is recalled in Section 4, as a framework to provide efficient solutions to decision problems. The computational efficiency of polarizationless P systems with active membranes, division rules, minimal cooperation and without dissolution rules is established in Section 5 by providing a uniform polynomial-time solution to SAT problem. A formal verification of this result is presented in Section 6. Next section is dedicated to show the limits of the computational efficiency of the polarizationless P systems with active membranes, separation rules and minimal cooperation in object evolution rules. The paper ends with some open problems and concluding remarks. 2 Preliminaries An alphabet Γis a non-empty set and their 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 that it contains. The empty string (with length 0) is denoted by λ. The Minimal cooperation in polarizationless P systems with active membranes 329 set of all strings 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 Γ. Let m1= (Γ, f1), m2= (Γ, f2) be 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∈Γ. We say that m1is contained in m2and we denote it by m1⊆m2, if f1(x)≤f2(x) for each x∈Γ. The relative complement of m2in m1, denoted by m1\m2, is the multiset (Γ, g), where g(x) = f1(x)−f2(x) if f1(x)≥f2(x), and g(x) = 0 otherwise. 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 {x, y}(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 [3] for details). 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 [12] for details). 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, such capability is not enough to efficiently solve NP–complete problems, unless P=NP (see [6] 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. Such variant was first introduced by Gh. P˘aun [10] and it has associated electrical charges with membranes but the rules are non-cooperative and there are not priorities. Nevertheless, the class of all problems solvable in polynomial time and in a uniform way by means of families of P systems with active membranes which use division for elementary and non-elementary membranes contains class PSPACE and it is contained in class 330 L. Valencia, D. Orellana, A. Riscos, M.J. P´erez EXP [16]. Thus, in order to provide efficient solutions to computationally hard problems, this framework seems to be too powerful from the computational complexity point of view. In this paper, electrical charges are removed from P systems with active membranes. Two different ways of producing an exponential number of membranes in linear time will be considered: division and separation rules (abstractions of mitosis and membrane fission processes, respectively). 3.1 Polarizationless P system with active membranes: Syntax Definition 1. A polarizationless P system with active membranes and membrane division of degree q≥2is 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 finite 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 not the label of the root of µ(division rules for elementary membranes). (f0) [ [ ]h0[ ]h1]h→[ [ ]h0]h[ [ ]h1]h, where h∈H\ {iout}is not the label of the root of µand h0, h1∈H(division rules for non–elementary membranes). •iout ∈H∪ {env}, where env /∈Hand in the case iout ∈H,iout is the label of a leaf of µ. Definition 2. A polarizationless P system with active membranes and membrane separation of degree q≥2is a tuple Π= (Γ, Γ0, Γ1, H, H0, H1, µ, 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; • {Γ0, Γ1}is a partition of Γand {H0, H1}is a partition of H; •µis a labelled rooted tree (called membrane structure) consisting of qnodes injectively labeled by elements of H; • M1,...,Mqare finite 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). Minimal cooperation in polarizationless P systems with active membranes 331 (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→[Γ0]h[Γ1]hfor h∈H\ {iout},a∈Γand his not the label of the root of µ(separation rules for elementary membranes). (f0) [ [ ]h0[ ]h1]h→[Γ0[ ]h0]h[Γ1[ ]h1]h, where h∈H\ {iout}is not the label of the root of µ,h0∈H0and h1∈H1(separation rules for non–elementary membranes). •iout ∈H∪ {env}, where env /∈Hand in the case iout ∈H,iout is the label of a leaf of µ. A polarizationless P system with active membranes of degree q≥2, 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; and (c) iout ∈H∪ {env}indicates the output region. We use the term region ito 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, otherwise, the membrane is said to be non-elementary. 3.2 Polarizationless P system 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 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]hfor 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]hfor 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[ ]hfor h∈H,a, b ∈Γis applicable to a configuration Ctat an instant t, if there exists a membrane labelled by hin Ct such 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→bfor h∈H\ {iout},a, b ∈Γis applicable to a configuration Ctat an instant t, if there exists a membrane labelled by hin 332 L. Valencia, D. Orellana, A. Riscos, M.J. P´erez Ct, different from the skin membrane and 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). A division rule [ a]h→[b]h[c]hfor h∈H\ {iout}, a, b, c ∈Γ, 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 the output region, such that it contains object a. When applying a division rule [a]h→[b]h[c]hto 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. A division rule [ [ ]h0[ ]h1]h→[ [ ]h0]h[ [ ]h1]his applicable to a configuration Ctat an instant t, if there exists a membrane labelled by hin Ct, different from the skin membrane and the output region, which contains a membrane labelled by h0and another membrane labelled by h1. When applying such a division rule to a membrane labelled by hin a configuration Ct, the membrane with label his divided into two membranes with the same label; the first copy inherits membrane h0with its contents, and the second copy inherits membrane h1with its contents. Besides, if the membrane labelled by hcontains more membranes other than those with the labels h0,h1, then such membranes are duplicated so that they become part of the contents of both new copies of the membrane h. A separation rule [ a]h→[Γ0]h[Γ1]hfor h∈H,a∈Γ, is applicable to a configuration Ctat an instant t, if there exists a membrane labelled by hin Ct, different from the skin membrane and the output region, such that it contains object a. When applying such a rule, the membrane is separated into two membranes with the same label; at the same time, object ais consumed and the multiset of objects contained in membrane hgets distributed: the objects from Γ0are placed in the first membrane, those from Γ1are placed in the second membrane. A separation rule [ [ ]h0[ ]h1]h→[Γ0[ ]h0]h[Γ1[ ]h1]h, where h, h0, h1are labels such that h0∈H0and h1∈H1, is applicable to a configuration Ctat an instant t, if there exists a membrane labelled by hin Ct, different from the skin membrane and the output region, such that it contains a membrane labelled by h0and another membrane labelled by h1. When applying such a separation rule to a membrane labelled by hin a configuration Ct, that membrane is separated into two membranes with the same label, in such a way that the contents (multiset of objects and inner membranes) are distributed as follows: The first membrane receives the multiset of objects from Γ0, and all inner membranes whose label belongs to H0; and the second membrane receives the multiset of objects from Γ1, and all inner membranes whose label belongs to H1. In polarizationless P systems with active membranes, the rules are applied according to the following principles: Minimal cooperation in polarizationless P systems with active membranes 333 •The rules associated with membranes labelled with hare used for all copies of this membrane. •At one transition step, one object can be used by only one rule (chosen in a non–deterministic way). •At one transition step, a membrane can be the subject of only one rule of types (b0)–(f0), and then it is applied at most once. •Object evolution rules can be simultaneously applied to a membrane with one rule of types (b0)–(f0). 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 (or the separation) is produced. Of course, this process takes only one transition step. •The skin membrane and the output membrane can never get divided, separated, nor dissolved. 3.3 Polarizationless P systems with active membranes and minimal cooperation in object evolution rules Next, we incorporate cooperation in object evolution rules of polarizationless P systems with active membranes. In this paper, we use minimal cooperation in the following sense: the left-hand side of each object evolution rules has at most two objects, and the length of the right-hand side cannot be greater than the length of the left-hand side. Consequently, in contrast with the usual object evolution rules in P systems with active membranes, by applying these rules with minimal cooperation the number of objects of the system does not increase. Definition 3. A polarizationless P system with active membranes, division or separation rules and minimal cooperation in object evolution rules is a polarizationless P system with active membranes and division or separation rules such that the object evolution rules are of the following form: [a→c]h,[a b →c]h,[a b →c d ]h for h∈Hand a, b, c, d ∈Γ. The semantics of these variants are analogous to the semantics of polarizationless P systems with active membranes. 4 Recognizer membrane systems In what follows, a membrane system denotes a P system of any of the different variants considered in the previous section. 334 L. Valencia, D. Orellana, A. Riscos, M.J. P´erez Definition 4. We say that a membrane system Πis a recognizer membrane system if the following holds: 1. The working alphabet Γof Πhas two distinguished objects yes and no. 2. Σis an (input) alphabet strictly contained in Γ. 3. The initial multisets M1,...,Mqof Πare finite multisets over Γ\Σ. 4. There exists a distinguished membrane labelled by iin called the input membrane. 5. The output region iout is the environment. 6. All computations halt. 7. 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. 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 Π. We denote it by Π+m. Therefore, we have an initial configuration associated with each input multiset m(over the input alphabet Σ) in this kind of systems. We use the following notations: • DAM0(γ, δ) where γ∈ {−d, +d}and δ∈ {−n, +n}, is the class of all recognizer polarizationless P systems with active membranes and division rules. • DAM0 mc(γ, δ) where γ∈ {−d, +d}and δ∈ {−n, +n}, is the class of all recognizer polarizationless P systems with active membranes, minimal cooperation in object evolution rules and division rules. • SAM0(γ, δ) where γ∈ {−d, +d}and δ∈ {−n, +n}, is the class of all recognizer polarizationless P systems with active membranes and separation rules. • SAM0 mc(γ, δ) where γ∈ {−d, +d}and δ∈ {−n, +n}, is the class of all recognizer polarizationless P systems with active membranes, minimal cooperation in object evolution rules and separation rules. The meaning of parameters γand δis the following: •if γ= +dthen dissolution rules are permitted. •if γ=−dthen dissolution rules are forbidden. •if δ= +nthen division rules for elementary and non–elementary membranes are permitted. •if δ=−nthen division rules only for elementary membranes are permitted. Let us notice that standard notation in the literature referring to polarizationless P systems with active membranes (AM0(γ, δ)) corresponds, within this new notation, to the class DAM0(γ, δ). Minimal cooperation in polarizationless P systems with active membranes 335 4.1 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 [13] for more details). Definition 5. Let Rbe a class of recognizer membrane systems. We say that a decision problem Xis solvable in polynomial time by a family Π={Π(n)|n∈N} of systems from R, in a uniform way, denoted by X∈PMCR, if the following 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 IX such 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 [14]. 4.2 Known results on polarizationless P systems with active membranes In previous works, membrane systems have been studied in terms of their computational efficiency and different borderlines between efficiency and non-efficiency have been obtained. Each of them provides attractive characterizations of the P6=NP conjecture. In [5], by using the dependency graph technique and the tractability of the reachability problem, the following result has been proved. Theorem 1. P =PMCDAM0(−d,+n) Thus, only problems in class Pcan be solved in polynomial time and in a uniform way by means of families of polarizationless P systems with active membranes making use of division rules for elementary and non-elementary membranes and not using dissolution rules. 342 L. Valencia, D. Orellana, A. Riscos, M.J. P´erez ?a different subset {r1,i, . . . , ri,i}, being r∈ {t , f}. (b) Cn(1) = {α , βn}, and in Cn(2) there are 2nmembranes labelled by 2such that each of them contains the input multiset cod(ϕ), as well as a different subset {R1,1, . . . , Rn,1}, being R∈ {T, F}. Proof. (a) is going to be demonstrated by induction on i. – The base case i= 1 is trivial because at the initial configuration C0we have: C0(1) = {α , β0}and there exists a single membrane labelled by 2 containing cod(ϕ) and the set {a1,1, . . . , an,1}. Then, configuration C0yields configuration C1by applying the rules: [a1,1]2→[t1,1]2[f1,1]2 [ai,1→ai,2]2,for 2 ≤i≤n [β0→β1]1 Thus, C1(1) = {α , β1}and in C1there exist two membranes labelled by 2 such that their contents is cod(ϕ) and the set {a2,2, . . . , an,2}. Also, one of those membranes contains object t1,1and the other one object f1,1. Hence, the result holds for i= 1. – Supposing that, by induction, result is true for i(1 ≤i<n−1); that is, –Ci(1) = {α , βi}. – There are 2imembranes labelled by 2 such that each of them contains ?the input multiset cod(ϕ); ?objects ai+1,i+1, . . . , an,i+1; and ?a different subset {r1,i, . . . , ri,i}, being r∈ {t , f}. Then, configuration Ciyields configuration Ci+1 by applying the rules: [tk,i →tk,i+1 ]2,for 1 ≤k≤i [ai+1,i+1 ]2→[ti+1,i+1 ]2[fi+1,i+1 ]2 [ak,i+1 →ak,i+2 ]2,for i+ 2 ≤k≤n [βi→βi+1 ]1 Therefore, the following holds: –Ci+1(1) = {α , βi+1}. – There are 2i+1 membranes labelled by 2 such that each of them contains ?the input multiset cod(ϕ); ?objects ai+2,i+2, . . . , an,i+2; and ?a different subset {r1,i+1, . . . , ri+1,i+1}, being r∈ {t , f}. Hence, the result holds for i+ 1. In order to prove (b) it is enough to notice that, on the one hand, from (a) configuration Cn−1holds: –Cn−1(1) = {α , βn−1}. – There are 2n−1membranes labelled by 2 such that each of them contains ?the input multiset cod(ϕ); ?object an,n; and ?a different subset {r1,n−1, . . . , rn−1,n−1}, being r∈ {t , f}. Minimal cooperation in polarizationless P systems with active membranes 343 On the other hand, configuration Cn−1yields configuration Cnby applying the rules: [tk,n−1→Tk,1]2,for 1 ≤k≤n−1 [an,n ]2→[Tn,1]2[Fn,1]2 [βn−1→βn]1 Then, we have Cn(1) = {α , βn}, and in Cn(2) there are 2nmembranes labelled by 2 such that each of them contains the input multiset cod(ϕ), as well as a different subset {R1,1, . . . , Rn,1}, being R∈ {T, F }.  6.2 First Checking stage At this stage, we try to determine the clauses satisfied for the truth assignment encoded by each membrane labelled by 2. For that, rules from 2.3 will be applied in such manner that in the j-th step (1 ≤j≤p) of this stage, clause jis checked and an object cjis produced in the case that clause is satisfied. Proposition 2. Let C= (C0,C1,...,Cq)be a computation of the system Π(s(ϕ)) with input multiset cod(ϕ). (a) For each i(1 ≤i≤p−1) at configuration Cn+iwe have the following: –Cn+i(1) = {α , βn+i}. – There are 2nmembranes labelled by 2such that each of them contains ?the input multiset cod(ϕ)p i+1 corresponding to the clauses ci+1, . . . , cp; ?a different subset {R1,i+1, . . . , Rn,i+1}, being R∈ {T , F}encoding a truth assignment for the variables {x1, . . . , xn}; and ?objects cj,i (1 ≤j≤i)such that clause Cjis satisfied by the truth assignment encoded by such a membrane. (b) Cn+p(1) = {α , βn+p}, and in Cn+p(2) there are 2nmembranes labelled by 2 such that each of them contains objects cjsuch that clause Cjis satisfied by the truth assignment encoded by such a membrane. Besides, the multiplicity of object cjrepresents the number of values of the truth assignment making true Cj. Proof. (a) is going to be demonstrated by induction on i. – In order to prove the base case i= 1 let us notice that from the previous proposition we deduce that configuration Cnverifies: Cn(1) = {α , βn}and in Cn(2) there are 2nmembranes labelled by 2 such that each of them contains the input multiset cod(ϕ), as well as a different subset {R1,1, . . . , Rn,1}, being R∈ {T, F}. Besides, configuration Cnyields configuration Cn+1 by applying rule [ βn→βn+1 ]1and rules: 344 L. Valencia, D. Orellana, A. Riscos, M.J. P´erez [Ti,1xi,1→Ti,2c1,1]2 [Ti,1xi,1→Ti,2]2 [Ti,1x∗ i,1→Ti,2]2 [Fi,1xi,1→Fi,2]2 [Fi,1xi,1→Fi,2c1,1]2 [Fi,1x∗ i,1→Fi,2]2                1≤i≤n, 1≤j≤p−1 Thus, the following holds for configuration Cn+1: –Cn+1(1) = {α , βn+1}. – There are 2nmembranes labelled by 2 such that each of them contains ?the input multiset cod(ϕ)p 2corresponding to the clauses c2, . . . , cp; ?a different subset {R1,2, . . . , Rn,2}, being R∈ {T , F}encoding a truth assignment for the variables {x1, . . . , xn}; and ?objects c1,1such that clause C1is satisfied by the truth assignment encoded by such a membrane. Hence, the result holds for i= 1. – Let us assume that by induction hypothesis, the result holds for i(1 ≤i < p−1); that is, –Cn+i(1) = {α , βn+i}. – There are 2nmembranes labelled by 2 such that each of them contains ?the input multiset cod(ϕ)p i+1 corresponding to the clauses ci+1, . . . , cp; ?a different subset {R1,i+1, . . . , Rn,i+1}, being R∈ {T , F}encoding a truth assignment for the variables {x1, . . . , xn}; and ?objects cj,i (1 ≤j≤i) such that clause Cjis satisfied by the truth assignment encoded by such a membrane. Besides, configuration Cn+iyields configuration Cn+(i+1) by applying rule [βn+i→βn+(i+1) ]1and rules: [Ti,i+1 xi,i+1 →Ti,i+2 ci+1,i+1 ]2 [Ti,i+1 xi,i+1 →Ti,i+2 ]2 [Ti,i+1 x∗ i,i+1 →Ti,i+2 ]2 [Fi,i+1 xi,i+1 →Fi,2]2 [Fi,i+1 xi,i+1 →Fi,i+2 ci+1,i+1 ]2 [Fi,i+1 x∗ i,i+1 →Fi,i+2 ]2 [cj,i −→ cj,i+1 ]2: 1 ≤j≤i Thus, the following holds for configuration Cn+(i+1): –Cn+(i+1)(1) = {α , βn+(i+1)}. – There are 2nmembranes labelled by 2 such that each of them contains ?the input multiset cod(ϕ)p i+2 corresponding to the clauses ci+2, . . . , cp; ?a different subset {R1,i+2, . . . , Rn,i+2}, being R∈ {T , F}encoding a truth assignment for the variables {x1, . . . , xn}; and ?objects cj,i+1 (1 ≤j≤i+1) such that clause Cjis satisfied by the truth assignment encoded by such a membrane. Hence, the result holds for i+ 1. Minimal cooperation in polarizationless P systems with active membranes 345 In order to prove (b) it is enough to notice that, on the one hand, from (a) configuration Cn+p−1verifies the following: –Cn+p−1(1) = {α , βn+p−1}. – There are 2nmembranes labelled by 2 such that each of them contains ?the input multiset cod(ϕ)p pcorresponding to the clause cp; ?a different subset {R1,p, . . . , Rn,p}, being R∈ {T , F }encoding a truth assignment for the variables {x1, . . . , xn}; and ?objects cj,p−1(1 ≤j≤p−1) such that clause Cjis satisfied by the truth assignment encoded by such a membrane. On the other hand, configuration Cn+p−1yields configuration Cn+pby applying rule [ βn→βn+1 ]1and rules: [Ti,p xi,p →cp]2 [Ti,p xi,p →# ]2 [Ti,p x∗ i,p →# ]2 [Fi,p xi,p →# ]2 [Fi,p xi,p →cp]2 [Fi,p x∗ i,p →# ]2                1≤i≤n [cj,p−1−→ cj]2: 1 ≤j≤p−1 Thus, configuration Cn+pholds: Cn+p(1) = {α , βn+p}and in Cn+p(2) there are 2n membranes labelled by 2 such that each of them contains objects cjsuch that clause Cjis satisfied by the truth assignment encoded by such a membrane. Besides, the multiplicity of object cjrepresents the number of values of the truth assignment making true Cj.  6.3 Second Checking stage At this stage, we try to determine if some truth assignment encoded by a membrane labelled by 2 satisfied all clauses of the input formula. For that, rules from 2.4 will be applied in such manner that object dj(2 ≤j≤p) is produced in the case clauses c1, . . . , cjall satisfied. Then, the input formula is satisfied by the truth assignment encoded by a membrane labelled by 2 if and only if object dpappears in that membrane. This stage spends p−1 computation steps. Proposition 3. Let C= (C0,C1,...,Cq)be a computation of the system Π(s(ϕ)) with input multiset cod(ϕ). (a) For each i(1 ≤i≤p−1) at configuration Cn+p+iwe have the following: –Cn+p+i(1) = {α , βn+p+i}. – There are 2nmembranes labelled by 2such that each of them contains objects di+1 if and only if the truth assignment encoded in that membrane, makes true clauses C1, . . . , Ci+1. 346 L. Valencia, D. Orellana, A. Riscos, M.J. P´erez (b) ϕis satisfiable if and only if at configuration Cn+2p−1there exists some membrane labelled by 2 which contains some object dp. Proof. (a) is going to be demonstrated by induction on i. – In order to prove the base case i= 1, let us notice that from the previous proposition we deduce that configuration Cn+pverifies: Cn+p(1) = {α , βn+p} and in Cn+p(2) there are 2nmembranes labelled by 2 such that each of them contains objects cjsuch that clause Cjis satisfied by the truth assignment encoded by such a membrane. Besides, the multiplicity of object cjrepresents the number of values of the truth assignment making true Cj. Configuration Cn+pyields configuration Cn+p+1 by applying the rules: [c1c2→d2]2 [βn+p→βn+p+1 ]1 Thus, in configuration Cn+p+1 the following holds: –Cn+p+1(1) = {α , βn+p+1}. – There are 2nmembranes labelled by 2 such that each of them contains objects d2if and only if the truth assignment encoded in that membrane, makes true clauses C1and C2. Hence, the result holds for i= 1. – Supposing that, by induction, result is true for i(1 ≤i<n−1); that is, –Cn+p+i(1) = {α , βn+p+i}. – There are 2nmembranes labelled by 2 such that each of them contains objects di+1 if and only if the truth assignment encoded in that membrane, makes true clauses C1, . . . , Ci+1. Then, configuration Cn+p+iyields configuration Cn+p+(i+1) by applying the rules: [ci+1 ci+2 →d2]2 [βn+p+i→βn+p+(i+1) ]1 Thus, in configuration Cn+p+(i+1) the following holds: –Cn+p+(i+1)(1) = {α , βn+p+(i+1)}. – There are 2nmembranes labelled by 2 such that each of them contains objects di+2 if and only if the truth assignment encoded in that membrane, makes true clauses C1, . . . , Ci+2. Hence, the result holds for i+ 1. In order to proof (b), let us note that formula ϕis satisfiable if and only if there exists a truth assignment σmaking true ϕ, that is, making true clauses C1, . . . , Cp. From (a) we deduce that ϕis satisfiable if and only at configuration Cn+2p−1there exists some membrane labelled by 2 which contains some object dp.  6.4 Output stage The output phase starts at the (n+ 2p)-th step, and takes exactly four steps. Minimal cooperation in polarizationless P systems with active membranes 347 –Affirmative answer: if the input formula ϕof SAT problem is satisfiable then at least one of the truth assignments from a membrane with label 2 has satisfied all clauses. Thus, a copy of object dpwill appear in that membrane at configuration Cn+2p−1. Then, by applying the last rule from 2.4 and rule [ βn+2p−1−→ βn+2p]1, objects γand βn+2pare produced in the skin membrane. At the next step, by applying rules [ α γ −→ γ0]1and [ βn+2p−→ β0]1, objects γ0and β0are produced in the skin membrane. At the next step, by applying rule [γ0−→ γ00 ]1, object γ00 is produced in the skin membrane (let us notice that object β0cannot interact with α). Finally, at the step n+ 2p+ 3 by applying rule [ γ00 ]1−→ yes [ ]1, object yes is sent out to the environment and the computation halts. –Negative answer: if the input formula ϕof SAT problem is not satisfiable then none of the truth assignments encoded by a membrane with label 2 makes the formula ϕtrue. Thus, object dpdoes not appear in any membrane with label 2. Thus, at step n+ 2p, only rule [ βn+2p−1−→ βn+2p]1is applicable to Cn+2p−1. Then, Cn+2p(1) = {α , βn+2p}. At the next step, by applying rule [βn+2p−→ β0]1we have Cn+2p+1(1) = {α , β0}. Then rule [ α β0−→ β00 ]1 produces an object β00 in the skin membrane. Finally, at step n+ 2p+ 3 by applying rule [ β00 ]1−→ no [ ]1releases an object no at the environment. Then, the computation halts and the answer of the computation is no. 6.5 Result Theorem 4. SAT ∈PMCDAM0 mc(−d,−n). Proof: The family of P systems previously constructed verifies the following: (a) Every system of the family Πis a recognizer P system from DAM0 mc(−d, −n). (b) The family Πis polynomially uniform by Turing machines because for each n, p ∈N, the rules of Π(hn, pi) of the family are recursively defined from n, p ∈N, and the amount of resources needed to build an element of the family is of a polynomial order in nand p, as shown below: – Size of the alphabet: 5np+3n2−5n+p2−3p+6 2+n+4p+9 ∈Θ((max{n, p})2). – Initial number of cells: 2 ∈Θ(1). – Initial number of objects in cells: n+ 2 ∈Θ(n). – Number of rules: 6np +3n2+p2+3n+5p 2+ 6 ∈Θ((max{n, p})2). – Maximal number of objects involved in any rule: 4 ∈Θ(1). (c) The pair (cod, s) of polynomial–time computable functions defined fulfill the following: for each input formula ϕof SAT problem, s(ϕ) is a natural number, cod(ϕ) is an input multiset of the system Π(s(ϕ)), and for each n∈N,s−1(n) is a finite set. (d) The family Πis polynomially bounded: indeed for each input formula ϕof SAT problem, the deterministic P system Π(s(ϕ)) + cod(ϕ) takes exactly, in n+ 2p+ 3 steps, being nthe number of variables of ϕand pthe number of clauses. 348 L. Valencia, D. Orellana, A. Riscos, M.J. P´erez (e) The family Πis sound with regard to (X, cod, s): indeed for each input formula ϕ, if the computation of Π(s(ϕ)) + cod(ϕ) is an accepting computation, then ϕis satisfiable (see Section 6). (f) The family Πis complete with regard to (X, cod, s): indeed, for each input formula ϕsuch that it is satisfiable, the accepting computation of Π(s(ϕ)) + cod(ϕ) is an accepting computation (see Section 6). Therefore, the family Πof P systems previously constructed solves SAT problem in polynomial time and in a uniform way, according to Definition 5.  Corollary 2. NP ∪co −NP ⊆PMCDAM0 mc(−d,−n) Proof: It suffices to notice that SAT problem is a NP-complete problem, SAT∈PMCDAM0 mc(−d,−n), and the complexity class PMCDAM0 mc(−d,−n)is closed under polynomial-time reduction and under complement.  7 Limits on efficient computations in SAM0 mc(+d, +n) In this section we study the computational efficiency of polarizationless P systems with active membranes, dissolution rules and minimal cooperation when separation rules (for elementary and non-elementary membranes) are considered as a mechanism to generate an exponential workspace in linear time. Specifically, we will show that these kind of P systems can only solve problems in class Pin an efficient way. The proof is inspired on a similar result, obtained in the framework of cell-like P systems with symport/antiport rules and cell separation [7]. Let Π= (Γ, Γ0, Γ1, Σ, H, H0, H1, µ, M1,...,Mq,R, iin, iout) be a recognizer P system from SAM0 mc(+d, +n). In what follows we use the concepts of notation from [15]. •We denote by p(i) (resp., ch(i)) the label of the parent (resp., a child) of the membrane labelled by i, the parent of the skin membrane is the environment (we write p(1) = 0). We denote by RE(resp., RC,RDand RS) the set of evolution rules (resp., communication, dissolution and separation rules) of Π. We will fix total orders in RE,RC,RDand RS. •Let Cbe a computation of Π, and Ctan arbitrary configuration of C. With respect to the number of objects of the system, let us notice that by applying a single rule, this number remains unchanged or decreases by one. Thus, the total number of objects in Ctis, at most, M, being M=|M0+... +Mq|. With respect to the number of membranes of the system, by applying a separation rule for elementary membranes, an object is removed from the system, no new objects are produced and a new membrane is created. Thus, at most Mmembranes can be produced by means of this process. Also, by applying a separation rule for non-elementary membranes, the number of objects remains Minimal cooperation in polarizationless P systems with active membranes 349 unchanged but a new membrane is created (when such a rule is applied to a non-elementary membrane, it cannot be applied to that membrane anymore). In this way, no more than q−2 new membranes can be generated. Consequently, q+M+ (q−2) = M+ 2q−2 is an upper bound of the total number of membranes at Ct. •In order to identify the membranes created by the application of a separation rule, we modify the labels of the new membranes in the following recursive manner: – The label of a membrane will be a pair (i, σ) where 0 ≤i≤qand σ∈ {0,1}∗. At the initial configuration, the labels of the membranes are (1, λ),...,(q, λ). The label of the environment is denoted by (0, λ). – If a separation rule is applied to a membrane labelled by (i, σ), then the new created membranes will be labelled by (i, σ0) and (i, σ1), respectively. Membrane (i, σ0) will only contain the objects of membrane (i, σ) which belong to Γ0, and membrane (i, σ1) will only contain the objects of membrane (i, σ) which belong to Γ1. Only elementary membranes can be separated, so if a membrane iis non-elementary then we denote it by the label (i, λ). – If an object evolution rule or a communication rule is applied to a membrane labelled by (i, σ), then after the application of the rule, the membrane keeps its label. •Let us notice that the number of labels we need to identify all membranes appearing along any computation of a P system from SAM0 mc(+d, +n) is of the order O(M+q). •A configuration Ctof a P system from SAM0 mc(+d, +n) is described by the current membrane structure and the multisets of labelled objects of the type {(a, i, σ) : a∈Γ, 0≤i≤q, σ ∈ {0,1}∗} The expression (a, i, σ)∈ Ctmeans that object abelongs to membrane labelled by (i, σ). •Let r= [ab →c]h∈ R be an object evolution rule of Π. We denote by n·LHS(r, (i, σ)), n∈N, the multiset of labelled objects (a, i, σ)n(b, i, σ)nWe denote by n·RHS(r, (i, σ)) the multiset of labelled objects (c, i, σ)nproduced by applying ntimes rule rover membrane (i, σ). Similarly these concepts are defined for object evolution rules of the forms [ ab →cd ]hand [ a→c]h. •Let r= [a]h→b[ ]h∈ R be a send-out communication rule of Π. We denote by LHS(r, (i, σ)) the labelled object (a, i, σ). We denote by RHS(r, (i, σ)) the labelled object (b, p(i), τ) produced by applying rule rover membrane (i, σ), where (p(i), τ) is the parent of membrane (i, σ). •Let r=a[ ]h→[b]h∈ R be a send-in communication rule of Π. We denote by LHS(r, (i, σ)) the labelled object (a, p(i), τ), where (p(i), τ) is the parent of membrane (i, σ). We denote by RHS(r, (i, σ)) the labelled object (b, i, σ) produced by applying rule rover membrane (i, σ). •Let Ctis a configuration of Π, we denote by Ct+{(x, i, σ)/σ0}the multiset obtained by replacing in Ctevery occurrence of (x, i, σ) by (x, i, σ0). Besides, 350 L. Valencia, D. Orellana, A. Riscos, M.J. P´erez Ct+m(resp., Ct\m) is used to denote that a multiset mof labelled objects is added (resp., removed) to the configuration. Next, we provide a deterministic algorithm Aworking in polynomial time that receives as input a recognizer P system Πfrom SAM0 mc(+d, +n) together with an input multiset mof Π. Then algorithm Areproduces the behaviour of a single computation of such system. The pseudocode of the algorithm Ais described as follows: Input: A P system Πfrom SAM0 mc(+d, +n)and an input multiset mof Π Initialization stage : the initial configuration C0of Π+m t←0 while Ctis a non-halting configuration do Selection stage : Input Ct, Output (C0 t, A) Execution stage : Input (C0 t, A), Output Ct+1 t←t+ 1 end while Output: Yes if Ctis an accepting configuration, No otherwise The selection stage and the execution stage implement a transition step of a recognizer P system Π. Specifically, the selection stage receives as input a configuration Ctof Πat an instant t. The output of this stage is a pair (C0 t, A), where Aencodes a multiset of rules selected to be applied to Ct, and C0 tis the configuration obtained from Ctonce the labelled objects corresponding to the application of rules from Ahave been consumed. The execution stage receives as input the output (C0 t, A) of the selection stage, and the output is the next configuration Ct+1 of Ct. Specifically, at this stage, configuration C0 tyields configuration Ct+1 by adding the labelled objects produced by the application of rules from A. Next, selection stage and execution stage are described in detail. Selection stage. Input: A configuration Ctof Πat instant t C0 t← Ct;A← ∅;B← ∅ for each membrane (i, σ)of C0 taccording to the lexicographical order do for each r∈ REaccording to the order chosen do nr←maximum number of times that ris applicable to (i, σ) if nr>0then C0 t← C0 t\nr·LHS(r, (i, σ)) A←A∪ {(r, nr,(i, σ))} end if end for for each r∈ RCaccording to the order chosen do if (i, σ)/∈Band ris applicable to (i, σ)in C0 tthen C0 t← C0 t\LHS(r, (i, σ)) A←A∪ {(r, 1,(i, σ))} B←B∪ {(i, σ)} end if end for Minimal cooperation in polarizationless P systems with active membranes 351 for each r≡[a]i→b∈ RDaccording to the order chosen do if (i, σ)/∈Band ris applicable to (i, σ)in C0 tthen C0 t← C0 t\ {(a, (i, σ))} A←A∪ {(r, 1,(i, σ))} B←B∪ {(i, σ)} end if end for for r∈ RSaccording to the order chosen do if (i, σ)/∈Band ris applicable to (i, σ)in C0 tthen C0 t← C0 t\LHS(r, (i, σ)) A←A∪ {(r, 1,(i, σ))} B←B∪ {(i, σ)} end if end for end for This algorithm is deterministic and works in polynomial time. Indeed, the cost in time is polynomial in the size of Πbecause the number of cycles of the external main for loop is of order O(M+q), and the number of cycles of the three internal main for loops are of order O(|R|). Besides, the cost of each internal loops is of the order O(M+q). Let us notice that the number of tuples in set Ais of the order O(M) because each object in the system can be involved in, at most, one rule and at any configuration Ctthe total number of objects is upper bounded by M. In set Aan order is considered in a natural way (a product order concerning the rules, natural numbers and labels). In order to complete the simulation of a computation step of the system Π, the execution stage takes care of the effects of applying the rules selected in the previous stage: updating the objects according to the RHS of the rules. Execution stage. Input: The output C0 tand Aof the selection stage for each (r, nr,(i, σ)) ∈Aaccording to the order chosen do if r∈ REthen C0 t← C0 t+nr·RHS(r, (i, σ)) if r∈ RCthen C0 t← C0 t+RHS(r, (i, σ)) if r∈ RDthen C0 t← C0 t+RHS(r, (p(i), σ)) C0 t← C0 t+{(x, (p(i), σ)) |xis in membrane (i, σ)in C0 t} Update the parent function by removing the membrane (i, σ) else if r∈ RSthen C0 t← C0 t+{(λ, i, σ)/σ0} C0 t← C0 t+{(λ, i, σ1)} for each (x, i, σ)∈ C0 taccording to the lexicographical order do if x∈Γ0then C0 t← C0 t+{(x, i, σ)/σ0}