Polarizationless P Systems with Active Membranes Working in the Minimally Parallel Mode

Polarizationless P Systems with Active Membranes Working in the Minimally Parallel Mode Rudolf Freund1, Gheorghe P˘aun2,3, Mario J. P´erez-Jim´enez3 1Institute of Computer Languages Vienna University of Technology Favoritenstr. 9, Wien, Austria [email protected] 2Institute of Mathematics of the Romanian Academy PO Box 1-764, 014700 Bucure¸sti, Romania, and [email protected], [email protected] 3Department of Computer Science and Artificial Intelligence University of Sevilla Avda. Reina Mercedes s/n, 41012 Sevilla, Spain [email protected] Summary. We investigate the computing power and the efficiency of P systems with active membranes without polarizations, working in the minimally parallel mode. We prove that such systems are computationally complete and able to solve NP-complete problems even when the rules are of a restricted form, e.g., for establishing computational completeness we only need rules handling single objects and no division of non-elementary membranes is used. 1 Introduction P systems with active membranes basically use five types of rules: (a) evolution rules, by which a single object evolves to a multiset of objects, (b) send-in, and (c) send-out rules, by which an object is introduced in or expelled from a membrane, maybe modified during this operation into another object, (d) dissolution rules, by which a membrane is dissolved, under the influence of an object, which may be modified into another object by this operation, and (e) membrane division rules; this last type of rules can be used both for elementary and non-elementary membranes, or only for elementary membranes. As introduced in [10], all these types of rules also use polarizations for membranes, “electrical charges” +,−,0, controlling the application of the rules. Systems with rules of types (a), (b), (c) were shown to be equivalent in computational power with Turing machines [11], even when using only two polarizations 132 R. Freund, Gh. P˘aun, M.J. P´erez-Jim´enez [4], while P systems using all types of rules were shown to be universal even without using polarizations [1]. Another important class of results concerns the possibility of using P systems with active membranes to provide polynomial solutions to computationally hard problems. Several papers have shown that both decision and numerical NP-complete problems can be solved in a polynomial time (often, even linear time) by means of P systems with three polarizations [11], [13], then the number of polarizations was decreased to two [3], [4]. The systems constructed in these solutions use only division of elementary membranes. At the price of using division also for non-elementary membranes, the polarizations can be completely removed, [2]. All papers mentioned above apply the rules in the maximally parallel mode: in each step, the assignment of objects to the rules in the chosen multiset of rules to be applied in parallel is maximal, i.e., no further rule could be added to this chosen multiset of rules in such a way that the rules in the resulting extended multiset still could be applied in parallel. Recently, [5] a more relaxed strategy of using the rules was introduced, the so-called minimal parallelism: in each step, the assignment of objects to the rules in the chosen multiset of rules to be applied in parallel does not allow for extending it by any rule out of a set of rules from which no rule has been chosen so far for this multiset of rules. This introduces an additional degree of non-determinism in the system evolution, but still computational completeness and polynomial solutions to SAT were obtained in the new framework by using P systems with active membranes, with three polarizations and division of only elementary membranes. In this paper we continue the study of P systems working in the minimally parallel way, and we prove that the polarizations can be avoided, at the price of using all five types of rules for computational completeness and the division of non-elementary membranes for computational efficiency. Moreover, in the proof for establishing computational completeness we restrict the form of the rules to handling only single objects in all types of rules (we call this the one-normal form for P systems with active membranes). 2 Prerequisites We suppose that the reader is familiar with the basic elements of Turing computability [6], and of membrane computing [11]. We here, in a rather informal way, introduce only the necessary notions and notation. For an alphabet A, by A∗we denote the set of all strings of symbols from A including the empty string λ. A multiset over an alphabet Ais a mapping from Ato the set of natural numbers; we represent a multiset by a string from A∗, where the number of occurrences of a symbol a∈Ain a string wrepresents the multiplicity of ain the multiset represented by w(hence, all strings obtained by permuting symbols in the string wrepresent the same multiset). The family of Turing-computable sets of natural numbers is denoted by NRE (with RE coming from “recursively enumerable”). Polarizationless P Systems with Active Membranes 133 In our proofs showing computational completeness we use the characterization of NRE by means of register machines. Such a device consists of a given number of registers, each of which can hold an arbitrarily large natural number, and a set of labeled instructions which specify how the numbers stored in registers can change, and which instruction should follow after the instruction just carried out. There are three types of instructions: •li: (ADD(r), lj, lk) add 1 to register r, and then go to one of the instructions labeled by ljand lk, non-deterministically chosen; •li: (SUB(r), lj, lk) if register ris non-empty (non-zero), then subtract 1 from it and go to the instruction labeled by lj, otherwise go to the instruction labeled by lk; •lh:HALT the halt instruction. Aregister machine is a construct M= (n, B, l0, lh, I), where nis the number of registers, Bis the set of instruction labels, l0is the start label, lhis the halt label (assigned to HALT only), and Iis the set of instructions. Each label of Blabels only one instruction from I, thus precisely identifying it. A register machine M generates a set N(M) of numbers in the following way: having initially all registers empty (i.e., storing the number zero), start with the instruction labeled by l0, and proceed to apply instructions as indicated by the labels and by the contents of registers. If we reach the halt instruction, then the number stored at that time in register 1 is said to be computed by M, and therefore it is introduced in N(M). Since we have a non-deterministic choice in the continuation of the computation in the case of ADD instructions, N(M) can be an infinite set. It is known (see [8]) that in this way we can compute all the sets of numbers which are Turing-computable, even using register machines with only three registers as well as registers two and three being empty whenever the register machine halts. A register machine can also work in the accepting mode. The number to be accepted is introduced in register 1, with all other registers being empty. We start computing with the instruction labeled by l0; if the computation halts, then the number is accepted (the contents of the registers in the halting configuration do not matter). We still denote by N(M) the set of numbers accepted by a register machine M. In the accepting case, we can request the register machines to be deterministic, namely with all instructions li: (ADD, lj, lk) having lj=lk. It is known that deterministic accepting register machines characterize NRE even with only three registers and all registers being empty whenever the register machine halts. 3 P Systems with Active Membranes We first introduce the P systems with active membranes in the general form, and then we describe the restricted version we investigate in this paper. 134 R. Freund, Gh. P˘aun, M.J. P´erez-Jim´enez AP system with active membranes, of the initial degree n≥1, is a construct of the form Π= (O, H, µ, w1, . . . , wn, R, ho), where: 1. Ois the alphabet of objects; 2. His a finite set of labels for membranes; 3. µis a membrane structure, consisting of nmembranes having initially neutral polarizations, labeled (not necessarily in a one-to-one manner) with elements of H; 4. w1, . . . , wnare strings over O, describing the multisets of objects placed in the ninitial regions of µ; 5. Ris a finite set of developmental rules, of the following forms: (a) [ha→v]e h, for h∈H, e ∈ {+,−,0}, a ∈O, v ∈O∗ (object evolution rules, associated with membranes and depending on the label and the charge of the membranes, but not directly involving the membranes, in the sense that the membranes are neither taking part in the application of these rules nor are they modified by them); (b) a[h]e1 h→[hb]e2 h, for h∈H, e1, e2∈ {+,−,0}, a, b ∈O (in communication rules; a possibly modified object is introduced in a membrane; the polarization of the membrane can also be modified, but not its label); (c) [ha]e1 h→b[h]e2 h, for h∈H, e1, e2∈ {+,−,0}, a, b ∈O (out communication rules; a possibly modified object is sent out of the membrane; the polarization of the membrane can also be modified, but not its label); (d) [ha]e h→b, for h∈H, e ∈ {+,−,0}, a, b ∈O (dissolving rules; in reaction with an object, a membrane can be dissolved, while the object specified in the rule can be modified); (e) [ha]e1 h→[hb]e2 h[hc]e3 h, for h∈H, e1, e2, e3∈ {+,−,0}, a, b, c ∈O (division rules for elementary or non-elementary membranes; in reaction with an object, the membrane with label his divided into two membranes with the same label, possibly of different polarizations; the object specified in the rule is replaced in the two new membranes by possibly new objects; the remaining objects may evolve in the same step by rules of type (a) and the result of this evolution is duplicated in the two new membranes; if membrane hcontains other membranes, then they may evolve at the same time by rules of any type and the result of their evolution is duplicated in the two new membranes); Polarizationless P Systems with Active Membranes 135 6. ho∈Hor ho=env indicates the output region. In the maximally parallel mode, in each step (a global clock is assumed) we apply multisets of rules in such a way that no further rule can be applied to the remaining objects or membranes. In each step, each object and each membrane can be involved in only one rule. Because this way of using the rules is standard in membrane computing, we do not give further details, and we present only the minimally parallel mode, which here means the following: All the rules of any type involving a membrane hconstitute the set Rh(this means all the rules of type (a) of the form [ha→v]e h, all the rules of type (b) of the form a[h]e1 h→[ha]e2 h, and all the rules of types (c) – (e) of the form [ha]e h→z, with the same h, constitute the set Rh). Moreover, if a membrane happears several times in a given configuration of the system, then for each occurrence of the membrane we consider a different set Rh; this means that we identify the ith copy of membrane hwith the pair (h, i), and we consider the set of rules Rh,i =Rh. Then, in each step, we choose a multiset of rules taken from the sets Rh,i,h∈H, in such a way that after having assigned objects to all the rules in this multiset, no rule from any of the sets Rh,i from which no rule has been taken so far, could be used in addition. Whenever relevant, in order to make visible the sets of rules, we write explicitly the sets Rh,h∈H, instead of the global set R. Of course, as usual for P systems with active membranes, each membrane and each object can be involved in only one rule, and the choice of rules to be used and of objects and membranes to evolve is done in a non-deterministic way. We should note that for rules of type (a) the membrane is not considered to be involved: when applying [ha→v]h, the object acannot be used by other rules, but the membrane hcan be used by any number of rules of type (a) as well as by one rule of types (b) – (e). In each step, the use of rules is done in the bottom-up manner (first the inner objects and membranes evolve, and the result is duplicated if any surrounding membrane is divided). A halting computation provides a result given by the number of objects present in region hoat the end of the computation; this is a region of the system if ho∈H (and in this case, for a computation to be successful, exactly one membrane with label hoshould be present in the halting configuration), or it is the environment if ho=env. We shall also consider the following normal form for P systems with active membranes: A system Πis said to be in the one-normal form if the membranes have no polarization (it is the same as saying that always all membranes have the same polarization, say 0, which therefore is irrelevant and thus omitted) and the rules are of the forms [ha→b]h,a[h]h→[hb]h, [ha]h→b[h]h, [ha]h→b, and [ha]h→[hb]h[hc]h, for a, b, c ∈O, such that a6=b, a 6=c, b 6=c. Note that the labels of membranes are never changed. The set of numbers generated in the minimally parallel way by a system Π is denoted by Nmin(Π). The family of sets Nmin(Π), generated by systems with 136 R. Freund, Gh. P˘aun, M.J. P´erez-Jim´enez rules of the non-restricted form, having initially at most n1membranes and using configurations with at most n2membranes during any computation is denoted by NminOPn1,n2((a),(b),(c),(d),(e)); when a type of rules is not used, it is not mentioned in the notation. If any of the parameters n1, n2is not bounded, then it is replaced by ∗. If the systems do not use polarizations for membranes, then we write (a0),(b0),(c0),(d0),(e0) instead of (a),(b),(c),(d),(e). When the system Π is in the one-normal form, then we write NminOPn1,n2((a1),(b1),(c1),(d1),(e1)). When considering families of numbers generated by P systems with active membrane working in the maximally parallel mode, the subscript min is replaced by max in the previous notations. For precise definitions, we refer to [11] and to the papers mentioned below. 4 Computational Completeness The following results are well known: Theorem 1. (i)NmaxOP3,3((a),(b),(c)) = NRE, [11]. (ii)NmaxOP∗,∗((a0),(b0),(c0),(d0),(e0)) = NRE, [1]. (iii)NminOP3,3((a),(b),(c)) = NRE, [5]. In turn, the following inclusions follow directly from the definitions: Lemma 1. NmodeOPn1,n2((a1),(b1),(c1),(d1),(e1)) ⊆ NmodeOPn1,n2((a0),(b0),(c0),(d0),(e0)) ⊆ NmodeOPn1,n2((a),(b),(c),(d),(e)), for all n1, n2≥1,mode ∈ {max, min}. We now improve the equalities from Theorem 1 in certain respects, starting with proving the computational completeness of P systems with active membranes in the one-normal form when working in the maximally parallel mode, and then we extend this result to the minimal parallelism. Theorem 2. NmaxOPn1,∗((a1),(b1),(c1),(d1),(e1)) = NRE, for all n1≥5. Proof. We only prove the inclusion NRE ⊆NmaxOP5,∗((a1),(b1),(c1),(d1),(e1)). Let us consider a register machine M= (3, B, l0, lh, I) generating an arbitrary set N(M)∈NRE. We then construct the P system Π= (O, H, µ, ws, wh, w1, w2, w3, R, env), of the initial degree 5, with Polarizationless P Systems with Active Membranes 137 O={di|0≤i≤5}∪{g, #,#0, p, p0, p00, c, c0, c00} ∪ B∪ {l0|l∈B} ∪ {liu |liis the label of an ADD instruction in I, 1≤u≤4} ∪ {liu0|liis the label of a SUB instruction in I, 1≤u≤4} ∪ {liu+|liis the label of a SUB instruction in I, 1≤u≤6}, H={s, h, 1,2,3}, µ= [s[1]1[2]2[3]3[h]h]s, ws=l0d0, wα=λ, for all α∈H− {s}, and with the rules constructed as described below. The value stored in a register r= 1,2,3 of M, in Πis represented by the number of copies of membranes with label rplus one (if the value of the register ris k, then we have k+ 1 membranes with label r). The membrane with label h is auxiliary, it is used for controlling the correct simulation of instructions of M by computations in Π. Each step of a computation in M, i.e., using an ADD or a SUB instruction, corresponds to six steps of a computation in Π. We start with all membranes being empty, except for the skin region, which contains the initial label l0of Mand the auxiliary object d0. If the computation in Mhalts, that is, the object lhappears in the skin region of Π, then we pass to producing one object cfor each membrane with label 1 present in the system, except one; in this way, the number of copies of csent to the environment represents the correct result of the computation in M. We first indicate the rules used in each of the six steps of simulating instructions ADD and SUB, and then we present the rules for producing the result of the computation; in each configuration, only the membranes and the objects relevant for the simulation of the respective instruction are specified. In particular, we ignore the “garbage” object g, because once introduced it remains idle for the whole computation. The simulation of an instruction li: (ADD(r), lj, lk) uses the rules from Table 1. Table 1. The simulation of an ADD instruction Step Main rules Auxiliary rules Configuration – – – [slid0[r]r... [h]h]s 1li[r]r→[rl0 i]r[sd0→d1]s[sd1[rl0 i]r... [h]h]s 2 [rl0 i]r→[rli1]r[rg]r[sd1→d2]s[sd2[rli1]r[rg]r... [h]h]s 3 [rli1]r→li2[r]rd2[h]h→[hd3]h[sli2[r]r[r]r... [hd3]h]s 4 [sli2→li3]s[hd3]h→d4[h]h[sli3d4[r]r[r]r... [h]h]s 5 [sli3→li4]s[sd4→d5]s[sli4d5[r]r[r]r... [h]h]s 6 [sli4→lt]s, t ∈ {j, k}[sd5→d0]s[sltd0[r]r[r]r... [h]h]s 138 R. Freund, Gh. P˘aun, M.J. P´erez-Jim´enez The label object lienters into the correct membrane r(even if the register ris empty, there is at least one membrane with label r) and in the next step divides it. The object li2exits the newly produced membrane, but gremains inside; li2will evolve three further steps, just to synchronize with the evolution of the auxiliary objects du, u ≥0, and the auxiliary membrane h, so that in the sixth step we end with the label ljor lkof the next instruction to be simulated present in the skin membrane, together with d0; note that the number of copies of membrane rwas increased by one. ' & $ % d3 d3→# #→#0 #0→# d2 d1 d0d4d5d0 - - - - - - 123 4 5 6 h Fig. 1. The evolution of auxiliary objects The auxiliary objects du, u ≥0, and the auxiliary membrane hare used in the simulation of SUB instructions, as we will see immediately; in step 4, there also are other rules to be used in membrane h, introducing the trap-object #, but using such rules will make the computation never halt, hence, they will not produce an unwanted result. The evolution of objects du, u ≥0, is represented graphically in Figure 1; membrane his only used in step 3, to send an object inside, and in the next step, for sending an object out of it. On each arrow we indicate the step, according to Table 1; the steps made by using rules of types (b), (c) are pointed out by drawing the respective arrows crossing the membranes, thus suggesting the in/out actions. The way the “ADD module” works is suggested in Figure 2; the division operation from step 2 is indicated by a branching arrow. The simulation of an instruction li: (SUB(r), lj, lk) is done with the help of the auxiliary membrane h. The object lienters a membrane r(there is at least one copy of it) and divides it, and on this occasion makes a non-deterministic choice between trying to continue as having register rnon-empty or as having it empty. If the guess has been correct, then the correct action is done (decrementing the register in the first case, doing nothing in the second case) and the correct next label is introduced, i.e., ljor lk, respectively. If the guess has not been correct, then the trap object # is introduced. For all membranes xof the system we consider the rules [x#→#0]x, [x#0→#]x, hence, the appearance of # will make the computation last forever. Polarizationless P Systems with Active Membranes 139 li         r l0 i li1g li2 6 @ @I   6 -li3-li4 lj/lk ? rr 1 2 3 45 6 Fig. 2. The work of the ADD module In Table 2 we present the rules used in the case of guessing that the register ris not empty. Like in the case of simulating an ADD instruction, the auxiliary objects and membranes do not play any role in this case. Table 2. The simulation of a SUB instruction, guessing that register ris not empty Step Main rules Auxiliary rules Configuration – – – [slid0[r]r...[h]h]s 1li[r]r→[rl0 i]r[sd0→d1]s[sd1[rl0 i]r...[h]h]s 2 [rl0 i]r→[rli1+]r[rli2+]r[sd1→d2]s[sd2[rli1+]r[rli2+]r...[h]h]s 3 [rli1+]r→li3+ d2[h]h→[hd3]h [rli2+]r→li4+[r]r[sli3+li4+[r]r...[hd3]h]s 4li3+[r]r→[rg]r[hd3]h→d4[h]h li4+[r]r→[rli5+]r[sd4[rli5+]r[rg]r...[h]h]s or [sli3+ →#]s,[sli4+ →#]s[sd4#[r]r...[h]h]s 5 [rli5+]r→li6+ [sd4→d5]s[sd5li6+[r]r...[h]h]s 7 [sli6+ →lj]s[sd5→d0]s[sljd0[r]r...[h]h]s In step 2 we divide the membrane rcontaining the object l0 iand the objects li1+, li2+ are introduced in the two new membranes. One of them is immediately dissolved, thus the number of copies of membrane rremains unchanged; the objects li3+, li4+ are introduced in this step. In the next step (the fourth one of the simulation), objects li3+, li4+ look for membranes rin the skin region. If both of them find such membranes – and this is the correct/desired continuation – then both of them enter such membranes; li3+ becomes gand li4+ becomes li5+. If only 146 R. Freund, Gh. P˘aun, M.J. P´erez-Jim´enez li    li      6 @ @I   li10 li20 li10 l120 6 6 li30       / 1 r r 2 r 3δ3 4 5 r li30 li40       - @@ @R ? 4 5 r r 6 li40 #         A A A A A A A AK 6 - JJJ^ lk 7 h h 6 5 li40 lk 5 # d3 h    -- d2d3 - 3 4 5 h d4d0 - - 6 7 d1 d0 6 - 1 2d2 d3[h00 ]h00 →[h00 d3]h00 [h00 d3→#]h00 Fig. 8. The work of module SUB, when guessing that the register is empty, with equal objects in the rules 5.1 Solving SAT by Polarizationless P Systems Below we give an efficient semi–uniform solution to the satisfiability problem by using P systems with polarizationless active membranes working in the minimally parallel mode. Theorem 4. The satisfiability of any propositional formula in the conjunctive normal form, using nvariables and mclauses, can be decided in a linear time with respect to nby a polarizationless P system with active membranes, constructed in a semi-uniform way in linear time with respect to nand m, and working in the minimally parallel mode. Proof. Let us consider a propositional formula ϕ=C1∧. . . ∧Cmsuch that each clause Cj, 1 ≤j≤m, is of the form Cj=yj,1∨. . . ∨yj,kj,kj≥1, for yj,r ∈ {xi,¬xi|1≤i≤n}. For each i= 1,2, . . . , n, let us denote Polarizationless P Systems with Active Membranes 147         p0 p00 p0 p00 ccc ? - - S S So   @ @R δout δ 1 1 1 p 6 -       lh lhp 6 -- 11 δ   p0 h  XXX Xz     P P P Pi δ Fig. 9. The work of the final module, with equal objects in the rules t(xi) = {cj|there is r, 1≤r≤kj,such that yj,r =xi}, f(xi) = {cj|there is r, 1≤r≤kj,such that yj,r =¬xi}. These are the sets of clauses which assume the value true when xiis true, and false when xiis false, respectively. We construct the P system Π(ϕ) with the following components (the output membrane is not necessary, because the result is obtained in the environment): O={ai, fi, ti|1≤i≤n} ∪ {cj, dj|1≤j≤m} ∪ {pi|1≤i≤2n+ 7} ∪ {qi|1≤i≤2n+ 1} ∪ {ri|1≤i≤2n+ 5} ∪ {b1, b2, y, yes,no}, H={s, s0, p, q, r, 0,1,2, . . . , m}, µ= [s[s0[p]p[0[q]q[r]r[1]1[2]2. . . [m]m]0]s0]s, wp=p1, wq=q1, wr=r1, w0=a1, ws=ws0=wj=λ, for all j= 1,2, . . . , m. The set of evolution rules, R, consists of the following rules: (1) [pi→pi+1]p,for all 1 ≤i≤2n+ 6, [qi→qi+1]q,for all 1 ≤i≤2n, [ri→ri+1]r,for all 1 ≤i≤2n+ 4. These rules are used for evolving counters pi, qi, and riin membranes with labels p, q, and r, respectively. (2) [ai]0→[fi]0[ti]0,for all 1 ≤i≤n, [fi→f(xi)ai+1]0and [ ti→t(xi)ai+1]0,for all 1 ≤i≤n−1, 148 R. Freund, Gh. P˘aun, M.J. P´erez-Jim´enez [fn→f(xn)]0, [tn→t(xn)]0. The goal of these rules is to generate the truth assignments of the nvariables x1, . . . , xn, and to analyse the clauses satisfied by xiand ¬xi, respectively. (3) cj[ ]j→[cj]jand [ cj]j→dj, for all 1 ≤j≤m. In parallel with the division steps, if a clause Cjis satisfied by the previously expanded variable, then the corresponding object cjenters membrane jin order to dissolve it and to send objects djto membrane 0. (4) [q2n+1 ]q→q2n+1[ ]q, [q2n+1 →b1]0. By using these rules the counter qproduces an object b1in each membrane 0. (5) b1[ ]j→[b1]jand [ b1]j→b2, for all 1 ≤j≤m, [b2]0→b2. These rules allow to detect whether the truth assignment associated with a membrane 0 assigns the value false to the formula (in that case, the membrane 0 will be dissolved). (6) [p2n+7 ]p→p2n+7[ ]p, [p2n+7 ]s0→no[ ]s0, [no ]s→no[ ]s, [r2n+5 ]r→r2n+5, [r2n+5 ]0→y[ ]0, [y]s0→yes, [yes ]s→yes[ ]s. These rules produce the answer of the P system. An overview of the computations in the P system For the sake of readability, the initial configuration is given in Figure 10. The membranes with labels p, q, and r, with the corresponding objects pi, qi, and ri, respectively, are used as counters, which evolve simultaneously with the main membrane 0, where the truth assignments of the nvariables x1, . . . , xnare generated; the use of separate membranes for counters makes possible the correct synchronization even for the case of the minimal parallelism. The evolution of counters is done by the rules of type (1). In parallel with these rules, membrane 0 evolves by means of the rules of type (2). In odd steps (from step 1 to step 2n), we divide the (non-elementary) membrane 0 (with fi, ticorresponding to the truth values false, true, respectively, for variable xi); in even steps we introduce the clauses satisfied by xi,¬xi, respectively. When we divide membrane 0, all inner objects and membranes are replicated; in particular, all membranes with labels 1,2, . . . , m, as well as membranes qand r, are replicated, hence, they are present in all membranes with label 0. This process lasts 2nsteps. At the end of this phase, all 2ntruth assignments for the nvariables have been generated and they are encoded in membranes labeled by 0. Polarizationless P Systems with Active Membranes 149 ' & $ % ' & $ %    ' & $ %              s s0 p p1 0qr q1a1r1 1 2 m ... Fig. 10. The initial configuration of the system from the proof of Theorem 4 In parallel with the division steps, if a clause Cjis satisfied by the previously expanded variable, then the corresponding object cjenters membrane j, by means of the first rule of type (3), permitting its dissolution by means of the second rule of that type and sending objects djto membrane 0. This is done also in step 2n+ 1, in parallel with using the rules of type (1) and (4) for evolving membranes p, q, and r. In step 2n+2, the counters piand rikeep evolving and the second rule of type (4) produces an object b1in each membrane 0. Thus, after 2n+ 2 steps, the configuration C2n+2 of the system consists of 2ncopies of membrane 0, each of them containing the membrane pempty, the membrane rwith the object r2n+3, possible objects cjand dj,1≤j≤m, as well as copies of those membranes with labels 1,2, . . . , m corresponding to clauses which were not satisfied by the truth assignment generated in that copy of membrane 0. The membranes associated with clauses satisfied by the truth assignments generated have been dissolved by the corresponding object cj. Moreover, in that configuration the membrane pcontains the object p2n+3, and membranes s0and sare empty. Therefore, formula ϕis satisfied if and only if there is a membrane 0 where all membranes 1,2, . . . , m have been dissolved. In order to check this last condition, we proceed as follows. In step 2n+3 we use the first rule of type (5) which introduces the object b1in a membrane jwhich has not been dissolved (this is made in a non–deterministically manner). In parallel, the counters qand rfollow with evolving. The object b1 in membrane j(step 2n+ 4) dissolves that membrane producing an object b2in membrane 0. In step 2n+ 5 the counter r2n+5 exits from membrane rand, simultaneously, each membrane 0 containing an object b2is dissolved by the third rule of type (5). 150 R. Freund, Gh. P˘aun, M.J. P´erez-Jim´enez Then, formula ϕis satisfied if and only if in the configuration C2n+5 there exists a membrane 0 that has not been dissolved (and thus containing the object r2n+5). In the next step, the counter qievolves to q2n+7 in membrane q, and if there is a membrane 0 that has not been dissolved, the object r2n+5 sends an object y to membrane s0. On the contrary, only the counter qievolves. In step 2n+ 7 the counter p2n+7 exits from membrane pto membrane s0, by applying the first rule of type (6). If the formula ϕis satisfiable then an object ydissolves the membrane s0by applying the sixth rule of type (6) producing an object yes in the skin. In the next step, this object is sent to the environment and the P system halts. On the contrary, if membrane s0has not been dissolved, the object p2n+7 in membrane s0produces an object no in the skin, by using the second rule of type (6); in the next step an object no is sent to the environment and the system halts. Therefore, if the formula is satisfiable, then the object yes exits the system in step 2n+ 8, and, if the formula is not satisfiable, then the object no exits the system in step 2n+ 9. In both cases, this is the last step of the computation. The system Π(ϕ) uses 9n+2m+18 objects, m+6 initial membranes, containing in total 4 objects, and 8n+ 4m+ 21 rules. The length of any rule is bounded by m+ 3. Clearly, all computations stop (after at most 2n+ 9 steps) and all give the same answer, yes or no, to the question whether formula ϕis satisfiable, hence, the system is weakly confluent. These observations conclude the proof. ut Remark 1. 1. The system used in the previous proof is not in the one-normal form, because the rules of type (b) are of the form [ha→u]hwith ubeing an arbitrary multiset. Because the maximal length of such strings uis known (m+ 1), we can replace each rule of this form by mrules, each of them introducing two objects; using rules of the form [ha→b]h, we can also synchronize the applications of rules, hence, at the price of getting a computation mtimes longer, we can obtain a sort of two-normal form. Of course, the rules of types (b), (c), (d) can be also arranged to have either different objects or identical objects. We leave the details as a task for the reader, together with the more interesting issue of finding a polynomial solution to SAT by a system in the one-normal form. 2. Let us note that we can design a deterministic P system Π(ϕ) working in minimally parallel mode which decides the satisfiability of ϕ. To this aim, it is enough to have mcopies of the object b1in each membrane 0 of the configuration C2n+2. For that, the rule [ q2n+1 →b1]0can be replaced by [q2n+1 →bm 1]0. 3. As a consequence of Theorem 4 we obtain the inclusion of NP ∪co −NP in the class of all decision problems solvable in polynomial time in a semi–uniform way by a family of P systems with polarizationless active membranes working in the minimally parallel mode (let us recall that due to the confluence of the P systems solving a decision problem, every P system that decides an instance working in minimally parallel mode, also decides it working in the maximally parallel mode, but the reciprocal is not true). Polarizationless P Systems with Active Membranes 151 5.2 A Formal Verification In order to assure that the system Π(ϕ) decides the instance ϕ, two main properties must to be proved: (a) if there exists an accepting computation of the P system processing ϕ, answering yes, then the problem also answers yes for that instance (soundness), and (b) if the problem answers yes, then any computation of the P system processing that instance answers yes (completeness). Hence, the system Π(ϕ) must satisfy a condition of confluence: every computation of the system has the same output. To prove that the system Π(ϕ) is sound and complete with respect to the SAT problem, it is sufficient to show that a truth assignment makes true the formula ϕ if and only if in the configuration C2n+5 there is at least a membrane labeled by 0 that has not been dissolved. If σis a truth assignment on a set of variables {x1, . . . , xn}, then we write σ(xi) = for σ(xi) = t. Lemma 2. For each i(1 ≤i≤n)the following conditions hold true: 1. C2i−1(p) = {p2i},C2i−1(s) = C2i−1(s0) = ∅. 2. For each truth assignment σon {x1, . . . , xi}there exists a unique membrane 0 such that its contents is {(σ(xi))i}∪{dj|cj∈[ 1≤l≤i−2 (σ(xl))(xl)∧i≥3} ∪ {cj|cj∈\ 1≤l≤i−1 (σ(xl))(xl)∧i≥3}. Moreover, it inside contains a membrane labeled by qwhich contains the object q2i, a membrane labeled by rwhich contains the object r2i, and empty inner membranes j, where 1≤j≤m; moreover, if i≥2, then: (a) cj/∈\ 1≤l≤i−2 (σ(xl))(xl), (b) if cj∈(σ(xi−1))(xi−1)−\ 1≤l≤i−2 (σ(xl))(xl), then C2i−1(j) = {cj}. 3. C2i(p) = {p2i+1},C2i(s) = C2i(s0) = ∅. 4. For each truth assignment σon {x1, . . . , xi}there exists a unique membrane 0 such that its contents is {(σ(xi))(xi), ai+1}∪{dj|cj∈[ 1≤l≤i−1 (σ(xl))(xl)∧i≥2} ∪ {cj|cj∈\ 1≤l≤i−1 (σ(xl))(xl)∧i≥3}, where an+1 =λ. Furthermore, it contains inside a membrane labeled by qwhich contains the object q2i+1, a membrane labeled by rwhich contains the object r2i+1, and 152 R. Freund, Gh. P˘aun, M.J. P´erez-Jim´enez empty inner membranes j, where 1≤j≤m; moreover, if i≥2, then cj/∈ \ 1≤l≤i−1 (σ(xl))(xl). Proof. By induction on n. It is easy to prove the base case. Let us suppose that the result holds for i(1 ≤i < n). From the induction hypothesis, we deduce that the configuration C2i+1 is obtained from C2iby applying the rules [ p2i+1 →p2i+2]p, [q2i+1 →q2i+2]q, [r2i+1 →r2i+2]r, [ ai+1]0→[fi+1]0[ti+1]0, and cj[ ]j→[cj]j(1 ≤j≤m). Hence, we have C2i+1(p) = {p2i+2}and C2i+1(s) = C2i+1(s0) = ∅. Moreover, for each truth assignment σon {x1, . . . , xi, xi+1}there exists a unique membrane 0 which contains {(σ(xi+1))i+1}∪{dj|cj∈[ 1≤l≤i−1 (σ(xl))(xl)∧i≥2} ∪ {cj|cj∈\ 1≤l≤i (σ(xl))(xl)∧i≥3}. This membrane 0 inside contains a membrane labeled by qwhich contains the object q2i+2, a membrane labeled by rwhich contains the object r2i+2, and inner membranes jsuch that: •if i≥2 and cj∈\ 1≤l≤i−1 (σ(xl))(xl), then membrane jhas been dissolved, •if i≥2 and cj∈(σ(xi))(xi)−\ 1≤l≤i−1 (σ(xl))(xl), then C2i+1(j) = {cj}; •the remaining membranes are empty. The configuration C2i+2 is obtained from C2i+1 by applying the rules [ p2i+2 → p2i+3]p, [ q2i+2 →q2i+3]q; [r2i+2 →r2i+3]r, [ fi+1 →f(xi+1ai+1]0,[ti+1 → t(xi+1)ai+1]0, where an+1 =λ, and cj[ ]j→[cj]j(1 ≤j≤m). Hence, we have C2i+2(p) = {p2i+3}and C2i+2(s) = C2i+2(s0) = ∅. Moreover, for each truth assignment σon {x1, . . . , xi, xi+1}there exists a unique membrane 0 which contains {(σ(xi+1))(xi+1)}∪{dj|cj∈[ 1≤l≤i (σ(xl))(xl)∧i≥2} ∪ {cj|cj∈\ 1≤l≤i (σ(xl))(xl)∧i≥3} That membrane 0 inside contains a membrane labeled by qwhich contains the object q2i+3, a membrane labeled by rwhich contains the object r2i+3, and empty inner membranes j, where 1 ≤j≤m; if i≥2, then cj/∈\ 1≤l≤i (σ(xl))(xl). ut Lemma 3. The configuration C2n+5 fulfills the following conditions: Polarizationless P Systems with Active Membranes 153 1. C2n+5(p) = {p2n+6},C2n+5(s) = ∅, and the content of C2n+5(s0)is {bu 2, ru 2n+5}∪{dj|cj∈[ 1≤l≤n (σ(xl))(xl)∧σ(ϕ) = 0 ∧n≥2} ∪ {cj|cj∈\ 1≤l≤n (σ(xl))(xl)∧σ(ϕ) = 0 ∧n≥3}, where uis the number of truth assignment σsuch that σ(ϕ) = 0. 2. For each assignment σwhich satisfies the formula ϕthere exists a unique membrane 0 whose contents is {r2n+5}∪{dj|cj∈[ 1≤l≤n (σ(xl))(xl)∧n≥2} ∪ {cj|cj∈\ 1≤l≤n (σ(xl))(xl)∧n≥3}. Corollary 1. The formula ϕis satisfiable if and only if in the configuration C2n+5 there is at least a membrane labeled by 0 that has not been dissolved. Proof. Indeed, a truth assignment σis a satisfying assignment if and only if in the configuration C2n+4 the object b1from the membrane 0 associated with the assignment σhas not entered any membrane j(1 ≤j≤m), because all such membranes have been dissolved in previous steps. But this condition is equivalent to the existence of some membrane labeled by 0 in the configuration C2n+5.ut Corollary 2. Let ube the number of truth assignments σsuch that σ(ϕ) = 0, and let Cbe a computation of Π(ϕ). 1. If the formula ϕis satisfiable, then C2n+8(p) = ∅, the contents of C2n+8(s)is {bu 2, ru 2n+5, yn−u−1, p2n+7}∪{dj|cj∈[ 1≤l≤n (σ(xl))(xl)∧σ(ϕ) = 0 ∧n≥2} ∪ {cj|cj∈\ 1≤l≤n (σ(xl))(xl)∧σ(ϕ) = 0 ∧n≥3}, C2n+8(env) = yes, and the system halts giving an affirmative answer. 2. If the formula ϕis not satisfiable, then C2n+8(p) = ∅, the contents of C2n+8(s0) is {bu 2, ru 2n+5, yn−u}∪{dj|cj∈[ 1≤l≤n (σ(xl))(xl)∧σ(ϕ) = 0 ∧n≥2} ∪ {cj|cj∈\ 1≤l≤n (σ(xl))(xl)∧σ(ϕ) = 0 ∧n≥3}, C2n+8(s) = {no},C2n+9(p) = ∅,C2n+9(s) = ∅,C2n+9(env) = no, and the system halts giving a negative answer. 154 R. Freund, Gh. P˘aun, M.J. P´erez-Jim´enez 6 Final Remarks We have shown that P systems with polarizationless active membranes are computationally complete, even when working in the minimally parallel mode with very restricted forms of the rules, i.e., only evolving one object in or through a membrane (one-normal form). Moreover, we have also shown that SAT can be solved by P systems with polarizationless active membranes even when working in the minimally parallel mode, but in this case the question whether we can restrict the rules to the one-normal form remains as an open problem. Acknowledgements The work of Gh. P˘aun was partially supported by Project BioMAT 2-CEx06- 11-97/19.09.06. The work of M.J. P´erez-Jim´enez was supported by the project TIN2005-09345-C04-01 of the Ministerio de Educaci´on y Ciencia of Spain, co– financed by FEDER funds, and of the project of Excellence TIC 581 of the Junta de Andaluc´ıa. References 1. A. Alhazov: P systems without multiplicities of symbol-objects. Information Processing Letters, 100 (2006), 124–129. 2. A. Alhazov, M.J. P´erez-Jim´enez: Uniform solution to QSAT using polarizationless active membranes, Vol. I of Proc. of the Fourth Brainstorming Week on Membrane Computing, Sevilla (Spain), Jan 30 - Feb 3, 2006, 29–40. 3. A. Alhazov, R. Freund, On efficiency of P systems with active membranes and two polarizations. In [7], 81–94. 4. A. Alhazov, R. Freund, Gh. P˘aun: Computational completeness of P systems with active membranes and two polarizations. In Machines, Computations, and Universality. 4th Intern. Conf. Sankt Petersburg, Russia, 2004, LNCS 3354 (M. Margenstern, ed.), Springer, 2005, 82–92. 5. G. Ciobanu, L. Pan, Gh. P˘aun, M.J. P´erez-Jim´enez: P systems with minimal parallelism. Theoretical Computer Sci., to appear. 6. J.E. Hopcroft, J.D. Ullman: Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading, MA, 1979. 7. G. Mauri, Gh. P˘aun, M.J. P´erez-Jim´enez, G. Rozenberg, A. Salomaa, eds.: Membrane Computing, International Workshop, WMC5, Milano, Italy, 2004, Selected Papers. Lecture Notes in Computer Science 3365, Springer-Verlag, Berlin, 2005. 8. M. Minsky: Computation – Finite and Infinite Machines. Prentice Hall, Englewood Cliffs, NJ, 1967. 9. Gh. P˘aun: Computing with membranes. Journal of Computer and System Sciences, 61 (2000), 108–143. 10. Gh. P˘aun: P systems with active membranes: Attacking NP-complete problems. Journal of Automata, Languages and Combinatorics, 6, 1 (2001), 75–90. 11. Gh. P˘aun: Membrane Computing. An Introduction. Springer-Verlag, Berlin, 2002. Polarizationless P Systems with Active Membranes 155 12. Gh. P˘aun, A. Riscos-N´u˜nez, A. Romero-Jim´enez, F. Sancho-Caparrini, eds.: Proceedings of the Second Brainstorming Week on Membrane Computing, Sevilla, February 2004. Technical Report 01/04 of Research Group on Natural Computing, Sevilla University, Spain, 2004. 13. M.J. P´erez-Jim´enez, A. Romero-Jim´enez, F. Sancho-Caparrini: Teoria de la complejidad en modelos de computacion celular con membranas. Kronos Editorial, Sevilla, 2002.