Characterizing Tractability with Membrane Creation

Characterizing Tractability with Membrane Creation Miguel A. Guti´ errez–Naranjo, Mario J. P´ erez–Jim´ enez, Agust´ ın Riscos–N´ u˜ nez, Francisco J. Romero–Campero Research Group on Natural Computing Dpt. Computer Science and Artificial Intelligence, University of Sevilla Avda. Reina Mercedes s/n, 41012 - Sevilla, SPAIN Email: {magutier, marper, ariscosn, fran}@us.es Abstract— This paper analyzes the role that membrane dissolution rules play in order to characterize (in the framework of recognizer P systems with membrane creation) the tractability of decision problems –that is, the efficient solvability of problems by deterministic Turing machines. In this context, the use or not of these rules provides an interesting borderline between tractability and (presumable) intractability. I. INTRODUCTION Membrane Computing is a cross-disciplinary field of Natural Computing with contributions by computer scientists, biologists and formal linguists that was introduced by Gh. P˘ aun in [6]. Since then it has received important attention from the scientific community. In fact, Membrane Computing has been chosen by the Institute for Scientific Information as a fast Emerging Research Front in Computer Science in October 2003 [14]. This new non-deterministic model of computation starts from the assumption that the processes taking place in the compartmental structure of a living cell can be interpreted as computations. The devices of this model are called P systems. Roughly speaking, a P system consists of a cell-like membrane structure, in the compartments of which one places multisets of objects which evolve according to given rules in a synchronous non-deterministic maximally parallel manner1. In living cells, new membranes are produced basically through two processes, mitosis (membrane division) and autopoiesis (membrane creation)2. These two processes have inspired two variants of P systems, namely P systems with active membranes and P systems with membrane creation. P systems with active membranes have been successfully used to design solutions to well-known NP-complete problems (e.g. [11], [12], [13]). Recently, the first (uniform) results related to the computational efficiency using membrane creation have arisen (see [2], [3]). The paper is organized as follows. First, we summarize basic notions on computational complexity in P systems. Section III recalls P systems with membrane creation. The concept of dependency graph is defined in Section IV, providing a characterization of standard class Pin terms of recognizer P systems with membrane creation without using dissolution 1A detailed description can be found in [7] and further bibliography at [15]. 2Membranes are created in living cells, for instance, in the process of vesicle mediated transport and in order to keep molecules close to each other to facilitate their reactions. Membranes can also be created in a laboratory - see [4]. rules. A linear solution to QSAT by P systems with membrane creation is presented in Section V, showing a surprising role of dissolution rules: using them we go beyond tractability. Finally, some conclusions are given in Section VI. II. RECOGNIZER P SYSTEMS In the structure and functioning of a cell, biological membranes play an essential role. The cell is separated from its environment by means of a skin membrane, and it is internally compartmentalized by means of internal membranes. Within the cell there are chemical substances that can participate in various reactions, depending on the compartment where they reside. In this way, the main syntactic ingredients of a cell–like membrane system (P system) are the membrane structure, the multisets, and the evolution rules. •Amembrane structure consists of several membranes arranged hierarchically inside a main membrane (the skin), and delimiting regions (the space in–between a membrane and the immediately inner membranes, if any). Each membrane identifies a region inside the system. A membrane structure can be represented by a rooted tree. •Regions defined by a membrane structure contain objects. We shall describe such objects by symbols, in such a way that multisets of objects are located in the regions of the membrane structure. •The objects can evolve according to given evolution rules, associated with the regions (hence, with the membranes). For the semantics of the cell–like membrane systems we take a non–deterministic and synchronous mode (a global clock is assumed). •Aconfiguration of a cell–like membrane system consists of a membrane structure and a family of multisets of objects associated with each region of the structure. At the beginning, there is a configuration called the initial configuration of the system. •In each time unit we can transform a given configuration into another one by applying evolution rules to the objects placed inside the regions, in a non–deterministic and maximally parallel manner (the rules are chosen in a non– deterministic way, and in each region all objects that can evolve must do it). In this way, we get transitions between configurations. •Acomputation of the system is a (finite or infinite) sequence of configurations such that each configuration –except the initial one– is obtained from the previous one by a transition. •A computation which reaches a configuration where no more rules can be applied to the existing objects is called ahalting computation. •The result of a halting computation is usually defined through the multiset associated with a specific output membrane (or the environment) in the final configuration. If the output is collected in the environment, then we say that the system has external output. Thus, a computation in a P system is summarized as follows: it starts with the initial configuration of the system, then the computation proceeds, and when it stops the result is to be found in the output membrane (or in the environment). In this paper we use membrane computing as a framework to address the resolution of decision problems. In order to solve these kinds of problems, having in mind that solving them is equivalent to recognizing the languages associated with them, we consider P systems as language recognizer devices. Definition 1: AP system with input is a tuple (Π,Σ, iΠ), where: (a) Πis a P system with working alphabet Γ, with pmembranes labelled by 1, . . . , p, and initial multisets M1, . . . , Mpassociated with them; (b) Σis an (input) alphabet strictly contained in Γand the initial multisets are over Γ−Σ; (c) iΠis the label of a distinguished (input) membrane. The semantics of a P system with input (Π,Σ, iΠ)is esentially the same as for Π. However, now the initial configuration of (Π,Σ, iΠ)is not unique, for every possible input multiset over Σthere is an associated initial configuration: Definition 2: Let (Π,Σ, iΠ)be a P system with input. Let Γ be the working alphabet of Π,µthe membrane structure, and M1, . . . , Mpthe initial multisets of Π. Let mbe a multiset over Σ. The initial configuration of (Π,Σ, iΠ)with input m is (µ, M1, . . . , MiΠ∪m, . . . , Mp). Let (Π,Σ, iΠ)be a P system with input. Let Γbe the working alphabet of Π,µthe membrane structure and M1, . . . , Mp the initial multisets of Π. Let mbe a multiset over Σ. Then we denote M∗ j={(a, j) : a∈ Mj}, for 1≤j≤p, and m∗={(a, iΠ) : a∈m}. This notation will be useful in Section IV. Definition 3: Arecognizer P system is a P system with external output such that: 1) The working alphabet contains two distinguished elements yes and no. 2) All computations halt. 3) If Cis a computation of the system, then either object yes or object no (but not both) must have been released into the environment, and only in the last step of the computation. In recognizer P systems, we say that a computation Cis an accepting computation (respectively, rejecting computation) if the object yes (respectively, no) appears in the environment associated with the corresponding halting configuration of C. Hence, these devices send to the environment an accepting or rejecting answer, at the end of their computations. Let us recall that a decision problem Xis a pair (IX, θX) where IXis a language over a finite alphabet (whose elements are called instances) and θXis a predicate (a total boolean function) over IX. Definition 4: Let X= (IX, θX)be a decision problem. Let Π= (Π(n))n∈Nbe a family of recognizer P systems with input. A polynomial encoding from Xto Πis a pair (cod, s) of polynomial time computable functions over IXsuch that for each instance w∈IX,s(w)is a natural number and cod(w) is an input multiset for the system Π(s(w)). It is easy to prove that polynomial encodings are stable under polynomial time reductions. More formally: Proposition 1: Let X1, X2be decision problems. Let rbe a polynomial time reduction from X1to X2. Let (cod, s)be a polynomial encoding from X2to Π. Then (cod ◦r, s ◦r)is a polynomial encoding from X1to Π. Definition 5: Let X= (IX, θX)be a decision problem. Let Π= (Π(n))n∈Nbe a family of recognizer P systems with input. Let (cod, s)be a polynomial encoding from Xto Π. •We say that the family Πis sound with regard to (X, cod, s)if the following holds: for each instance of the problem w∈IX, if there exists an accepting computation of Π(s(w)) with input cod(w), then θX(w)=1. •We say that the family Πis complete with regard to (X, cod, s)if the following holds: for each instance of the problem u∈IX, if θX(u) = 1, then every computation of Π(s(u)) with input cod(u)is an accepting computation. Next, we propose to solve a decision problem through a family of P systems (constructed in polynomial time by a deterministic Turing machine) where each element of the family processes, in a specified sense, all the instances of equivalent size. Definition 6: Let Rbe a class of recognizer P systems with input membrane. A decision problem X= (IX, θX)is solvable in polynomial time by a family Π= (Π(n))n∈Nof P systems from R, and we denote this by X∈PMCR, if the following holds: •The family Πis polynomially uniform by Turing machines, that is, there exists a deterministic Turing machine working in polynomial time which constructs the system Π(w)from the instance w∈IX. •There exists a polynomial encoding (cod, s)from Xto Πsuch that –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)) with input cod(u)is halting and, moreover, it performs at most p(|u|)steps. –The family Πis sound and complete with regard to (X, cod, s). It is easy to see that the class PMCRis closed under polynomial–time reduction and complement (see [9] for details). III. P SYSTEMS WITH MEMBRANE CREATION In this section we recall the description of cellular devices with membrane creation. Basically there are two ways of producing new membranes in living cells: mitosis (membrane division) and autopoiesis (membrane creation, see [4]). The replication is one of the most important functions of a cell and, in ideal circumstances, by division we can obtain an exponential number of cells in linear time. One of the roles of membranes is to keep the molecules of a compartment close to each other, in order to facilitate their reactions; when a compartment becomes too large, it often happens that new membranes appear (are created) inside it (new membranes are produced under the influence of the existing objects). Both ways of generating new membranes have given rise to different variants of P systems: P systems with active membranes, where the new workspace is generated by membrane division, and P systems with membrane creation, where the new membranes are created from objects. Both models have been proved to be universal, but up to now there is no theoretical result proving that these models simulate each other in polynomial time. P systems with active membranes have been successfully used to design solutions to many NP-complete problems3, but as Gh. P˘ aun pointed in [8] “membrane division was much more carefully investigated than membrane creation as a way to obtain tractable solutions to hard problems”. Recently it has been shown that NP–complete problems can also be uniformly solved in the membrane creation framework (see, e.g., [2], [3]). Recall that a P system with membrane creation is a construct of the form Π = (Γ, H, µ, M1, . . . , Mp, R)where: 1) p≥1is the initial degree of the system; Γis the alphabet of objects and His a finite set of labels for membranes; 2) µis a membrane structure consisting of pmembranes, with the membranes injectively labelled with elements of H, and M1, . . . , Mpare strings over Γ, describing the multisets of objects placed in the pregions of µ; 3) Ris a finite set of rules, of the following forms: (a) [a→u]hwhere h∈H,a∈Γand uis a string over Γdescribing a multiset of objects. These are object evolution rules associated with membranes and depending only on the label of the membrane. (b) a[ ]h→[b]hwhere h∈H,a, b ∈Γ. These are send-in communication rules. An object is introduced in the membrane, possibly modified. (c) [a]h→[ ]hbwhere h∈H,a, b ∈Γ. These are send-out communication rules. An object is sent out of the membrane, possibly modified. (d) [a]h→bwhere h∈H,a, b ∈Γ. These are dissolution rules. Under the influence of an object, a membrane is dissolved, while the object specified in the rule can be modified. (e) [a→[u]h0]hwhere h, h0∈H,a∈Γand uis a string over Γdescribing a multiset of objects. These are creation rules. As the effect of the 3See [15] for a comprehensive bibliography of such solutions. evolution of an object, a, a new membrane is created. This new membrane is placed inside the membrane of the object which triggers the rule and has associated an initial multiset, u, and a label, h0. Rules are applied according to the following principles: •Rules from (a) to (d) are used as usual in the framework of membrane computing, that is, in a maximally parallel way. In one step, each object in a membrane can only be used for one rule (non–deterministically chosen when there are several possibilities), but any object which can evolve by a rule of any form must do it. •Rules of type (e) are also used in a maximally parallel way. Each object ain a membrane labelled with h produces a new membrane with label h0placing in it the multiset of objects described by the string u. •If a membrane is dissolved, its content (multiset and interior membranes) becomes part of the immediately external membrane. The skin membrane is never dissolved. •All the elements which are not involved in any of the operations to be applied remain unchanged. •The rules associated with the label hare used for all membranes with this label, irrespectively of whether or not the membrane is an initial one or it was obtained by creation. •Several rules can be applied to different objects in the same membrane simultaneously. The exception are the rules of type (d) since a membrane can be dissolved only once. We denote by MC−d(respectively, MC+d) the class of recognizer P systems with membrane creation and without dissolution rules (respectively, with dissolution rules). IV. DEPENDENCY GRAPH OF A RECOGNIZER PSYSTEM WITH MEMBRANE CREATION Let Πbe a recognizer P system with membrane creation and without dissolution. Let Rbe the set of rules associated with Π. Each rule can be considered, in some sense, as a dependency relationship between the object triggering the rule and the object(s) produced by its application. We can consider a general pattern for all kinds of rules of such systems, except for dissolution rules, as follows: (a, h)→(a1, h0)(a2, h0)...(as, h0), according to the following criterion: •The rules of type (a) correspond to the case h=h0, u=a1. . . as, and s≥1. •The rules of type (b) correspond to the case h∈F(h0) and s= 1. •The rules of type (c) correspond to the case h0∈F(h) and s= 1. •The rules of type (e) correspond to the case u=a1. . . as, and s≥1. If his the label of a membrane, then F(h)denotes the set of labels h0∈Hsuch that h0is the label of the father of the membrane labelled by hin the initial configuration, or there exist a∈Γ, u ∈Γ∗verifying [a→[u]h]h0∈R, where Ris the set of rules associated with the system. Given h, h0∈H the cost of determining whether or not h0∈F(h)is of the order O(|R|+p), being pthe number of initial membranes. We adopt the convention that the set F(h)associated with the skin membrane is the singleton whose only element is the label of the environment, denoted by env ∈H. For example, let us consider a general rule (a, h)→ (a1, h0)...(as, h0). Then we can interpret that from the object ain membrane labelled by hwe can reach the objects a1, . . . , asin membrane labelled by h0. We formalize these ideas in the following definition. Definition 7: Let Πbe a recognizer P system with membrane creation and without dissolution. Let Rbe the set of rules associated with Π. The dependency graph associated with Πis the directed graph GΠ= (VΠ, EΠ)defined as follows: VΠ=V LΠ∪V RΠ, (a, h)∈V LΠif and only if: •∃u∈Γ∗([a→u]h∈R), or •∃b∈Γ ([a]h→[ ]hb∈R), or •∃b∈Γ∃h0∈H(h∈F(h0)∧a[ ]h0→[b]h0∈R), or •∃u∈Γ∗∃b∈Γ∃h0∈H(b∈alph(u)∧h∈F(h0)∧ [a→[u]h0]h∈R); (b, h)∈V RΠif and only if: •∃a∈Γ∃u∈Γ∗([a→u]h∈R∧b∈alph(u)), or •∃a∈Γ∃h0∈H(h∈F(h0)∧[a]h0→[ ]h0b∈R), or •∃a∈Γ (a[ ]h→[b]h∈R), or •∃a∈Γ∃u∈Γ∗∃h0∈F(h) (b∈alph(u)∧[a→ [u]h]h0∈R); ((a, h),(b, h0)) ∈EΠif and only if: •∃u∈Γ∗([a→u]h∈R∧b∈alph(u)∧h=h0)∨ ([a]h→[ ]hb∈R∧h0∈F(h)) ∨ (a[ ]h0→[b]h0∈R∧h∈F(h0)), or •∃u∈Γ∗(b∈alph(u)∧h∈F(h0)∧[a→[u]h0]h∈R). Proposition 2: Let Πbe a recognizer P system with membrane creation and without dissolution. There exists a Turing machine that constructs the dependency graph, GΠ, associated with Π, in polynomial time, that is, in a time bounded by a polynomial function depending on the total number of rules and the maximum length of the rules. Proof: A deterministic algorithm that, given a P system Πwith the set Rof rules, constructs the corresponding dependency graph, is the following: Input: Π(with Ras its set of rules) VΠ← ∅;EΠ← ∅ for each rule r∈Rof Πdo if r= [a→u]h∧alph(u) = {a1, . . . , as}then VΠ←VΠ∪Ss j=1{(a, h),(aj, h)}; EΠ←EΠ∪Ss j=1{((a, h),(aj, h))} if r= [a]h→[ ]hbthen for each h0∈F(h)do VΠ←VΠ∪ {(a, h),(b, h0)}; EΠ←EΠ∪ {((a, h),(b, h0))} if r=a[ ]h→[b]hthen for each h0∈F(h)do VΠ←VΠ∪ {(a, h0),(b, h)}; EΠ←EΠ∪ {((a, h0),(b, h))} if r= [a→[u]h0]h∧alph(u) = {a1, . . . , as}then VΠ←VΠ∪Ss j=1{(a, h),(aj, h0)}; EΠ←EΠ∪Ss j=1{((a, h),(aj, h0))} The cost of this algorithm is of the order O(|R|·(q+|R|+p)), where q=max{length(r) : r∈R}, and pis the number of initial membranes. Proposition 3: Let Πbe a recognizer P system with membrane creation and without dissolution. Let ∆Πbe defined as follows: (a, h)∈∆Πif and only if there exists a path (within the dependency graph) from (a, h)to (yes, env). Then, there exists a Turing machine that constructs the set ∆Πin polynomial time, that is, in a time bounded by a polynomial function depending on the total number of rules and the maximum length of the rules. Proof: We can construct the set ∆Πfrom Πas follows: •Construct the dependency graph GΠassociated with Π. •Consider the following algorithm: Input: GΠ= (VΠ, EΠ) ∆Π← ∅ for each (a, h)∈VΠdo if there exists a path from (a, h)to (yes, env)in GΠ, then ∆Π←∆Π∪ {(a, h)} The running time of this algorithm is of the order O(|VΠ| · |VΠ|2), hence it is of the order O(|Γ|3· |H|3), where Γis the working alphabet and Hthe set of labels of Π. Remark 1: It is easy to design an algorithm running in polynomial time solving the following decision problem: given a directed graph G, and two nodes a, b, determine whether or not the node bis reachable from a, that is, whether or not there exists a path in the graph from ato b. For example, given a directed graph G, and two nodes a, b, we consider a depth–first–search with source a, and we check if bis in the tree of the computation forest whose root is a. The total running time of this algorithm is O(|V|+|E|), that is, in the worst case is quadratic in the number of nodes. Moreover, this algorithm needs to store a linear number of items. Proposition 4: Let X= (IX, θX)be a decision problem. Let Π= (Π(n))n∈Nbe a family of recognizer P systems with input membrane solving X, according to Definition 6. Let (cod, s)be the polynomial encoding associated with that solution. Then, for each instance wof the problem Xthe following assertions are equivalent: (a) θX(w) = 1 (that is, the answer to the problem is yes for w). (b) ∆Π(s(w)) ∩((cod(w))∗∪Sp j=1 M∗ j)6=∅, where M1, . . . , Mpare the initial multisets of the system Π(s(w)). Proof: Let w∈IX. Then w∈LXif and only if there exists an accepting computation of the system Π(s(w)) with input multiset cod(w). But this condition is equivalent to the following: in the initial configuration of Π(s(w)) with input multiset cod(w)there exists an object a∈Γin a membrane labelled by hsuch that in the dependency graph the node (yes, env)is reachable from (a, h). Hence, θX(w) = 1 if and only if ∆Π(s(w)) ∩ M∗ 16=∅, or ..., or ∆Π(s(w)) ∩ M∗ p6=∅, or ∆Π(s(w)) ∩(cod(w))∗6=∅. Next, we show that, in the framework of recognizer P systems with membrane creation (but not using dissolution rules), constructing in polynomial time an exponential workspace (number of membranes) is not enough to solve NP–complete problems in polynomial time (unless P=NP). Theorem 1: PMCMC−d=P. Proof: We have P⊆PMCMC−dbecause the class PMCMC−dis closed under polynomial time reduction. Next, we show that PMCMC−d⊆P. For that, let X∈ PMCMC−d. Let Π= (Π(n))n∈Nbe a family of recognizer P systems with membrane creation and without dissolution solving X, according to Definition 6. Let (cod, s)be the polynomial encoding associated with that solution. We consider the following deterministic algorithm: Input: An instance wof X - Construct the system Π(s(w)) with input multiset cod(w) - Construct the dependency graph GΠ(s(w)) associated with Π(s(w)) - Construct the set ∆Π(s(w)) according to Proposition 3 - Consider the following algorithm: answer ←no; j←1 while j≤p∧answer =no do if ∆Π(s(w)) ∩ M∗ j6=∅then answer ←yes j←j+ 1 endwhile if ∆Π(s(w)) ∩(cod(w))∗6=∅then answer ←yes On one hand, the answer of this algorithm is yes if and only if there exists a pair (a, h)belonging to ∆Π(s(w)) such that in the membrane labelled by hin the initial configuration (with input the multiset cod(w)) appears the symbol a. On the other hand, a pair (a, h)belongs to ∆Π(s(w)) if and only if there exists a path from (a, h)to (yes, env); that this, if and only if we can obtain an accepting computation of Π(s(w)) with input cod(w). Hence, the algorithm above described solves the problem X. The cost to determine whether or not ∆Π(s(w)) ∩ M∗ j6=∅ (or ∆Π(s(w)) ∩(cod(w))∗6=∅)is of the order O(|Γ|2· |H|2). Hence, the running in time of this algorithm can be bounded by f(|w|) + O(|R| · q) + O(p· |Γ|2· |H|2), where fis the (total) cost of a polynomial encoding from Xto Π,Rthe set of rules of Π,pis the initial number of membranes, and q= max {length(r) : r∈R}. But from Definition 6 we have that all involved parameters are polynomials in |w|. That is, the algorithm is polynomial in the size |w|of the input. V. SOLVING QSAT IN LINEAR TIME In this section we design a family of recognizer P systems with membrane creation (and using dissolution rules) which solves QSAT (the quantified satisfiability problem) in linear time. Given a boolean formula ϕ(x1, . . . , xn)in conjunctive normal form, with boolean variables x1, . . . , xn, the sentence ϕ∗=∃x1∀x2. . . Qnxnϕ(x1, . . . , xn)(where Qnis ∃if nis odd, and Qnis ∀otherwise) is said to be the (existential) fully quantified formula associated with ϕ(x1, . . . , xn). Recall that a sentence is a boolean formula in which every variable is in scope of a quantifier. We say that ϕ∗is satisfiable if there exists a truth assignment, σ, over {i: 1 ≤i≤n∧iodd}such that each extension, σ∗, of σover {1, . . . , n}verifies σ∗(ϕ(x1, . . . , xn)) = 1. The QSAT problem is the following one: Given the (existential) fully quantified formula ϕ∗associated with a boolean formula ϕ(x1, . . . , xn)in conjunctive normal form, determine whether or not ϕ∗is satisfiable. It is well known that QSAT is a PSPACE–complete problem [5]. Next, we provide a polynomial time solution to QSAT by a family of recognizer P systems with membrane creation and using dissolution rules, according to Definition 6. The solution follows a brute force approach, in the framework of recognizer P systems with membrane creation, and consists in the following phases: •Generation and Evaluation Stage: Using membrane creation, a binary complete tree is constructed. The leaves of that tree encode all possible truth assignments associated with the formula. Nodes whose level is even (respectively, odd) are codified by an OR gate (respectively, AND gate). So, we can consider the constructed tree as a boolean circuit that only have gates AND, OR. In this stage, the values of the formula corresponding to each assignment is obtained in the leaves. •Checking Stage: We proceed to compute the output of that boolean circuit from the inputs obtained in the leaves by propagating values along the wires and computing the respective gates until the output gate (the root of the tree) has assigned a value. •Output Stage: The systems sends out to the environment the right answer according to the result of the previous stage. Let us consider the pair function h,idefined by hn, mi= ((n+m)(n+m+ 1)/2) + n. This function is polynomial-time computable (it is primitive recursive and bijective from N2onto N). For any given boolean formula, ϕ(x1, . . . , xn) = C1∧ · · · ∧ Cm, in conjunctive normal form, with nvariables and mclauses, we construct a P system Π(hn, mi)processing the (existential) fully quantified formula ϕ∗associated with ϕ(when an appropriate input is supplied). The family of recognizer P systems with membrane creation and using dissolution rules presented here is Π={(Π(hn, mi),Σ(hn, mi), i(hn, mi)) : (n, m)∈N2} where the input alphabet is Σ(hn, mi) = {xi,j, xi,j : 1 ≤i≤m, 1≤j≤n} the input membrane is i(hn, mi) =< t, ∨>, and the P system Π(hn, mi) = (Γ(hn, mi), H(hn, mi), µ, Ms,M<t,∨>, R(hn, mi)) is defined as follows: •Working alphabet, Γ(hn, mi), is Σ(hn, mi)∪ {zj,c |j∈ {0,...n}, c ∈ {∧,∨} } ∪ {zj,c,l |j∈ {0,...,n−1}, c ∈ {∧,∨}, l ∈ {t, f}} ∪ {xi,j,l, xi,j,l |j∈ {1,...,n}, i ∈ {1,...,m}, l ∈ {t, f}} ∪ {xi,j |j∈ {1,...,n}, i ∈ {1,...,m}} ∪ {ri, ri,t, ri,f |i∈ {1,...,m}} ∪ {d1, . . . , dm, q, t0, . . . , t4, ans0, . . . , ans5} ∪ {yes, yes∨, yes∗, yes∧, yes∧, Y ES} ∪ {no, no∨, no∗, no∨, no∧, no∧, NO} •The set of labels, H(hn, mi), is {< l, c >:l∈ {t, f}, c ∈ {∧,∨}} ∪ {a, s, 1, . . . , m} •Initial membrane structure: µ= [ [ ]<t,∨>]s •Initial multisets: Ms=∅,M<t,∨>={z0,∧,tz0,∧,f } •Input membrane: [ ]<t,∨> •The set of evolution rules, R(hn, mi), consists of the following rules (recall that λdenotes the empty string, and if cis ∧then cis ∨, and if cis ∨then cis ∧): 1.[zj,c →zj,c,t, zj,c,f ]<l,c> [zj,c,l →[zj+1,c]<l,c>]<l0,c> ), for l, l0∈ {t, f}, c ∈ {∨,∧}, j ∈ {0,...,n−1}. The goal of these rules is to create one membrane for each assignment to the variables of the formula. Firstly, the object zj,c evolves to two objects, one for the assignment true (the object zj,c,t), and a second one for the assignment false (the object zj,c,f ). In a second step these objects will create two membranes. The new membrane with tin its label represents the assignment xj+1 =true; on the other hand, the new membrane with fin its label represents the assignment xj+1 =false. 2.[xi,j →xi,j,txi,j,f ]<l,c> [xi,j →xi,j,txi,j,f ]<l,c> [ri→ri,tri,f ]<l,c>      , for l∈ {t, f}, i ∈ {1,...,m}, c ∈ {∨,∧}, j ∈ {1,...,n}. These rules duplicate the objects representing the formula so it can be evaluated on the two possible assignments, xj=true (xi,j,t, xi,j,t) and xj=false (xi,j,f , xi,j,f ). The objects riare also duplicated (ri,t, ri,f ) in order to keep track of the clauses that evaluate true on the previous assignments to the variables. 3. xi,1,t[ ]<t,c> →[ri]<t,c> xi,1,t[ ]<t,c> →[λ]<t,c> xi,1,f [ ]<f,c> →[λ]<f,c> xi,1,f [ ]<f,c> →[ri]<f,c> ), for i∈ {1,...,m}, c ∈ {∨,∧}. According to these rules the formula is evaluated in the two possible assignments for the variable that is being analyzed. The objects xi,1,t (resp. xi,1,f ) get into the membrane with tin its label (resp. f) being transformed into the objects rirepresenting that the clause number ievaluates true on the assignment xj+1 =true (resp. xj+1 =false). On the other hand, the objects xi,1,t (resp. xi,1,t) get into the membrane with fin its label (resp. t) producing no objects. This represents that these objects do not make the clause true in the assignment xj+1 =true (resp. xj+1 =false). 4. xi,j,l[ ]<l,c> →[xi,j−1]<l,c> xi,j,t[ ]<l,c> →[xi,j−1]<l,c> ri,t[ ]<l,c> →[ri]<l,c>      , for l∈ {t, f}, i ∈ {1,...,m}, c ∈ {∨,∧}, j ∈ {2, . . . , n}. In order to analyze the next variable the second subscript of the objects xi,j,l and xi,j,l are decreased when they are sent into the corresponding membrane labelled with l. Moreover, following the last rule, the objects ri,l get into the new membranes to keep track of the clauses that evaluate true on the previous assignments. 5.[zn,c →d1. . . dmq]<l,c>, for l∈ {t, f}and c∈ {∨,∧}. At the end of the generation stage the object znwill produce the objects d1, . . . , dmand yes0, which will take part in the checking stage. 6.[di→[t0]i]<l,c> ri,t[ ]i→[ri]i[ri]i→λ [tj→tj+1]i[t2]i→t3      , for i∈ {1,...,m}, j ∈ {0,1}, l ∈ {t, f}, c ∈ {∨,∧}. Following these rules each object dicreates a new membrane with label iwhere the object t0is placed; this object will act as a counter. The object rigets into the membrane labelled with iand dissolves it preventing the counter tifrom reaching the object t2. The fact that the object t2appears in a membrane with label imeans that there is no object ri, that is, the clause number idoes not evaluate true on the assignment associated with the membrane; therefore neither does the formula on the associated assignment. 7.[q→[ans0]a]<l,c> t3[ ]a→[t4]a[t4]a→λ [ansh→ansh+1]a[ans5]a→yes [ans5→no]<l,c>          , for l∈ {t, f}, c ∈ {∨,∧}, h = 0,...,4. The object qcreates a membrane with label awhere the object ans0is placed. The object anshevolves to the object ansh+1; at the same time the objects t3can get into the membrane labelled with aand dissolve it preventing the object yes from being sent out from this membrane. 8.[yes]<l,c> →yesc[no]<l,c> →noc [yes∨]<l,∨>→yes∗[no∨→no∨]<l,∨> [yes∗→yes∧]<l,∧>[no∨]<l,∨>→no∧ [no∨→λ]<l,∧>[yes∨→λ]<l,∧> [no∧]<l,∧>→no∗[yes∧→yes∧]<l,∧> [no∗→no∨]<l,∨>[yes∧]<l,∧>→yes∨ [no∧→λ]<l,∨>[yes∧→λ]<l,∨> [yes∗]s→Y ES [ ]s[no∧]s→NO [ ]s                              , for l∈ {t, f}. This set of rules controls the output stage. After the evaluation stage, from each working membrane we obtain an object yes or no depending on whether the assignment associated with this membrane satisfies or not the formula. Contrary to the SAT problem, in QSAT it is not enough that one assignment satisfies the formula, but the final answer is YES if an appropriate combination of assignments according to the quantifiers ∃and ∀is found. A. An overview of the computation First of all we define a polynomial encoding of the QSAT problem in the family Πconstructed in the previous section. Given a boolean formula in conjunctive normal form, ϕ=C1∧... ∧Cmsuch that V ar(ϕ) = {x1, . . . , xn}, and considering ϕ∗the (existential) fully quantified formula associated with it, we define s(ϕ∗) = hn, mi(recall the bijection mentioned in the previous section) and cod(ϕ∗) = {xi,j :xj∈Ci} ∪ {xi,j :¬xj∈Ci}. Next we describe informally how the recognizer P system with membrane creation Π(s(ϕ∗)) with input cod(ϕ∗)works. In the initial configuration we have the input multiset cod(ϕ∗)and the objects z0,∧,t and z0,∧,f placed in the input membrane (membrane labelled with < t, ∨>). In the first step of the computation the object z0,∧,t creates a new membrane with label < t, ∨>which represents the assignment x1= true and the object z0,∧,f creates a new membrane with label < f, ∨>which represents the assignment x1=false. The second component of the labels, i.e., ∧and ∨will be used in the output stage. In these two new membranes the object z1,∨is placed. At the same time the input multiset representing the formula ϕ∗ is duplicated following the two first rules in group 2. In the next step, according to the rules in group 3, the formula is evaluated on the two possible assignments for x1. In the same step the rules in group 4 decrease the second subscript of the objects representing the formula (xi,j,l, xi,j,l with j≥2) in order to analyze the next variable. Moreover, at the same time, the object z1,c produces the object z1,c,t and z1,c,f (c∈ {∧,∨}) and the system is ready to analyze the next variable. The generation and evaluation stage goes on in this way until all the possible assignments to the variables are generated and the formula is evaluated on each of them. Observe that it takes two steps to generate the possible assignments for a variable and evaluate the formula on them; therefore the generation and evaluation stage takes 2nsteps. The checking stage starts when the object zn,c produces the objects d1, . . . , dmand the object q. In the first step of the checking stage each object di, for i= 1, . . . , m, creates a new membrane labelled with iwhere the object t0is placed, and the object qcreates a new membrane with label aplacing the object yes0in it. The objects ri,t, which indicate that the clause number i evaluates true on the assignment associated with the membrane, are sent into the membranes by the last rule in group 4 so the system keeps track of the clauses that are true. The objects ri,t get into the membrane with label iand dissolves it in the following two steps preventing the counter t2from dissolving the membrane and producing the object t3 according to the last rule in group 6. If for some ithere is no object ri, which means that the clause idoes not evaluate true on the associated assignment, the object t2will dissolve the membrane labelled with iproducing the object t3that will get into the membrane with label awhere the object ansh evolves following the rules in group 7. The object t4dissolves the membrane with label apreventing the production of the object ans5. Therefore the checking stage takes 7 steps. Finally the output stage takes place according to the rules in group 8. If some object ans5is present in any membrane with label < l, c >, (l∈ {t, f},c∈ {∧,∨}), this means that there exists at least one clause not satisfied by the assignment associated with the membrane, and by the last rule in group 7 we obtain no in this membrane. Otherwise, the object ans5 will be inside the membrane with label a, it will dissolve the membrane, and send yes to the working membrane. At this point, in each of the 2nworking membranes we have an object yes or no depending on if the associated assignment satisfies or not the formula ϕ. In the last steps we control the flow of the objects yes and no from the working membranes to the environment. Basically, the process is the following: if there is one object yes inside a membrane with ∨ in its label, this object dissolves the membrane and sends out another yes; if this does not happen, i.e., if two objects no are inside a membrane with label ∨, the membrane is dissolved and no is sent out. Analogously, if there is one object no inside a membrane with ∧in its label, this object dissolves the membrane and sends out another no. Otherwise, if two objects yes are inside a membrane with label ∨, the membrane is dissolved and yes is sent out. If the answer is affirmative, then the system halts in the (4n+8)–step. If, on the contrary, the answer is negative, then the system halts in the (4n+9)–step. Hence, the family Πof recognizer P systems with membrane creation using dissolution rules solves in polynomial (actually, linear) time QSAT according to Definition 6. So, we have the following result. Theorem 2: QSAT ∈PMCMC+d Corollary 1: PSPACE ⊆PMCMC+d Proof: It suffices to remark that the QSAT problem is PSPACE–complete, QSAT ∈PMCMC+d, and this complexity class is closed under polynomial time reduction. VI. CONCLUSIONS It is a very interesting issue to obtain conditions providing a distinction between tractable problems (that is, those that are solvable by computational devices running in polynomial time) and the problems that are not tractable. This paper is focused in that direction and it wishes to stress the relevant role played by an apparently innocent operation (as dissolution rules) in order to “separate” the complexity classes Pand PSPACE. Thus, in the framework of recognizer P systems with membrane creation, dissolution rules permit to distinguish the tractability of decision problems, suppossing P6=PSPACE. In our characterization of the class P, we have used the concept of dependency graph, that initially was defined to help to design strategies looking for short computations of confluent membrane systems. We characterize the accepting computations of recognizer P systems with membrane creation and without dissolution through the reachability of a distinguished node of the graph from other nodes associated with the initial configuration. ACKNOWLEDGMENT This work is supported by Ministerio de Ciencia y Tecnolog´ ıa of Spain, by Plan Nacional de I+D+I (2000–2003) (TIC2002-04220-C03-01), cofinanced by FEDER funds, and by a FPI fellowship (University of Seville), in the case of the fourth author. REFERENCES [1] 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, 9, 9 (2005), 673–678. [2] M.A. Guti´ errez-Naranjo, M.J. P´ erez-Jim´ enez, F.J. Romero-Campero: A linear solution of Subset Sum Problem by using Membrane Creation. In Mechanisms, symbols and models underlying cognition, First International Work-Conference on the interplay between Natural and Artificial Computation, IWINAC 2005 (J. Mira, J.R. Alvarez, eds.), LNCS 3561 (2005), 258–267. [3] M.A. Guti´ errez-Naranjo, M.J. P´ erez-Jim´ enez, F.J. Romero-Campero: Solving SAT with Membrane Creation. In Computability in Europe 2005, CiE 2005: New Computational Paradigms (S. Barry Cooper, B. Lowe, L. Torenvliet, eds.), Report ILLC X-2005-01, University of Amsterdam, 82–91. [4] P.L. Luisi: The chemical implementation of autopoiesis, Self-Production of Supramolecular Structures (G.R. Fleishaker et al., eds.), Kluwer, Dordrecht, 1994. [5] Ch.H. Papadimitriou: Computational Complexity, Addison-Wesley Publishing Company, Reading, Massachusetts, 1995. [6] Gh. P˘ aun: Computing with membranes, Journal of Computer and System Sciences,61, 1 (2000), 108–143. [7] Gh. P˘ aun: Membrane Computing. An Introduction, Springer–Verlag, Berlin, 2002. [8] Gh. P˘ aun: Further open problems in membrane computing. Proceedings of the Second Brainstorming Week on Membrane Computing (Gh. P˘ aun, A. Riscos-N´ u˜ nez, A. Romero-Jim´ enez, F. Sancho-Caparrini, eds.), Report RGNC 01/04, University of Seville, 2004, 354–365. [9] M.J. P´ erez–Jim´ enez: An approach to computational complexity in Membrane Computing. In Membrane Computing, 5th International Workshop, WMC5, Revised Selected and Invited Papers (G. Mauri, Gh. P˘ aun, M. J. P´ erez-Jim´ enez, G. Rozenberg, A. Salomaa, eds.), LNCS 3365 (2005), 85–109. [10] M.J. P´ erez-Jim´ enez, F.J. Romero-Campero: Solving the Bin Packing problem by recognizer P systems with active membranes. Proceedings of the Second Brainstorming Week on Membrane Computing (Gh. P˘ aun, A. Riscos-N´ u˜ nez, A. Romero-Jim´ enez, F. Sancho-Caparrini, eds.), Report RGNC 01/04, University of Seville, 2004, 414–430. [11] 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, 23, 4 (2005), 367–384. [12] M.J. P´ erez-Jim´ enez, A. Riscos-N´ u˜ nez: A linear–time solution for the Knapsack problem using P systems with active membranes, Membrane Computing (C. Mart´ ın-Vide, G. Mauri, Gh. P˘ aun, G. Rozenberg, A. Salomaa, eds.), LNCS 2933 (2004), 250–268. [13] M.J. P´ erez-Jim´ enez, A. Romero-Jim´ enez, F. Sancho-Caparrini: A polynomial complexity class in P systems using membrane division, Proceedings of the 5th Workshop on Descriptional Complexity of Formal Systems, DCFS 2003, (E. Csuhaj-Varj´ u, C. Kintala, D. Wotschke, Gy. Vaszil, eds.), 2003, 284-294. [14] ISI web page: http://esi-topics.com/erf/october2003.html [15] P systems web page: http://psystems.disco.unimib.it/