Uniform Solution to QSAT Using Polarizationless Active Membranes

Uniform Solution to QSAT Using Polarizationless Active Membranes Artiom Alhazov1,2, Mario J. P´erez-Jim´enez3 1Research Group on Mathematical Linguistics Rovira i Virgili University Pl. Imperial Tarraco 1, 43005 Tarragona, Spain [email protected] 2Institute of Mathematics and Computer Science Academy of Sciences of Moldova Str. Academiei 5, Chi¸sin˘au, MD 2028, Moldova [email protected] 3Research Group on Natural Computing Department of Computer Science and Artificial Intelligence University of Sevilla Avda. Reina Mercedes s/n, 41012 Sevilla, Spain [email protected] Summary. It is known that the satisfiability problem (SAT) can be solved a semiuniform family of deterministic polarizationless P systems with active membranes with non–elementary membrane division. We present a double improvement of this result by showing that the satisfiability of a quantified boolean formula (QSAT) can be solved by a uniform family of P systems of the same kind. 1 Introduction A particularly interesting class of membrane systems (P systems) are the systems with active membranes and with three electrical charges (see [8]), where membrane division can be used in order to solve computationally hard problems in polynomial or even linear time, by a space–time trade-off. The first efficient semi–uniform solution to SAT (satisfiability problem) was given by Gh. P˘aun in [8], using division for non–elementary membranes. This result was improved by Gh. P˘aun, Y. Suzuki, H. Tanaka, and T. Yokomori in [9] using only division for elementary membranes (in that paper also a semi–uniform solution to HPP (hamiltonian path problem) using membrane creation is presented). P. Sosik in [16] provides an efficient semi–uniform solution to QSAT (quantified satisfiability problem), a well known PSPACE–complete problem, in the framework of P systems with active membranes but using cell division rules for 30 A. Alhazov, M.J. P´erez-Jim´enez non–elementary membranes. A uniform solution for QSAT was presented in [3], while a semi–uniform polarizationless solution for SAT was presented in [1]. Different efficient uniform solutions have been obtained in the framework of recognizer P systems with active membranes, with polarizations and only using division rules for elementary membranes ([12], [11], [4], [14], [2], [13], and [15]). Nevertheless, the polynomial complexity class associated with recognizer P systems with active membranes and with polarizations does not seem precise enough to describe classical complexity classes below PSPACE. Therefore, it is challenging to investigate weaker variants of cell–like membrane systems able to characterize classical complexity classes. In this paper we work with a variant of these membrane systems that does not use polarizations, and where dissolution rules provide a borderline between efficiency and non–efficiency as shown in [5]. The paper is organized as follows. In the next section some preliminary ideas about recognizer membrane systems and polynomial complexity classes are introduced. In Section 3 we present a uniform and polynomial solution of the quantified satisfiability problem by a family of recognizer P systems with active membranes, without polarization, permitting dissolution rules and division for elementary and non–elementary membranes. Conclusions and some final remarks are given in Section 4. 2 Preliminaries We start by defining what means to solve decision problems by recognizer P systems, in a semi–uniform or uniform way. In order to solve NP–complete problems in polynomial (even linear) time in the framework of P systems without input membrane, we need to design one system for each instance of the problem. Definition 1. Let X= (IX, θX)be a decision problem. We say that Xis solvable in polynomial time by a (countable) family of recognizer membrane systems without input Π= (Π(u))u∈IX, and we denote it by X∈PMC∗ R, if the following is true: •The family Πis polynomially uniform by Turing machines; that is, there exists a deterministic Turing machine working in polynomial time which constructs the system Π(u)from the instance u∈IX. •The family Πis polynomially bounded; that is, there exists a polynomial function p(n)such that for each u∈IX, all computations of Π(u)halt in, at most, p(|u|)steps. •The family Πis sound with regard to X; that is, for each instance of the problem u∈IXsuch that there exists an accepting computation of Π(u), we have θX(u) = 1. •The family Πis complete with regard to X; that is, for each instance of the problem u∈IXsuch that θX(u) = 1 every computation of Π(u)is an accepting computation. Uniform Solution to QSAT 31 We say that the family Πis a semi–uniform solution of the problem X. As a direct consequence of working with recognizer membrane systems (all of its computations halt) is that the complexity classes PMC∗ Rare closed under complement. Moreover, these complexity classes are closed under polynomial time reduction, in the classical sense (see [10]). Now, we deal with recognizer membrane systems with input membrane solving decision problems in a uniform way in the following sense: all instances of a decision problem with the same size (according to a previously fixed polynomial time computable criterion) are processed by the same system, on which an appropriate input, representing the specific instance, is supplied. Definition 2. AP system with input membrane is a tuple (Π, Σ, iΠ), where: (a) Πis a P system with working alphabet Γ, with pmembranes labeled with 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. If mis a multiset over the input alphabet Σ, then the initial configuration of the P system (Π, Σ, iΠ)with input mis (µ, M1, . . . , MiΠ∪m, . . . , Mp). Next, we define the concept of polynomial solvability of decision problems by families of recognizer P systems constructed in polynomial time by Turing machines. Definition 3. Let X= (IX, θX)be a decision problem. We say that Xis solvable in polynomial time by a family of recognizer membrane systems with input membrane Π= (Π(n))n∈N, and we denote it by X∈PMCR, if the following is true: •The family Πis polynomially uniform by Turing machines; that is, there exists a deterministic Turing machine that constructs in polynomial time the system Π(n)from n∈N. •There exists a pair (cod, s)of polynomial-time computable functions whose domain is L, such that for each u∈L,s(u)is a natural number and cod(u)is an input multiset of the system Π(s(u)), verifying the following:. – The family Πis polynomially bounded with regard to (X, cod, s); that is, there exists a polynomial function p(n)such that for each u∈IXevery computation of the system Π(s(u)) with input cod(u)is halting and, moreover, it performs at most p(|u|)steps. – The family Πis sound with regard to (X, cod, s); that is, for each instance of the problem u∈IXsuch that there exists an accepting computation of Π(s(u)) with input cod(u), we have θX(u) = 1. – The family Πis complete with regard to (X, cod, s); that is, for each instance of the problem u∈IXsuch that θX(u) = 1, every computation of Π(s(u)) with input cod(u)is an accepting one. 32 A. Alhazov, M.J. P´erez-Jim´enez We say that the family Πis a uniform solution to the problem X. The complexity classes PMCRare closed under complement and under polynomial time reduction, in the classical sense (see [10]). Let us note that if Πis a family of recognizer P systems solving a decision problem Xin polynomial time and in a uniform way, then it provides a polynomial time solution of Xin a semi–uniform way. That is, we have PMCR⊆PMC∗ R. 2.1 P systems with polarizationless active membranes Definition 4. A P system with active membranes and without polarizations is a P system with Γas working alphabet, with Has the finite set of labels for membranes, and where the rules are of the following forms: (a0) [ a→u]hfor h∈H,a∈Γ,u∈Γ∗. These are object evolution rules. An object a∈Γbelonging to a membrane labeled by hevolves to a string u∈Γ∗. (b0)a[ ]h→[b]hfor h∈H,a, b ∈Γ. These are send–in communication rules. An object from the region immediately outside a membrane labeled by his introduced in this membrane, possibly transformed into another object. (c0) [ a]h→b[ ]hfor h∈H,a, b ∈Γ. These are send–out communication rules. An object is sent out from membrane labeled by hto the region immediately outside, possibly transformed into another object. (d0) [ a]h→bfor h∈H,a, b ∈Γ. These are dissolution rules. A membrane labeled by his dissolved in reaction with an object. The skin is never dissolved. (e0) [ a]h→[b]h[c]hfor h∈H,a, b, c ∈Γ. These are division rules for elementary membranes. An elementary membrane can be divided into two membranes with the same label, possibly transforming some objects. (f0) [ [ ]h1[ ]h2]h0→[ [ ]h1]h0[ [ ]h2]h0, where h0, h1, h2are labels. These are division rules for non–elementary membranes. If the membrane with label h0 contains other membranes than those with labels h1, h2, these membranes and their contents are duplicated and placed in both new copies of the membrane h0; all membranes and objects placed inside membranes h1,h2, as well as the objects from membrane h0placed outside membranes h1and h2, are reproduced in the new copies of membrane h0. These rules are applied according to the following principles: •All the rules 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 at the same time a membrane labeled with his divided by a rule of type (e0) or (f0) and there are objects in this membrane which evolve by means of rules of type (a0), then we suppose that first the evolution rules of type (a0) are used, and then the division is produced. Of course, this process takes only one step. Uniform Solution to QSAT 33 •The rules associated with membranes labeled with hare used for all copies of this membrane. At one step, a membrane can be the subject of only one rule of types (b0)–(f0). We denote by AM0(α, β), where α∈ {−d, +d}and β∈ {−ne, +ne}, the class of all recognizer P systems with polarizationless active membranes such that: •if α= +dthen dissolution rules are permitted; •if α=−dthen dissolution rules are forbidden; •if β= +ne then division rules for elementary and non–elementary membranes are permitted; •if β=−ne then only division rules for elementary membranes are permitted. Proposition 1. For each α∈ {−d, +d}and β∈ {−ne, +ne}we have: (1) PMCAM0(α,β)⊆PMC∗ AM0(α,β). (2) PMCAM0(α,−ne)⊆PMCAM0(α,+ne). (3) PMC∗ AM0(α,−ne)⊆PMC∗ AM0(α,+ne). (4) PMCAM0(−d,β)⊆PMCAM0(+d,β). (5) PMC∗ AM0(−d,β)⊆PMC∗ AM0(+d,β). A conjecture known in the membrane computing area under the name of the P– conjecture (proposed by Gh. P˘aun in 2005) affirms that P=PMCAM0(+d,−ne). It has been obtained some partial answers of that conjecture ([5]). Specifically, in the framework of recognizer P systems with membrane division but without using polarizations it was shown a surprising role of the dissolution rules, as it makes the difference between efficiency and non–efficiency for P systems with membrane division and without polarization. Theorem 1. We have the following: (1) P=PMCAM0(−d,β)=PMC∗ AM0(−d,β), for each β∈ {−ne, +ne}. (2) NP ⊆PMC∗ AM0(+d,+ne). 3 A Uniform Solution to QSAT In this section we extend the result (2) from Theorem 1, providing an uniform and linear time solution to QSAT (quantified satisfiability) problem, through a family of recognizer P systems using polarizationless active membranes, dissolution rules, and division for elementary and non–elementary membranes. Given a boolean formula ϕ(x1, . . . , xn) in the 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. 34 A. Alhazov, M.J. P´erez-Jim´enez 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 [7]. Theorem 2. QSAT belongs to the class PMCAM0(+d,+ne). Proof. The solution proposed follows a brute force approach, in the framework of recognizer P systems with polarizationless active membranes where dissolution rules, and division for elementary and non–elementary membranes are permitted. The solution consists in the following stages: •Generation Stage: using membrane division for elementary and non–elementary membranes, all truth assignments for the variables associated with the boolean formula are produced. •Assignments stage: in a special membrane we encode the clauses that are satisfied for each truth assignments. •Checking Stage: we determine what truth assignments make true the boolean formula. •Quantifier Stage: the universal and existential gates of the fully quantified formula are simulated and its satisfiability is encoded by a special object in a suitable membrane. •Output Stage: The systems sends out to the environment the right answer according to the result of the previous stage. Let us consider a propositional formula in the conjunctive normal form: ϕ=C1∨ · · · ∨ Cm, Var(ϕ) = {x1, . . . , xn} Ci=yi,1∧ · · · ∧ yi,li,1≤i≤m, where yi,k ∈ {xj,¬xj|1≤j≤n},1≤i≤m, 1≤k≤li. We consider a normal form for QSAT: the number of variables is even (n= 2n0) and the quantified formula is ϕ∗=∃x1∀x2· · · ∃xn−1∀xnϕ(x1, . . . , xn). Let us consider the pair function from N2onto Ndefined by hn, mi= ((n+m)(n+m+ 1)/2) + n. This function is polynomial time computable and bijective. Uniform Solution to QSAT 35 Depending on numbers m(of clauses) and n(of variables), we will consider a system (Π(hn, mi), Σ(hn, mi), i0), where i0= 0 is the input region and Σ(hn, mi) = {vi,j, v0 i,j |1≤i≤m, 1≤j≤n}is the input alphabet. The problem instance will be encoded in the rules of the P system by multisets Xand X0of symbols from Σ, corresponding to the clause-variable pairs such that the clause is satisfied by true and false assignment of the variable: X={(vi,j,1) |xj∈ {yi,k |1≤k≤li},1≤i≤m, 1≤j≤n}, X0={(v0 i,j,1) | ¬xj∈ {yi,k |1≤k≤li},1≤i≤m, 1≤j≤n}. We now construct the P system Π(hn, mi) = (O, H, µ, w0,· · · , wm+5n+3, R),with O=Σ(hn, mi)∪ {ui,j, u0 i,j |1≤i≤m, 1≤j≤n} ∪ {di|0≤i≤2m+ 7n+ 2}∪{ai, ti, fi|1≤i≤n} ∪ {ci|1≤i≤m}∪{t, f, z, z0, T, T0,yes,no}, µ= [ [ · · · [ [ ]0]1· · · ]m+5n+2]m+5n+3, w0=wm+5n+1 =d0, wm+2n+3i=dm+5n−2,1≤i≤n, wi=λ, i /∈ {0, m + 5n+ 1} ∪ {m+ 2n+ 3i|1≤i≤n}, H={0,· · · , m + 5n+ 3}, and the following rules (we also explain their use): Generation stage G1 [ d3i→ai+1d3i+1]0, [ d3i+1 →d3i+2]0, [ d3i+2 →d3i+3]0, 0 ≤i < n. [d3n+i→d3n+i+1]0, 0 ≤i < m + 2n. We count to m+5n, which is the time needed for producing all 2ntruth assignments for the nvariables, as well as membrane sub-structures which will examine the truth value of formula ϕfor each of these truth assignments; this counting is done in the central membrane; moreover during steps 3i, 0 ≤i≤n, symbols a1,· · · , an are subsequently produced. G2 [ ai]0→[ti]0[fi]0, 1 ≤i≤n. In membrane 0, we subsequently choose each variable xi, 1 ≤i≤n, and both values true and false are associated with it, in form of objects tiand fi, which are separated in two membranes with label 0. The division of membrane 0 is triggered by the objects ai, which are introduced by the first rule from group G1 in odd steps; this is important in interleaving the use of these rules (hence the division of membrane 0) with the use of the rules of group G4, for dividing membranes placed above membrane 0. 36 A. Alhazov, M.J. P´erez-Jim´enez label s ~~~ ~ tage m+5n+3 Oo m+5n+2 Oo m+5n+1 Oo eeeeeeeeeeeeee Y Y Y Y Y Y Y Y Y Y Y Y Y Y m+5n−1Qo o m+5n−2Qo kkkkkkkS S S S S S So kkkkkkkS S S S S S S m+5n−4Qo o o o m+5n−5Qo o o o m+2n+2 Qo o o o o o o o m+2n+1 Qo ¢ ¢G G Go w w wG G Go w w wG G Go w w wG G Go w w wG G Go w w wG G Go w w wG G Go w w w= = m+2nAo o o o o o o o o o o o o o o o m+2n−1Ao o o 2n+ 1 Ao o o 2nCo o o 2Co o o 1Co o o 0Go o o Fig. 1. The membrane structure of the system Πafter m+ 5nsteps. G3 [ dj→dj−1]m+2n+3i, 1 ≤j≤m+ 5n−2, 1 ≤i < j, [d0]m+2n+3i→z0, 1 ≤i≤n. After m+ 5n−2 steps, dissolution rules are applied to membranes m+ 2n+ 3i. G4 [ [ ]i[ ]i]i+1 →[[]i]i+1[ [ ]i]i+1, 0 ≤i < m + 5n. These are division rules for membranes with label 0,1,· · · , m + 5n, to be used for the central membrane 0 in steps which follow the use of the first rule of type G1. The division of a membrane with label 1 is then propagated from lower levels to upper levels of the membrane structure and the membranes are continuously divided. The membrane division stops at the level where a membrane m+ 2n+ 3i has been already dissolved by a rule from group G3. This results in the structure as shown in Figure 1 after m+ 5nsteps. G5 [ dm+5n]0→T. After m+ 5nsteps, each copy of membrane with label 0 is dissolved and the contents is released into the surrounding membrane, which is labeled with 1. Assignments stage A1 [ ti→t0]2i−1, [t0]2i−1→z, [fi]2i−1→f0, Uniform Solution to QSAT 37 [f0→z]2i, [z]2i→z0, 1 ≤i≤n. Depending on the variable assignments, we need to determine what clauses are satisfied. For a variable xi, this is done in membranes 2i−1 and 2i. The objects encoding the problem propagate through the membrane structure: object tidissolves membrane 2i−1 after one step, and then it dissolves membrane 2i immediately, while object fidissolves membrane 2i−1 immediately, and then it dissolves membrane 2iafter one step. A2 [ vi,j →ui,j ]2i−1, [v0 i,j →u0 i,j]2i−1. Once in membrane 2i−1, objects vi,j and v0 i,j wait for one step. A3 [ u0 i,j →λ]2i−1, [ui,j →ci]2i−1, [ui,j →λ]2i, [u0 i,j →ci]2i, 1 ≤i≤n. If membrane 2i−1 is not dissolved in the meantime, then the objects encoding the instance of SAT evolve according to the value true of xi, otherwise, they evolve according to the value false of xi. At the end of this routine (it takes 3nsteps), a membrane with label 2n+ 1 which contains all the symbols c1,· · · , cmcorresponds to the truth assignment satisfying all clauses, hence it satisfies formula ϕ, and vice-versa. Checking stage C1 [ ci]2n+i→ci, 1 ≤i≤m. A membrane with label 2n+i, 1 ≤i≤m, is dissolved if and only if cjappears in it (i.e., clause Cjis satisfied by the current truth assignment); if this is the case, the truth assignment associated with the membrane is released in the surrounding membrane. Otherwise, the truth assignment remains blocked in membrane 2n+i and never used at the next steps by the membranes placed above. C2 [ T]m+2n+1 →T. The fact that the object Tappears in the membrane with the label m+ 2n+ 1 means that there is a truth assignment which satisfies the formula ϕ. In this case, the membrane with label m+2n+1 is dissolved and the contents are released into the membrane with label m+2n+2. Otherwise, the formula is not satisfiable, and the membrane with label m+ 2n+ 1 will not dissolve. Quantifier stage Q1 [ T]m+2n+6i+1 →T0, [T]m+2n+6i+2 →T, [T0→λ]m+2n+6i+2, 1 ≤2i≤m.