A Characterization of PSPACE with Antimatter and Membrane Creation

A Characterization of PSPACE with Antimatter and Membrane Creation Zsolt Gazdag1, Miguel A. Guti´errez–Naranjo2 1Department of Algorithms and their Applications Faculty of Informatics E¨otv¨os Lor´and University, Hungary [email protected] 2Research Group on Natural Computing Department of Computer Science and Artificial Intelligence University of Sevilla, 41012, Spain [email protected] Summary. The use of negative information provides a new tool for exploring the limits of P systems as computational devices. In this paper we prove that the combination of antimatter and annihilation rules (based on the annihilation of physical particles and antiparticles) and membrane creation (based on autopoiesis) provides a P system model able to solve PSPACE-complete problems. Namely, we provide a uniform family of P system in such P system model which solves the satisfiability problem for quantified Boolean formulas (QSAT). In the second part of the paper, we prove that all the decision problems which can be solved with this P system model belong to the complexity class PSPACE, so this P system model characterises PSPACE. 1 Introduction The use of negative information provides a new challenge in the development of theoretical aspects in Membrane Computing (see [20]). Such negative information can be considered by extending the definition of a multiset fon a set Xfrom f:X→Nto f:X→Z(i.e., admitting negative multiplicity of the elements of the multiset [4, 13]) or even considering negative time and the possibility of travelling in time [7]. One of the most extended uses of negative information in Membrane Computing is considering anti-spikes in the framework of Spiking Neural P systems. In such model when one spike and one anti-spike appear in the same neuron, the annihilation occurs and both, spike and anti-spike, disappear [15, 17, 22, 24]. The use of antimatter, as an extension of the concept of anti-spikes, is being explored in other P system models [1, 2, 5]. 160 Z. Gazdag and M.A. Guti´errez-Naranjo Recently, it has been proved that antimatter and annihilation rules are a frontier of tractability in Membrane Computing [5]. The starting point for the study was a well-known result in the complexity theory of Membrane Computing: P systems with active membranes without polarizations, without dissolution and with division of elementary and non-elementary membranes (denoted by AM0 −d,+ne) can solve exactly problems in the complexity class P(see [8], Th. 2). The main result in [5] is that AM0 −d,+ne endowed with antimatter and annihilation rules (denoted by AM0 −d,+ne,+ant) can solve NP-complete problems. In a certain sense, such results show that if the number of membranes of the P system can be increased by membrane division, then endowing the model with dissolution or annihilation rules, then the model is capable to solve NP-complete problems. Similar results hold in the case of P systems with membrane creation. In [9] it is shown that these P systems when dissolution rules are allowed can solve PSPACE- complete problems (i.e, they can solve all the decision problems which can be solved by Turing machines, deterministic or non-deterministic, in polynomial space). In this paper, we show that using annihilation rules instead of dissolution rules, P systems with membrane creation are not only able to solve NP-complete problems, but PSPACE-complete problems too. By taking [23] as starting point, in the second part of the paper, we prove that all the decision problems which can be solved with this P system model belong to the complexity class PSPACE, so this P system model characterises PSPACE. The paper is organized as follows. In the next section, the notion of P systems with membrane creation and annihilation rules is introduced. Then recognizer P systems are briefly described. In Section 4 we show that the well known QSAT problem (i.e., the problem of deciding if a fully quantified Boolean formula is true or not) can be solved in linear time by P systems with membrane creation, with annihilation rules and without dissolution rules. In Section 5, we prove that PSPACE is an upper bound for the set of decision problems which can be solved with this model. Finally, some conclusions are given in the last section. 2 The P System Model The basis of the model is two types of rules which are not so common on complexity studies in Membrane Computing. The first type, rules of membrane creation, is based on the biological process of autopoiesis [14]. It creates a membrane from a single object in a similar way to the creation of a vesicle in a cell by a metabolite. This type of rule was first considered in [12, 16] and it has been proved that P systems with membrane creation and dissolution rules can solve NP-complete problems (see [10, 11]) or even PSPACE-complete problems (see [9]). The idea of using antimatter as a generalization of the anti-spikes used in Spiking Neural P Systems was firstly proposed in [21]. Based on the physical inspiration of particles and antiparticles, if an object aand its opposite one a A Characterization of PSPACE with Antimatter 161 appears simultaneously in the same membrane, they are annihilated by application of the corresponding rule aa →λ. As pointed above, several authors have started to explore the possibilities of using antimatter in Membrane Computing [1, 2, 5]. Formally, a P system with membrane creation and annihilation rules is a construct of the form Π= (O, H, µ, w1, . . . , wm, R), where: 1. m≥1 is the initial degree of the system; Ois the alphabet of objects and H is a finite set of labels for membranes; 2. µis a membrane structure consisting of mmembranes labelled (not necessarily in a one-to-one manner) with elements of Hand w1, . . . , wmare strings over O, describing the multisets of objects placed in the mregions of µ; 3. Ris a finite set of rules, of the following forms: (a) [a→v]hwhere h∈H,a∈O, and vis a string over Odescribing 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 ∈O. These are send-in communication rules. An object is introduced in the membrane possibly modified. (c) [a]h→[ ]hbwhere h∈H,a, b ∈O. These are send-out communication rules. An object is sent out of the membrane possibly modified. (d) [a→[v]h2]h1where h1, h2∈H,a∈O, and vis a string over Odescribing a multiset of objects. These are creation rules. In reaction with an object, a new membrane is created. This new membrane is placed inside of the membrane of the object which triggers the rule and has associated an initial multiset and a label. (e) [ aa→λ]hfor h∈H,a, a ∈O. This is an annihilation rule, associated with a membrane labelled by h: the pair of objects a, a ∈Obelonging simultaneously to this membrane disappears. Rules are applied according to the following principles: •Rules of type (a) - (d) are applied in parallel and in a maximal manner. In one step, one object of a membrane can be used by only one rule (chosen in a non–deterministic way), but any object which can evolve by one rule of any form, must evolve. •If an object can trigger two or more rules, one of such rules is nondeterministically chosen, except for annihilation rules (type (e)). Any annihilation rule has priority over all rules of the other types of rules. This fact has a clear physical inspiration. If a particle and its antiparticle meet, they do disappear and no other option is possible. This semantics was also used in [5]. •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, irrespective 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. 162 Z. Gazdag and M.A. Guti´errez-Naranjo Following the standard notations, the class of these P systems is denoted by AM0 −d,+mc,+antP ri, where −dindicates that dissolution rules are not used, +mc indicates the use of membrane creation and we add +antPri to denote the use of antimatter and annihilation rules with priority. 3 Recognizer P Systems We recall the main notions related to recognizer P systems and complexity in Membrane Computing. For a detailed description see, e.g., [18, 19]. A decision problem Xis a pair (IX, θX) such that IXis a language over a finite alphabet (whose elements are called instances) and θXis a total Boolean function over IX. A P system with input is a tuple (Π, Σ, iΠ), where Πis a P system, with working alphabet Γ, with pmembranes labelled by 1, . . . , p, and initial multisets M1,...,Mpassociated with them; Σis an (input) alphabet strictly contained in Γ; the initial multisets are over Γ−Σ; and iΠis the label of a distinguished (input) membrane. Let (Π, Σ, iΠ) be a P system with input, Γbe the working alphabet of Π,µits membrane structure, and M1,...,Mpthe initial multisets of Π. Let mbe a multiset over Σ. The initial configuration of (Π, Σ, iΠ)with input mis (µ, M1,...,MiΠ∪m, . . . , Mp). In the case of P systems with input and with external output, the above concepts are introduced in a similar way. Arecognizer P system is a P system with input and with external output such that: •The working alphabet contains two distinguished elements yes,no. •All its computations halt. •If Cis a computation of Π, then either the object yes or the object no (but not both) must have been released into the environment, and only in the last step of the computation. We say that Cis an accepting computation (respectively, rejecting computation) if the object yes (respectively, no) appears in the external environment associated to the corresponding halting configuration of C. A decision problem Xcan be solved in a polynomially uniform way by a family Π={Π(n)}n∈Nof P systems of type Fif the following holds: •There is a deterministic Turing machine Msuch that, for every n∈N, starting Mwith the unary representation of non its input tape, it constructs the P system Π(n) in polynomial time in n. •There is a deterministic Turing machine Nthat started with an instance I∈IX with size non its input tape, it computes a multiset wI(called the encoding of I) over the input alphabet of Π(n) in polynomial time in n. •For every instance I∈IXwith size n, starting Π(n) with wIin its input membrane, every computation of Π(n) halts and sends out to the environment yes if and only if Iis a positive instance of X. A Characterization of PSPACE with Antimatter 163 We denote by PMCFthe set of problems decidable in polynomial time using a polynomially uniform family of P systems of type F. 4 Solving QSAT In this section, we show that QSAT can be solved in linear time by a polynomially uniform family of recognizer P systems of type AM0 −d,+mc,+antP ri. The QSAT problem is the following one. Given a Boolean formula in conjunctive normal form over the propositional variables {x1, . . . , xn}. Then the fully (existentially) quantified Boolean formula associated to ϕis ϕ∗=∃x1∀x2. . . Qnxnϕ, (where Qnis ∃if nis odd, and it is ∀, otherwise). Now, the task is to decide if ϕ∗is true, i.e., to decide if there exists a truth assignment Iof the variables {xi|1≤i≤n, i is odd}such that each extension I∗of Ito the variables {xi|1≤i≤n, i is even}satisfies ϕ. Next, we construct a recognizer P system of type AM0 −d,+mc,+antP ri to solve QSAT. The construction is a variant of the one occurring in [9] where it is shown that QSAT can be solved in linear time using a family of P systems with membrane creation using dissolution rules. The main difference between the construction in [9] and the one in this paper is that instead of dissolution rules we use annihilation rules to control the computations. Similarly as in [9], the work of our P systems can be divided into three stages: •Generation and evaluation stage: Using membrane creation we construct a binary complete tree where the leaves encode all possible truth assignments associated with the formula. The values of the formula corresponding to these truth assignments are obtained in the corresponding leaves. Moreover, the nodes at even (resp. odd) levels from the root are codified by OR gates (respectively, AND gates). •Checking stage: In this stage the membrane structure corresponds to a Boolean circuit with gates AND and OR. We compute the values of the gates starting with the truth values computed at the leaves towards the root of the circuit which is the output gate. •Output stage: The system sends out to the environment the answer of the system computed in the previous stages. The evaluation stage will be the same as in [9], since there no dissolution rules are applied. In the other two stages we will use annihilation rules instead of using membrane dissolution. Let ϕ=C1∧ · · · ∧ Cmbe a Boolean formula in conjunctive normal form over nvariables. Then ϕcan be encoded as a multiset over the alphabet {xi,j , yi,j | 1≤i≤m, 1≤j≤n}, where xi,j (resp. yi,j) represents the fact that xj(resp. ¬xj) occurs in Ci(notice that since barred objects usually denote antimatters, we cannot use ¯xi,j to represent negated variables). Let us denote the above encoding of ϕby cod(ϕ). Let us moreover choose an appropriate pairing function h,ifrom 164 Z. Gazdag and M.A. Guti´errez-Naranjo N×Nto N. We construct a P system Π(hn, mi) processing the fully quantified formula ϕ∗associated with ϕ, when cod(ϕ) is supplied in its input membrane. The family presented here is: Π={(Π(hn, mi), Σ(hn, mi), i(hn, mi)) |(n, m)∈N2}, where the input alphabet is Σ(hn, mi) = {xi,j , yi,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), µ, ws, w<t,∨>, R(hn, mi)) is defined as follows: •Working alphabet: Γ(hn, mi) = Σ(hn, mi) ∪ {zj,c |j∈ {0,...n}, c ∈ {∧,∨}} ∪ {zj,c,l |j∈ {0, . . . , n −1}, c ∈ {∧,∨}, l ∈ {t, f}} ∪ {xi,j, yi,j, xi,j,l, yi,j,l |j∈ {1, . . . , n}, i ∈ {1, . . . , m}, l ∈ {t, f}} ∪ {ri, ri, ri,t, ri,f |i∈ {1, . . . , m}} ∪ {pi, qi, si, ti, ui, vi|i∈ {1,2,3}} ∪ {q2, p3, t2, s3, u2, v3} ∪ {ai|i∈ {0, . . . , n −1}} ∪ {bi,l |i∈ {1, . . . , n −1}, l ∈ {t, f}} ∪ {ci,j |i∈ {1, . . . , n −1}, j ∈ {1,...,5(n−i+ 1)}} ∪ {yes, no, yes∨, no∨, yes∧, no∧, yes∧, no∨}. •The set of labels: H(hn, mi) = {< l, c >|l∈ {t, f}, c ∈ {∧,∨}} ∪ {s}. •Initial membrane structure: µ= [ [ ]<t,∨>]s. •Initial multiset: ws=∅,w<t,∨>={a0z0,∧,t z0,∧,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}. With these rules the P system creates a nested membrane structure with 2ninner- most cells each of which corresponding to a truth assignment of the variables of the input formula. At the first step, 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 the second step these objects 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,t xi,j,f ]<l,c> [yi,j →yi,j,t yi,j,f ]<l,c> [ri→ri,t ri,f ]<l,c>      for l∈ {t, f}i∈ {1, . . . , m}, c∈ {∨,∧} j∈ {1, . . . , n}. These rules duplicate the objects representing the formula. One copy corresponds A Characterization of PSPACE with Antimatter 165 to the case when the variable is assigned true, the other copy corresponds to the case when it is assigned false. The objects riare also duplicated (ri,t, ri,f ) in order to keep track of those clauses that evaluate true on the previous assignments to the variables. 3. xi,1,t[ ]<t,c> →[ri]<t,c> yi,1,t[ ]<t,c> →[λ]<t,c> xi,1,f [ ]<f,c> →[λ]<f,c> yi,1,f [ ]<f,c> →[ri]<f,c>          for i∈ {1, . . . , m}, c∈ {∨,∧}. Using these rules the P system can evaluate which clauses are true under the possible (true or false) truth assignments of the corresponding variable. 4. xi,j,l[ ]<l,c> →[xi,j−1]<l,c> yi,j,l[ ]<l,c> →[yi,j−1]<l,c> ri,l[ ]<l,c> →[ri]<l,c>      for l∈ {t, f}, i ∈ {1, . . . , m}, c∈ {∨,∧}, j ∈ {2, . . . , n}. In order to analyse the next variable the second subscript of the objects xi,j,l and yi,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 truth assignments. 5.[zn,c →r1. . . rmp1q1]<l,c> for l∈ {t, f}and c∈ {∨,∧}. After the evaluation stage, these rules introduce antimatters zi,i∈ {1, . . . , m}, in the inner membranes. These antimatters will be used to check if there is a clause that is not satisfied by the corresponding truth assignment. 6.[riri→λ]<l,c> [ri→q2]<l,c> )for l∈ {t, f}, i ∈ {1, . . . , m}, c∈ {∨,∧} If an antimatter is not annihilated by the first rule, i.e., there is a clause that is not satisfied by the corresponding truth assignment, then this antimatter introduces the antimatter q2. 7.[q1→q2]<l,c> [p1→p2]<l,c> [q2q2→λ]<l,c> [p3p3→λ]<l,c> [p2→p3]<l,c> [p3→no]<l,c> [q2→q3p3]<l,c> [q3→yes]<l,c>                              for l∈ {t, f} c∈ {∨,∧} These rules introduce yes in an innermost cell with label < l, c > if and only if the antimatter q2is not present in this cell. On the other hand, if q2is in 166 Z. Gazdag and M.A. Guti´errez-Naranjo the cell, then object no is introduced. Since q2is introduced if and only if the corresponding truth assignment does not satisfy all the clauses of the formula, the appearance of yes or no in this cell indicates correctly whether the corresponding truth assignment satisfies the formula or not. 8.[yes]<l,c> →yesc[ ]<l,c> [no]<l,c> →noc[ ]<l,c> )for l∈ {t, f} c∈ {∨,∧} These rules with the rules in groups 9and 10 below will be used to check whether an appropriate combination of truth assignments according to the quantifiers ∃ and ∀are founded or not. 9.[yes∧yes∧→λ]<l,∧> [t1→t2]<l,∧> [s1→s2]<l,∧> [t2→t3s3]<l,∧> [s2→s3]<l,∧> [t3]<l,∧>→yes∨[ ]<l,∧> [yes∧→t2]<l,∧> [s3]<l,∧>→no∨[ ]<l,∧> [t2t2→λ]<l,∧> [s3s3→λ]<l,∧>                                        for l∈ {t, f} 10.[no∨no∨→λ]<l,∨> [u1→u2]<l,∨> [v1→v2]<l,∨> [u2→u3v3]<l,∨> [v2→v3]<l,∨> [u3]<l,∨>→no∧[ ]<l,∨> [no∨→u2]<l,∨> [v3]<l,∨>→yes∧[ ]<l,∨> [u2u2→λ]<l,∨> [v3v3→λ]<l,∨>                                        for l∈ {t, f} 11.[ai→bi+1,t bi+1,f ci+1,1]<l,c> bi+1,l [ ]<l,c> →[ai+1]<l,c> )for l∈ {t, f}, i ∈ {0, . . . , n −2}, c∈ {∨,∧} These rules with the rules in groups 12-14 below will be used to introduce the multisets s1t1yes2 ∧and u1v1no2 ∨in the appropriate membranes. These multisets will be used then by rules in groups 9and 10, respectively. Since these multisets will be needed at different levels in the membrane structure in different time steps, we need to employ a counter ci,j for the appropriate timing (see also the A Characterization of PSPACE with Antimatter 167 groups below). 12.[an−1→cn−1,1]<l,c> for l∈ {t, f}, c ∈ {∨,∧} 13.[ci,j →ci,j+1]<l,c> for l∈ {t, f}, i ∈ {1, . . . , n}, c∈ {∨,∧}, j ∈ {1,...,5n−5i+ 4} 14.[cn−k,5k+5 →s1t1yes2 ∧]<l,∧> [cn−k,5k+5 →u1v1no2 ∨]<l,∨>)for l∈ {t, f} k∈ {0, . . . , n −1} 15.[yes∧]s→yes [ ]s [no∧]s→no [ ]s. These rules are used to send out the computed answer to the environment. 4.1 A Short Overview of the Computation The initial configuration only has two membranes, the skin and an elementary membrane with label < t, ∨>. Labels have two types of information. On the one hand, the first symbol can be tor f, (true of false) and the second symbol can be ∧or ∨to denote if the corresponding variable is universally or existentially quantified. Membrane creation rules are applied in parallel in order to obtain a binary tree like structure of membranes enclosed in the skin. In the 2n-th step of the computation, 2nelementary membranes are created. One for each possible truth assignment of the variables. The key set of rules for the evaluation of the variables is the set 3. According to this set of rules, a symbol rjis produced for each variable such that its truth value makes true the clause Cj. Each of the 2nelementary membranes in the configuration after 2nsteps can be seen as one of the possible truth assignments for the variables and the set of different rjobjects inside represent the set of clauses satisfied by the corresponding truth assignment. In order to check if all the clauses are satisfied, a set with all the antiparticle rjobjects is generated in each elementary membrane. If all of these rj objects are annihilated, it means that in this elementary membrane there were all the objects rj(maybe with multiple copies). This means that the truth assignment associated with the elementary membrane satisfies all the clauses. Otherwise, if any rjis not consumed after the annihilation process, then we conclude that the corresponding assignment does not satisfy the corresponding clause. A set of technical rules produce an object yes or no inside each elementary membrane. The target of most of these rules is to control that only one object yes or no is generated, regardless the possible combination of multiple copies of rjin the membrane. Once the objects yes and no are generated in the elementary membranes, they are sent up in the tree-like membrane structure. When two of these objects arrive to an intermediate membrane, a new object yes or no is sent up, according to the label of the membrane. Such label encodes the type of quantification (universal or existential) of the corresponding variable. This stage is controlled by rules from the sets 9and 10. 174 Z. Gazdag and M.A. Guti´errez-Naranjo the computation is considered. The first parameter is an index of a membrane in Cj. The last two parameters are those sets of objects that are involved by the communications between this membrane and its children in the step from Cjto Cj+1. 1. procedure CommWithChildren((h1i1,1. . . i1,j , . . . , hkik,1. . . ik,j ), j, X, Y ) 2. for each gl1,1. . . l1,j , where g∈H, l1,1, . . . , l1,j ∈H∪Ndo 3. Sc←Content((gl1,1. . . l1,j , h1i1,1. . . i1,j, . . . , hkik,1. . . ik,j ), j); 4. if Sc6=nil then 5. Y0←∅; 6. TryRules(g, ann, Sc, Y 0, Y 0); 7. TryRules(g, evo, Sc, Y 0, Y 0); 8. TryRules(g, out com, Sc, Y 0, Y ); 9. TryRules(g, in com, Y 0, Y 0, X); // We apply rules of type ann and evo to keep the computation deterministic; membrane creation rules are skipped as they do not contribute to the content of the parent membrane stored in X; in-communication rules involve only the content of the parent membrane; 10. end if 11. end for Finally, we present the procedure Ato decide if Π(n) sends out to the environment yes on a given input multiset m. We assume without loss of generality that those rules that send out to the environment yes (resp. no) have the form [yes ]s→yes (resp. [ yes ]s→yes), where sis the label of the skin membrane. 1. procedure A(Π(n)) // Π(n)=(Γ, H, µ, W, hi, R) is a recognizer P systems of type AM−d,+mc,+antP ri with input multiset m 2. s←the label of the skin in µ; 3. S←∅; 4. for each j= 1,2, . . . do 5. S←Content((si1. . . ij), j) where i1= 1, . . . , ij= 1; 6. if yes ∈Sand there is a rule [ yes ]s→yes then output: yes;exit 7. end if 8. if no ∈Sand there is a rule [ no ]s→no then output: no;exit 9. end if 10. end for First we show that Ahalts on Π(n) and m. Since Content recursively calls itself with a decreasing second parameter and Content with second parameter 1 exits after finite steps, we can conclude that Content always exits after finite steps. Moreover, since Π(n) is a recognizer P system, it halts in lsteps, for an appropriate number l. Thus the multiset content of the skin of Πshould contain yes or no after at most l−1 steps. Therefore, l+ 1 is the highest number that occurs as a second parameter in the calls of Content in A. This means that A stops after a finite number of steps. A Characterization of PSPACE with Antimatter 175 Next we discuss the space complexity of A. Let Π={Π(n)}n∈Nbe a polynomially uniform family of P systems of type AM−d,+mc,+antP ri. By definition, there is a polynomial p(n) such that the size of the initial configuration of Π(n) containing an encoding of a formula in its input membrane is upper bounded by p(n). Moreover, there is a polynomial t(n) such that the running time of Π(n) is upper bounded by t(n). Let C=C1, . . . , Clbe a halting computation of Π(n), for some l≤t(n), and Mbe a membrane in Ci(i∈ {1, . . . , l}). Then the index w=fC(M) contains at most k+i−1 components, where k=d(C1). Clearly, kis upper bounded by p(n). Moreover, every component of wis a word with length at most t(n) + 2. It follows then that wcontains at most (p(n)+t(n)−1)·(t(n)+2) letters. Clearly, for every i∈ {1, . . . , l}, the size of Ciis at most p(n)O(t(n)) (the size of a configuration is the sum of the number of objects and membranes in the configuration). Thus, every letter in wthat is contained in Nis at most p(n)k·t(n), for some appropriate constant k. Therefore, storing a letter of a word in wneeds at most log(p(n)k·t(n)) = O(nt(n)) bits (notice that the first letters of the words in ware labels and the number of different labels is bounded by p(n)). This implies that the index wcan be stored using at most O((p(n) + t(n)) ·t(n)·nt(n)) bits, i.e., the number of necessary bits is polynomial in n. Therefore, on every level of the recursion in the function Content, the number of bits that is used to store the parameters is upper bounded by an appropriate polynomial. Moreover, the depth of the recursion in Content is bounded by the poynomial t(n). It follows, that the space complexity of Ais bounded by a polinomial too. 6 Conclusions and Future Work In this paper, we have proved that the family of P systems with membrane creation and annihilation rules characterizes the complexity class PSPACE. In [5] it has been proved that P systems with active membranes without polarizations, without dissolution and with division of elementary and non-elementary membranes endowed with antimatter and annihilation rules can solve NP-complete problems. It is an interesting research topic to explore the exact computational power of these systems. It seems that these systems can only solve problems in PSPACE. On the other hand, solving a PSPACE-complete problem with these systems seems to be a challenging task. Acknowledgements MAGN acknowledges the support of the project TIN2012-37434 of the Ministerio de Econom´ıa y Competitividad of Spain. 176 Z. Gazdag and M.A. Guti´errez-Naranjo References 1. Alhazov, A., Aman, B., Freund, R.: P systems with anti-matter. In: Gheorghe, M., Rozenberg, G., Salomaa, A., Sos´ık, P., Zandron, C. (eds.) Membrane Computing - 15th International Conference, CMC 2014, Prague, Czech Republic, August 20-22, 2014, Revised Selected Papers. Lecture Notes in Computer Science, vol. 8961, pp. 66–85. Springer (2014) 2. Alhazov, A., Aman, B., Freund, R., P˘aun, Gh.: Matter and anti-matter in membrane systems. In: DCFS 2014. Lecture Notes in Computer Science, vol. 8614, pp. 65–76. Springer (2014) 3. Berman, L.: The complexity of logical theories. Theoretical Computer Science 11, 71–77 (1980) 4. Blizard, W.D.: Negative membership. Notre Dame Journal of Formal Logic 31(3), 346–368 (1990) 5. D´ıaz-Pernil, D., Pe˜na-Cantillana, F., Alhazov, A., Freund, R., Guti´errez-Naranjo, M.A.: Antimatter as a frontier of tractability in membrane computing. Fundamenta Informaticae 134, 83–96 (2014) 6. Freund, R., P˘aun, Gh., Rozenberg, G., Salomaa, A. (eds.): Membrane Computing, 6th International Workshop, WMC 2005, Vienna, Austria, July 18-21, 2005, Revised Selected and Invited Papers, Lecture Notes in Computer Science, vol. 3850. Springer, Berlin Heidelberg (2006) 7. Gott, J.: Time Travel in Einstein’s Universe: The Physical Possibilities of Travel Through Time. Houghton Mifflin (2001) 8. Guti´errez-Naranjo, M.A., P´erez-Jim´enez, M.J., Riscos-N´u˜nez, A., Romero-Campero, F.J.: On the power of dissolution in P systems with active membranes. In: Freund et al. [6], pp. 224–240 9. Guti´errez-Naranjo, M.A., P´erez-Jim´enez, M.J., Romero-Campero, F.J.: A linear solution for QSAT with membrane creation. In: Freund et al. [6], pp. 241–252 10. Guti´errez-Naranjo, M.A., P´erez-Jim´enez, M.J., Romero-Campero, F.J.: A linear solution of subset sum problem by using membrane creation. In: Mira, J., ´ Alvarez, J.R. (eds.) IWINAC (1). Lecture Notes in Computer Science, vol. 3561, pp. 258–267. Springer, Berlin Heidelberg (2005) 11. Guti´errez-Naranjo, M.A., P´erez-Jim´enez, M.J., Romero-Campero, F.J.: A uniform solution to SAT using membrane creation. Theoretical Computer Science 371(1-2), 54–61 (2007) 12. Ito, M., Mart´ın-Vide, C., P˘aun, G.: A characterization of parikh sets of ET0L languages in terms of P systems. In: Ito, M., P˘aun, G., Yu, S. (eds.) Words, Semigroups, and Transductions - Festschrift in Honor of Gabriel Thierrin. pp. 239–253. World Scientific (2001) 13. Loeb, D.: Sets with a negative number of elements. Advances in Mathematics 91, 64–74 (1992) 14. Luisi, P.: The chemical implementation of autopoiesis. In: Fleischaker, G., Colonna, S., Luisi, P. (eds.) Self-Production of Supramolecular Structures, NATO ASI Series, vol. 446, pp. 179–197. Springer Netherlands (1994) 15. Metta, V.P., Krithivasan, K., Garg, D.: Computability of spiking nueral P systems with anti-spikes. New Mathematics and Natural Computation (NMNC) 08(03), 283– 295 (2012) 16. Mutyam, M., Krithivasan, K.: P systems with membrane creation: Universality and efficiency. In: Margenstern, M., Rogozhin, Y. (eds.) MCU. Lecture Notes in Computer Science, vol. 2055, pp. 276–287. Springer (2001) A Characterization of PSPACE with Antimatter 177 17. Pan, L., P˘aun, Gh.: Spiking neural P systems with anti-spikes. International Journal of Computers, Communications & Control IV(3), 273–282 (September 2009) 18. P´erez-Jim´enez, M.J.: An approach to computational complexity in membrane computing. In: Mauri, G., P˘aun, Gh., P´erez-Jim´enez, M.J., Rozenberg, G., Salomaa, A. (eds.) Workshop on Membrane Computing. Lecture Notes in Computer Science, vol. 3365, pp. 85–109. Springer (2004) 19. P´erez-Jim´enez, M.J., Riscos-N´u˜nez, A., Romero-Jim´enez, A., Woods, D.: Complexity - membrane division, membrane creation. In: P˘aun, Gh., Rozenberg, G., Salomaa, A. (eds.) The Oxford Handbook of Membrane Computing, pp. 302 – 336. Oxford University Press, Oxford, England (2010) 20. P˘aun, Gh.: Some quick research topics., In these proceedings. 21. P˘aun, G.: Four (somewhat nonstandard) research topics. In: Macc´ıas-Ramos, L.F., del Amor, M.A.M., P˘aun, G., Riscos-N´u˜nez, A., Valencia-Cabrera, L. (eds.) Twelfth Brainstorming Week on Membrane Computing. pp. 305–309. F´enix Editora, Sevilla, Spain (2014) 22. Song, T., Jiang, Y., Shi, X., Zeng, X.: Small universal spiking neural P systems with anti-spikes. Journal of Computational and Theoretical Nanoscience 10(4), 999–1006 (2013) 23. Sos´ık, P., Rodr´ıguez-Pat´on, A.: Membrane computing and complexity theory: A characterization of PSPACE. J. Comput. Syst. Sci. 73(1), 137–152 (2007) 24. Tan, G., Song, T., Chen, Z., Zeng, X.: Spiking neural P systems with anti-spikes and without annihilating priority working in a ’flip-flop’ way. International Journal of Computing Science and Mathematics 4(2), 152–162 (Jul 2013)