The Unique Satisfiability Problem from a Membrane Computing Perspective

ROMANIAN JOURNAL OF INFORMATION SCIENCE AND TECHNOLOGY Volume 21, Number 3, 2018, 288–297 The Unique Satisfiability Problem from a Membrane Computing Perspective David ORELLANA-MART´ IN1, Luis VALENCIA-CABRERA1, Agust´ ın RISCOS-N ´ U˜ NEZ1, and Mario J. P ´ EREZ-JIM ´ ENEZ1 1Research Group on Natural Computing Dept. of Computer Science and Artificial Intelligence Universidad de Sevilla, Av. Reina Mercedes s/n, 41012, Sevilla, Spain E-mail: {dorellana, lvalencia, ariscosn, marper}@us.es Abstract. Complexity class DP is the class of “differences” of any two languages in NP. It verifies that NP ∪co-NP ⊆DP ⊆PNP, where PNP is the second level of the polynomial hierarchy, specifically, it is the class of languages decidable by a deterministic polynomial-time Turing machine having access to an NP oracle. The unique sastifiability problem (UNIQUE SAT) is a well known DP problem which has been proved to be co-NP- hard. In this paper, a uniform and polynomial time solution for the UNIQUE SAT problem is given by a family of polarizationless P systems with active membranes and division rules only for elementary membranes, without dissolution rules but using minimal cooperation and minimal production in object evolution rules. Key-words: Complexity class DP; polarizationless P systems with active membranes; cooperative rules; UNIQUE SAT problem. 1. Preliminaries An alphabet Γis a non-empty set and their elements are called symbols. A string uover Γis an ordered finite sequence of symbols, that is, a mapping from a natural number n∈Nonto Γ. The number nis called the length of the string uand it is denoted by |u|. The empty string (with length 0) is denoted by λ. The set of all strings over an alphabet Γis denoted by Γ∗. A language over Γis a subset of Γ∗. Amultiset over an alphabet Γis an ordered pair (Γ, f)where fis a mapping from Γonto the set of natural numbers N. The support of a multiset m= (Γ, f)is defined as supp(m) = {x∈ Γ|f(x)>0}. A multiset is finite (respectively, empty) if its support is a finite (respectively, The Unique Satisfiability Problem 289 empty) set. We denote by ∅the empty multiset. Let m1= (Γ, f1),m2= (Γ, f2)be multisets over Γ, then the union of m1and m2, denoted by m1+m2, is the multiset (Γ, g), where g(x) = f1(x) + f2(x)for each x∈Γ. 1.1. Decision problems and languages Roughly speaking, a decision problem Xis one whose solution/answer is either “yes” or “no”. This can be formally defined by an ordered pair (IX, θX), where IXis a language over a finite alphabet ΣXand θXis a total Boolean function over IX. The elements of IXare called instances of the problem X. Each decision problem Xhas associated a language LXover the alphabet ΣXas follows: LX={u∈ΣX|θX(u) = 1}, that is, LXis the set of inputs for which the answer is affirmative. Conversely, every language Lover an alphabet Σhas associated a decision problem XL= (IXL, θXL)as follows: IXL= Σ∗and θXL(u)=1if and only if u∈L. Then, given a decision problem Xwe have XLX=X, and given a language Lover an alphabet Σwe have LXL=L. The complement problem Xof a decision problem X= (IX, θX)is the decision problem (IX,¬θX), that is for each instance the answer of Xis “yes” if and only if the answer of Xis “no”. 1.2. The Cantor pairing function The Cantor pairing function encode pairs of natural numbers by single natural numbers and it is defined as follows: for each n, p ∈N hn, pi=(n+p)(n+p+ 1) 2+n The Cantor pairing function is a primitive recursive bijective function from N×Nonto N. Then, for each t∈Nthere exist unique natural numbers n, p ∈Nsuch that t=hn, pi. 2. Minimal cooperation and minimal production in polarizationless P system with active membranes Membrane Computing is an emergent branch of Natural Computing providing distributed parallel non deterministic computing models whose computational devices are called membrane systems, containing processing units called compartments. This computing paradigm is inspired by some basic biological features, by the structure and functioning of the living cells, as well as from the cooperation of cells in tissues, organs, and organisms. There exist basically two ways to consider computational devices: cell-like membrane systems and tissue-like membrane systems. The first one, using the biological membranes arranged hierarchically, inspired from the structure of the cell, and the second one using the biological membranes placed in the nodes of a graph, inspired from the cell inter-communication in tissues. We refer the interested reader to [9,11] for more details of these models. P systems with active membranes were first introduced by Gh. P˘ aun [10], introducing electrical charges (polarizations) associated to membranes, but the rules are non-cooperative and there are no priorities. Nevertheless, the class of all problems solvable in a uniform way in polynomial 290 D. Orellana et al. time by means of families of P systems with active membranes which use division for elementary and non-elementary membranes coincides with PSPACE [13]. Consequently, the usual framework of P systems with active membranes for solving decision problems is too powerful from the computational complexity point of view. Polarizationless P systems with active membranes were initially studied in [1, 2]. However, this initial approach proposed to replace polarizations by a somehow equivalent or even more powerful ingredient: the ability to change the label of the membranes. Throughout this paper, P systems with active membranes but no electrical charges nor membrane relabelling are considered. When dissolution rules are forbidden in this framework, only problems in class Pcan be solved in an efficient way [5]. In order to get the presumable efficiency (ability to solve NP-complete problems in a uniform way in polynomial time) of these systems, minimal cooperation and minimal production in object evolution rules are allowed. Definition 1. A polarizationless P system with active membranes, without dissolution, with division rules for elementary membranes and making use of minimal cooperation and minimal production in object evolution rules of degree q≥1, is a tuple Π = (Γ, H, µ, M1,...,Mq,R, iout), where: •Γis a finite alphabet whose elements are called objects. •His a finite alphabet such that H∩Γ = ∅whose elements are called labels. •µis a labelled rooted tree (called membrane structure)consisting of qnodes injectively labelled by elements of H(the root of µis labelled by rµ). • M1,...,Mqare multisets over Γ. • R is a finite set of rules, of the following forms: ?[a→c]hor [a b →c]h, where h∈H,a, b, c ∈Γ(object evolution rules). ? a [ ]h→[b]h, where h∈H\ {rµ},a, b ∈Γ(send–in communication rules). ?[a]h→b[ ]h, where h∈H,a, b ∈Γ(send–out communication rules). ?[a]h→[b]h[c]h, where h∈H\ {iout, rµ},a, b, c ∈Γand his the label of an elementary membrane µ(division rules for elementary membranes). –iout ∈H∪ {env}, where env is the label of the environment (if iout ∈Hthen iout is the label of a leaf of µ). The semantics of this kind of P systems follows the usual principles of P systems with active membranes [10]. We denote by DAM0(mcmp, +c, −d, −n)the class of all recognizer polarizationless P system with active membranes, without dissolution, with division rules for elementary membranes and which makes use of minimal cooperation and minimal production in objects evolution rules, Recognizer membrane systems were introduced in [12] and they provide a natural framework to solve decision problems. This kind of systems are characterized by the following features: – the working alphabet Γhas two distinguished objects yes and no; The Unique Satisfiability Problem 291 – there exists an input alphabet Σstrictly contained in Γ; – there exists an input compartment labelled by iin ∈H; –iout =env, that is, the output “zone” is the enviroment; – the initial contents of the compartments are multisets over Γ\Σ; – for each multiset mover Σthe initial configuration of Πwith input multiset mis M1,...,Miin + m, . . . , Mq, that is, the input multiset mis added to the contents of the input compartment; – all computations of the system Π + mhalt, where Π + mdenotes the membrane system Πwith input multiset m; and – for each computation of Π + m, either object yes or object no (but not both) must have been released into the environment, and only at the last step of the computation. 3. The complexity class DP The class DP was introduced by C.H. Papadimitriou and M. Yannakis in 1982 [6], as the class of “differences” of any two decision problems in NP. Roughly speaking, class DP tries to capture the complexity of problems that most likely can not be decided by any non-deterministic Turing machine working in polynomial time. Formally, a language Lis in the class DP if and only if there are two languages L1and L2 such that L1, L2∈NP and L=L1\L2. Equivalently, a language Lis in the class DP if and only if there are two languages L1and L2such that L1∈NP,L2∈co-NP, and L=L1∩L2. It is easy to proof that NP ∪co-NP ⊆DP. The class DP can defined in terms of decision problems as follows: a decision problem Xis in class DP if and only if there are two decision problems X1= (IX1, θX1)and X2= (IX2, θX2)such that X1∈NP,X2∈co-NP, and LX=LX1∩LX2. UNIQUE SAT is the problem of deciding whether a Boolean formula given in conjunctive normal form has exactly one satisfying truth assignment. This problem is in class DP because UNIQUE SAT=SAT ∩X, being Xthe co-NP problem of deciding whether a Boolean formula given in conjunctive normal form has not two different satisfying truth assignment. UNIQUE SAT is a co-NP hard problem [3]. Indeed, let us recall that UNSAT is the problem of deciding whether a given a Boolean formula in conjunctive normal form is unsatisfiable. It is well known that UNSAT is a co-NP-complete problem. The function ffrom the set of instances of UNSAT to the set of instances of UNSAT defined by f(ϕ(x1, . . . , xn)) = [ϕ(x1, . . . , xn)∧z]∨[(¬z)∧x1∧ · · · ∧ xn] being za propositional variable not in the set {x1, . . . , xn}, is a polynomial-time reduction from UNSAT to UNIQUE SAT. Then, UNIQUE SAT is a co-NP hard problem but it is unknown what is its precise complexity. However, UNIQUE SAT is a DP-complete problem under randomized polynomial-time reductions (see [16] for details). 292 D. Orellana et al. 4. A solution to UNIQUE-SAT by membrane systems In this section a uniform polynomial-time solution to the UNIQUE SAT problem is provided by means of a family of recognizer polarizationless P systems with active membranes, without dissolution rules, with minimal cooperation and minimal production in objects evolution rules which use only division for elementary membranes, that is, by a family of systems DAM0(mcmp, +c, −d, −n). For that purpose, the solution to the SAT problem given in [14] and to the #SAT given in [15] are adapted, basically, in what concerns to the output stage. The family Π={Π(t)|t∈N}is defined in such a manner that a system Π(t)will process any Boolean formula ϕin conjunctive normal form (CNF) with nvariables and pclauses (so that t=hn, pi) provided that the appropriate input multiset cod(ϕ)is supplied to the system (through the corresponding input membrane). Then, system Π(t)will answer how many truth assignments make true the input formula ϕ. Thus, for each n, p ∈N, we consider the recognizer P system Π(hn, pi) = (Γ,Σ, H, µ, M1,M2,R, iin) from DAM0(mcmp, +c, −d, −n), defined as follows: – Working alphabet Γ = Σ ∪ {β , \ , yes ,yes0,no , γ0}∪{αi|0≤i≤n+ 2p+ 1} ∪ {δi|0≤i≤n+ 2p+ 3}∪{ai,j |0≤i≤n−1,0≤j≤i} ∪ {bi,k |1≤i≤n, 1≤k≤i}∪{cj|1≤j≤p}∪{dj|2≤j≤p} ∪ {ti,k, fi,k |1≤i≤n, i ≤k≤n+p−1} ∪ {Ti,k, Fi,k |1≤i≤n, 0≤k≤n−1}∪{Ti, Fi|1≤i≤n} ∪ {xi,j,k, xi,j,k, x∗ i,j,k |1≤i≤n, 1≤j≤p, 0≤k≤n+p}. – Input alphabet Σ = {xi,j,0, xi,j,0, x∗ i,j,0|1≤i≤n, 1≤j≤p}. –H={1,2}. – Membrane structure: µ= [ [ ]2]1, that is, µ= (V, E)where V={1,2}and E= {(1,2)}. – Initial multisets: M1={α0, δ0},M2={β, bi,1, Tp i,0, Fp i,0|1≤i≤n}. – The set of rules Rconsists of the following rules: R.1 Rules for a general counter. [αk−→ αk+1 ]1for 0≤k≤n+ 2p [δk−→ δk+1 ]1for 0≤k≤n+ 2p+ 2 R.2 Rules to generate all truth assignments. [bi,i ]2−→ [ti,i ]2[fi,i ]2,for 1≤i≤n [bi,k −→ bi,k+1 ]2,for 2≤i≤n, 1≤k≤i−1 The Unique Satisfiability Problem 293 R.3 Rules to generate suitable objects in order to start the next stage. [ti,k −→ ti,k+1 ]2 [fi,k −→ fi,k+1 ]21≤i≤n−1, i ≤k≤n−1 [Ti,k −→ Ti,k+1 ]2 [Fi,k −→ Fi,k+1 ]21≤i≤n, 0≤k≤n−2 [Ti,n−1−→ Ti]2 [Fi,n−1−→ Fi]21≤i≤n R.4 Rules to produce exactly pcopies of each truth assignment. [ti,k Fi−→ ti,k+1 ]2 [fi,k Ti−→ fi,k+1 ]21≤i≤n, n ≤k≤n+p−2 [ti,n+p−1Fi−→ \]2 [fi,n+p−1Ti−→ \]21≤i≤n R.5 Rules to prepare the input formula for check clauses: [xi,j,k −→ xi,j,k+1 ]2 [xi,j,k −→ xi,j,k+1 ]2 [x∗ i,j,k −→ x∗ i,j,k+1 ]2        1≤i≤n, 1≤j≤p, 0≤k≤n+p−1 R.6 Rules for the first checking stage. [Tixi,j,n+p−→ cj]2 [Tixi,j,n+p−→ \]2 [Tix∗ i,j,n+p−→ \]2 [Fixi,j,n+p−→ \]2 [Fixi,j,n+p−→ cj]2 [Fix∗ i,j,n+p−→ \]2                1≤i≤n, 1≤j≤p R.7 Rules for the second checking stage. [c1c2−→ d2]2 [djcj+1 −→ dj+1 ]2,for 2≤j≤p−1 R.8 Rules to prepare objects in the skin membrane. [β dp−→ γ0]2 [γ0]2−→ γ0[ ]2,for 0≤i≤n−1 R.9 Rules to produce the output. [αn+2p+1 γ0−→ yes0]1 [yes0γ0−→ no ]1 [δn+2p+3 yes0−→ yes ]1 [αn+2p+1 δn+2p+3 −→ no ]1 [yes ]1−→ yes [ ]1 [no ]1−→ no [ ]1 – The input membrane is the membrane labelled by 2 (iin = 2) and the output region is the environment. 294 D. Orellana et al. 4.1. An overview of the computation It is easy to check that for each pair of natural numbers n, p, the system Π(hn, pi), previously defined, is deterministic. We consider the polynomial encoding (cod, s)from UNIQUE SAT in Πdefined as follows: let ϕbe a Boolean formula in conjunctive normal form. Let V ar(ϕ) = {x1, . . . , xn}be the set of propositional variables and {C1, . . . , Cp}the set of clauses of ϕ. Let us assume that the number of variables and the number of clauses of the input formula ϕ, are greater than or equal to 2. Then, we define s(ϕ) = hn, piand cod(ϕ) = {xi,j,0|xi∈Cj}∪{xi,j,0| ¬xi∈Cj}∪{x∗ i,j,0|xi/∈Cj,¬xi/∈Cj} Notice that we can represent this multiset as a matrix, in such a way that the j-th row (1≤j≤p) encodes the j-th clause Cjof ϕ, and the columns (1≤i≤n) are associated with variables. We denote by codk(ϕ)the multiset cod(ϕ)with the third index of all objects x, x, x∗being k. The Boolean formula ϕwill be processed by the system Π(s(ϕ)) with input multiset cod(ϕ). Next, we informally describe how that system works. The solution proposed consists of the following stages: •Generation stage: by applying division rules from R.2, all truth assignments for the variables {x1, . . . , xn}associated with ϕare produced. This stage takes exactly ncomputation steps and at the i-th step, 1≤i≤n, of this stage, division rule is triggered by an object bi,i over each membrane labelled by 2, producing two new membranes with all its remaining contents replicated in the new membranes labelled by 2. Simultaneously to these divisions, objects ti,k, fi,k, Ti,k, Fi,k (by applying rules from R.3) and objects xi,j,k, xi,j,k, x∗i,j,k (by applying rules from R.5) evolve during this stage in such a manner that at configuration Cnthe following holds: (a) There is a membrane labelled by 1 which contains ncopies of object αn. (b) There are 2nmembranes labelled by 2 such that each of them contains: a copy of object β, the set codn(ϕ), the multiset {Tp i, Fp i|1≤i≤n}; and a different subset {r1,n, . . . , rn,n}, being r∈ {t, f}. •Production of enough copies for each truth assignment: in this stage pcopies (pis the number of clauses of ϕ) of each truth assignment are produced, in order to allow the checking of the literal associated with each variable in each clause. By using minimal cooperation and minimal production (applying rules from R.4), objects ti,k (respectively, objects fi,k) are used to remove all copies of Fi(respectively, Ti). This stage takes exactly psteps, and at configuration Cn+pthe following holds: (a) The root membrane (labelled by 1) contains ncopies of object αn+p. (b) There are 2nmembranes labelled by 2 such that each of them contains: a copy of object β,ncopies of the garbage object \, the set codn+p(ϕ), and a different multiset {Rp 1, . . . , Rp n}, being R∈ {T, F}. •First Checking stage: by applying rules from R.6, we check whether or not each clause of the input formula ϕis satisfied by the truth assignments generated in the previous stage, encoded by each membrane labelled by 2. This stage takes exactly one computation step, and at configuration Cn+p+1: The Unique Satisfiability Problem 295 (a) The root membrane (labelled by 1) contains ncopies of object αn+p+1. (b) There are 2nmembranes labelled by 2 such that each of them contains: a copy of object β, many copies of the garbage object \(which they will not evolve in the rest of the computation), and copies of objects cjwhose presence means that clause Cj is true for the truth assignment encoded by that membrane. •Second Checking stage: by applying rules from R.7, we check whether or not all clauses of the input formula ϕare satisfied by some truth assignment encoded by a membrane labelled by 2. This stage takes exactly p−1steps and at configuration Cn+2pthe following holds: (a) The root membrane (labelled by 1) contains ncopies of object αn+2p. (b) There are 2nmembranes labelled by 2 such that each of them contains: a copy of object β, many copies of the garbage object \(which they will not evolve in the rest of the computation), and copies of objects djand cj, in such manner that the truth assignment encoded by such membrane makes true ϕif and only if contains some object dp. •Output stage. Affirmative answer. If there exists exactly one input assignment that makes true the input formula, at configuration Cn+2p+1 there will be exactly one object γ0at the skin membrane. Then, by applying the first rule from R.9, an object yes0will be produced, while δn+2p+1 evolves into δn+2p+2. In the next step, only object δn+2p+2 can evolve into δn+2p+3, since there are no objects that can interact with object yes0. Finally, rule [δn+2p+3 yes0−→ yes ]1will be fired, and will produce an object yes in the skin membrane, and it will be released to the environment in the last step of the computation. It takes 4 computation steps. Negative answer. There are two possibilities: ?Case 1: No truth assignment exists making the input formula true. In this case, object γ0will not appear in the skin membrane at configuration Cn+2p+1. Then, in the next two steps, object δn+2p+1 will change to δn+2p+2 and δn+2p+3. These two objects will interact by means of the rule [αn+2p+1 δn+2p+3 −→ no ]1, and object no just created will be sent out to the environment and the system will halt, taking 4 steps of computation. ?Case 2: More than one truth assignment make this formula true. In this case, more than one object γ0will appear in the membrane labelled by 1 at configuration Cn+2p+1. As in the affirmative answer case, objects αn+2p+1 and γ0, selected non-deterministically from the existent ones, will create an object yes0. Besides this, object δn+2p+1 evolves into δn+2p+2. But in the next step, by the presence of another object γ0, rule [yes0γ0−→ no ]1will be fired, and will produce an object no. This object will not interact with the recently evolved object δn+2p+3, that will be released into the environment in the last step on the computation, and then the system halts. This case takes 3 steps. 296 D. Orellana et al. 5. Main result In this section, the most important result of this work is presented; that is: the family of polarizationless P systems from DAM0(mcmp, +c, −d, −n), designed in the previous section, solves the UNIQUE SAT problem in a uniform way in polynomial time. Theorem 1. UNIQUE SAT ∈PMCDAM0(mcmp,+c,−d,−n). Proof. The family Π={Π(t)|t∈N}defined in the previous section verifies the following: (a) Every system Π(t)of the family Πbelongs to DAM0(mcmp, +c, −d, −n). (b) The family Πis polynomially uniform by Turing machines because for each n, p ∈N, the amount of resources needed to build the system Π(hn, pi)is of a polynomial order in n and p. Indeed, – The size of the alphabet is of the order O(n2·p2). – The initial number of membranes is 2∈Θ(1). – The initial number of objects in membranes is 2np + 2n+ 1 ∈Θ(n·p). – The number of rules is of the order O(n2·p2). – The maximal number of objects involved in any rule is 3∈Θ(1). (c) The pair (cod, s)of polynomial-time computable functions defined fulfills the following: for each input formula ϕof the UNIQUE SAT problem, s(ϕ)is a natural number, cod(ϕ) is an input multiset of the system Π(s(ϕ)), and for each t∈N,s−1(t)is a finite set. (d) The family Πis polynomially bounded. Indeed, for each input formula ϕof the UNIQUE SAT problem, the number of computation steps of the system Π(s(ϕ)) + cod(ϕ)is the following: (a) at most n+ 2p+ 4 in the case of the input formula has not or has exactly one truth satisfying truth assignment; and (b) n+ 2p+ 3 in the case that there are more than one truth assignments making true ϕ. (e) The family Πis sound and complete with regard to (X, cod, s). This can be informally deduced from the overview of the computations previously described. Therefore, the family Πof P systems designed in the previous section solves the UNIQUE SAT problem in a uniform way in polynomial time. 6. Conclusions Polarizationless P systems with active membranes and no dissolution rules are non efficient computing models, in the sense that only problems in class Pcan be solved in an efficient way by these P systems. In this paper, a uniform and polynomial time solution to the UNIQUE SAT problem is provided by means of a family of polarizationless P systems when minimal cooperation (the length of the left-hand side of a rule is at most 2) and minimal production (the length of the right-hand side of a rule is 1) are considered in object evolution rules. US is the class of problems that have a unique solution for each instance. It is easy to prove that UNIQUE SAT is complete for this complexity class [3]. A very interesting open problem