An optimal solution to the SAT problem with tissue P systems
Abstract
In the framework of membrane computing, several frontiers of e ciency have been found with respect to the resources that di erent families of P systems take to solve a decision problem. Each of these frontiers provides a new way to tackle the P versus NP problem. In this sense, optimal frontiers are needed in order to separate close variants of P systems. In a previous work, an e cient solution to SAT was given in the framework of P systems from T DC(3). In this work, we will provide an optimal solution to the SAT problem in terms of length of the rules.
Full text
An optimal solution to the SAT problem with tissue P systems David Orellana-Mart´ın, Luis Valencia-Cabrera, Mario J. P´erez-Jim´enez Research Group on Natural Computing Department of Computer Science and Artificial Intelligence Universidad de Sevilla Avda. Reina Mercedes s/n, 41012 Sevilla, Spain E-mail: {dorellana, lvalencia, marper}@us.es Summary. In the framework of membrane computing, several frontiers of efficiency have been found with respect to the resources that different families of P systems take to solve a decision problem. Each of these frontiers provides a new way to tackle the Pversus NP problem. In this sense, optimal frontiers are needed in order to separate close variants of P systems. In a previous work, an efficient solution to SAT was given in the framework of P systems from T DC(3). In this work, we will provide an optimal solution to the SAT problem in terms of length of the rules. Key words: Membrane Computing, tissue P systems, symport/antiport rules, SAT problem. 1 Introduction One of the most prolific fields within the framework of Membrane Computing is computational complexity theory. The search for frontiers of efficiency has produced several results in terms of correspondences between classic computational complexity classes and membrane computing complexity classes. In particular, several results with tissue P systems [5] have been achieved. Recognizer tissue P systems were introduced in [6]. In [3], it was demonstrated that the complexity class of tissue P systems from T DC(1) are non-efficient systems through the dependency graph technique. In [6], an efficient solution to the SAT problem is given by means of a family of tissue P systems from T DC(5). In this work, we present an optimal solution for SAT with a family of tissue P systems from T DC(2). This implies that NP ∪co −NP ⊆PMCT DC(2). However, this last result is not new, since in [9] it was presented a solution to HAM-CYCLE, a well-known NP-complete problem, with a family of P systems from T DC(2). The novelty of this work is to present an efficient SAT solver, given the relevance of the problem. The paper is
92 D. Orellana, L. Valencia, M.J. P´erez organized as follows. In Section 2, some prerequisites about languages and sets are given. The next section is devoted to introduce tissue P systems, and the complexity classes associated to them. In Section 4, an efficient solution to SAT by means of tissue P systems from T DC(2) is given, and in the next section an overview of the computations is given. Finally, the work finishes with some conclusions. 2 Preliminaries An alphabet Γis a non-empty set whose elements are called symbols. A string u over Γ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 (Γ, 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, 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∈Γ. The difference of m1and m2, denoted by m1\m2, is the multiset (Γ, g) where g(x) = f1(x)−f2(x) for each x∈Γ. We denote by M(Γ) the set of all multisets over Γ. The Cantor pairing function is used to encode two natural numbers into a single one, and is defined as follows: given x, y ∈N,hx, yi=(x+y+1)(x+y) 2+y 3 Tissue P systems with symport/antiport rules Definition 1. A recognizer tissue P system with symport/antiport rules and division rules of degree q≥1is a tuple Π= (Γ, Σ, E,M1,...,Mq,R, iin, iout), where: 1. Γ,Σand Eare finite alphabets such that Σ, E ⊆ Γand Σ∩ E =∅. 2. M1,...,Mqare multisets over Γ\(Σ∪ E). 3. Ris a set of rules of the following types: (a) Communication rules: (i, u/v, j), for i, j ∈ {0,1, . . . , q}, i 6=j, u, v ∈ M(Γ),|u|+|v|>0. (b) Division rules: [a]i→[b]i[c]i, for i∈ {1, . . . , q}, a, b, c ∈Γ. 4. iin ∈ {1, . . . , q}and iout =env. A recognizer tissue P system with symport/antiport rules and division rules Π= (Γ, Σ, E,M1,...,Mq,R, iin, iout) of degree q≥1 can be viewed as a se of qcells, labelled by 1, . . . , q with an environment labelled by 0 such that: (a)
An optimal solution to the SAT problem with tissue P systems 93 M1, . . . Mqare the multisets of objects initially placed in the qcells of the system; (b) Eis the set of objects located initially placed in the environment of the system, all of them appearing in an arbitrary number of copies; and (c) iin ∈ {1, . . . , q}, iout =env represent distinguished cells where objects of the instance are introduced and which will encode the output of the system, respectively. When applying a rule (i, u/v, j), the objects of the multiset represented by u are sent from region ito region jand, simultaneously, the objects of multiset vare sent from region jto region i. The length of the communication rule (i, u/v, j) is defined as |u|+|v|, that is, the total number of objects which appear in the rule. A communication rule (i, u/v, j) is called a symport rule if u=λor v=λ. A symport rule (i, u/λ;j), with i6= 0, j 6= 0 provides a virtual arc from cell ito cell j. A communication rule (i, u/v, j) is called an antiport rule if u6=λand v6=λ. An antiport rule (i, u/v, j), with i6= 0, j 6= 0, provides two arcs: one from cell i to cell jand another one from cell jto cell i. Thus, every tissue P systems has an underlying directed graph whose nodes are the cells of the system and the arcs are obtained from communication rules. In this context, the environment can be considered as a virtual node of the graph such that their connections are defined by communication rules of the form (i, u/v, j), with i= 0 or j= 0. When applying a division rule [ a]i→[b]i[c]i, cell iis duplicated into two new cells with the same label. Object adissapears and an object bis created in the first new cell and an object cis created in the second new cell. The rest of the objects within the cell iare duplicated in the two new cells. The rules of a system like the one above are used in a non-deterministic maximally parallel manner as it is customary in Membrane Computing. At each step, all communication rules which can be applied will be applied in a maximally parallel way (at each step we apply a multiset of rules which is maximal, no further applicable rule can be added). Only a single division rule can be applied to each cell. If a division rule is applied to a cell, we say that this cell is is “blocked”, and no communication rules can be applied to that cell in that computational step. An instantaneous description or a configuration at any instant of a tissue P system is described by all multisets of objects over Γassociated with all the cells present in the system, and the multiset of objects over Γ\ E associated with the environment at that moment. Bearing in mind that the objects from E have infinite copies in the environment, they are not properly changed along the computation. The initial configuration is (M1,...,Mq;∅). A configuration is a halting configuration if no rule of the system is applicable to it. Let us fix a tissue P system with symport/antiport rules Π. We say that configuration Ciyields configuration Ci+1 in one transition step, denoted Ci⇒ΠCi+1, if we can pass from Cito Ci+1 by applying the rules from Rfollowing the previous remarks. A computation of Πis a (finite or infinite) sequence of configurations such that: (a) the first term of the sequence is an initial configuration of the system; (b) each non-initial configuration of the sequence is obtained from the previous configuration by applying the rules of the system in a maximally parallel manner with the restrictions previously mentioned; and (c) if the sequence is finite (called
94 D. Orellana, L. Valencia, M.J. P´erez halting computation), then the last term of the sequence is a halting configuration. All computations start from an initial configuration and proceed as stated above;only halting computations give a result, which is encoded by the objects present in the environment in the halting configuration. Given that they are recognizer P systems, all computations halt and return the same output. We denote a recognizer membrane system Πwith the input multiset min the input region as Π+m. 3.1 Complexity classes associated to tissue P systems Let Rbe a class of recognizer membrane systems. We say that PMCRis the class of problems solvable efficiently in a uniform way by means of a family of recognizer membrane systems from R. The class of recognizer tissue P systems with symport/antiport rules with length at most kand division rules is denoted by T DC(k), k ≥1. For more information about computational complexity theory in the framework of membrane computing, we refer the reader to [7, 8]. 4 A solution to SAT in T DC(2) In this section, an efficient solution to the SAT problem by means of a family of P systems will cell division and symport/antiport rules of length at most 2 is presented. For each pair of natural numbers n, p ∈N, we will consider the recognizer tissue P system with cell division and symport/antiport rules Π(hn, pi)=(Γ, E, Σ, M1,...,Mnp+3,R, iin, iout) of degree np + 3 defined as follows: (a) Γ=Σ∪ E ∪ {yes,no, α, β0, γ0}∪{cj|1≤k≤p} ∪ {αk|0≤k≤np −1}∪{ai,j |1≤i≤n, 1≤j≤p} ∪ {Ti,j, Fi,j |1≤i≤n, 1≤j≤p} ∪ {xi,j,k, xi,j,k |1≤i≤n, 1≤j≤p, 0≤k≤np} (b) E={αk|np ≤k≤2np + 2}∪{βk|1≤k≤2np + 4} ∪ {γk|1≤k≤2np + 5}∪{xi,j,k, xi,j,k |1≤i≤n, 1≤j≤p, np + 1 ≤k≤2np} (c) Σ={xi,j,0, xi,j,0|1≤i≤n, 1≤j≤p} (d) Mi=∅for 1 ≤i≤np,Mnp+1 ={yes,no, β0, γ0},Mnp+2 ={ai,j |1≤i≤ n, 1≤j≤p}∪{cj|1≤j≤p}∪{α},Mnp+3 ={α0}. (e) The set of rules Ris the following: 1. Rules to generate pcopies of the 2ntrue possible truth assignments. For this, 2np partial truth assignments will be generated. [ai,j ]np+2 →[Ti,j ]np+2[Fi,j ]np+2 (np + 2, Ti,jFi,j0, /λ, env)for 1≤i≤n, 1≤j, j0≤p
An optimal solution to the SAT problem with tissue P systems 95 2. Rules to generate 2np copies of cod(ϕ). (np + 1, xi,j,0/λ, i +n·(j−1)) (np + 1, xi,j,0/λ, i +n·(j−1))for 1≤i≤n, 1≤j≤p [xi,j,k ]i+n·(j−1) →[xi,j,k+1 ]i+n·(j−1)[xi,j,k+1 ]i+n·(j−1) [xi,j,k ]i+n·(j−1) →[xi,j,k+1 ]i+n·(j−1)[xi,j,k+1 ]i+n·(j−1) for 1≤i≤n, 1≤j≤p, 0≤k≤np −1 (i+n·(j−1), xi,j,k/xi,j,k+1, env) (i+n·(j−1), xi,j,k/xi,j,k+1, env)for 1≤i≤n, 1≤j≤p, np ≤k≤2np −1 3. Rules to check which clauses are satisfied by the truth assignment (np + 2, Ti,j/xi,j,2np, i +n·(j−1)) (np + 2, Fi,j/xi,j,2np, i +n·(j−1))for 1≤i≤n, 1≤j≤p (np + 2, cjxi,j,2np/λ, env) (np + 2, cjxi,j,2np/λ, env)for 1≤i≤n, 1≤j≤p [αk]np+3 →[αk+1 ]np+3 [αk+1 ]np+3 for 0≤k≤np −1 (np + 3, αnp+k/αnp+k+1, env)for 0≤k≤np + 1 (np + 1, βk/βk+1, env)for 0≤k≤2np + 3 (np + 1, γk/γk+1, env)for 0≤k≤2np + 4 (np + 2, α/α2np+2, np + 3) (np + 2, α2np+2cj/λ, env)for 1≤j≤p 4. Rules to return a negative answer (np + 1, β2np+4, γ2np+5/λ, np + 3) (np + 1,no/β2np+4, np + 3) (np + 3,no/λ, env) 5. Rules to return a positive answer (np + 1, β2np+4/α2np+2, np + 2) (np + 1, α2np+2yes/λ, env) (f) iin =np + 1 and iout =env 5 An overview of the computations In this section, we will explain a brief overview of the computations. Let ϕbe a propositional logic formula in conjunctive normal form, where V ar(ϕ) = {x1, . . . , xn}. Then, ϕis of the form ϕ=C1∧. . . ∧Cp, where Cj is a clause such that Cj=l1,j ∨. . . lpj,j, li,j ∈ {xi,¬xi}. The pair (cod, s) for this family is cod(ϕ) = {xi,j |xi∈Cj}∪{xi,j | ¬xi∈Cj}, and s=hn, pi. For that, let us remember that the input is an instance of the SAT problem. Let ϕthe input formula with nvariables and pclauses. The tissue P system that will give the answer to the instance is Π(hn, pi) + cod(ϕ).
96 D. Orellana, L. Valencia, M.J. P´erez 5.1 Generation stage The first 2np steps will be devoted to generate both the 2npossible truth assignments. For this, rules from 1and 2are used. On the one hand, With rules from 1, 2np cells with label np + 2 with different truth assignments. The second rule is fired in order to remove incompatible truth assignments in the following sense: if two different assignments are given to the same variable, then the corresponding objects are sent to the environment. In this way, the incompatible assignments are removed and the remaining objects will be equivalent to a valid truth assignment. On the other hand, rules from 2will create 2np copies of each object from cod(ϕ). Being li,j,0∈cod(ϕ), at the end of the stage, there will be 2np cells i+n· (j−1) (1 ≤i≤n, 1≤j≤p) with an object li,j,2np in the corresponding cell. Besides these rules, 2np cells with label np + 3 with an object α2np+2 will be generated with rules from 3. This stage will take 2np steps. 5.2 First checking stage In this stage, clauses validated by the truth assignments are going to be analyzed. For this, rules from 3are used. In particular, in the first step of the stage objects Ti,j and Fi,j are interchanged with objects xi,j,2np and xi,j,2np, respectively. Then, objects xi,j,2np and xi,j,2np will represent that the literal limakes true clause Cj. Then, if an object xi,j,2np or xi,j,2np exists in a cell labelled by np + 2, it will “remove” the corresponding object cj, sending it to the environment. When the stage is over, cells labelled by np + 2 will contain only the objects cjsuch that the clause Cjhas not been satisfied by the corresponding truth assignment. This stage takes 2 steps. 5.3 Second checking stage The satisfiability of the input formula ϕwill be analyzed in this stage. Last two rules from 3will be used. In the first step, object αfrom cells labelled by np + 2 will be interchanged with object α2np+2 from cells labelled by np + 3. Object α2np+2 in cells labelled by np + 3 is a mark to know if there are remaining objects cj. With the last rule, any remaining object cjwill “remove” object α2np+2 from the corresponding cell np + 2. Therefore, if a truth assignment does not satisfy the whole formula ϕ, object α2np+2 will not be present in the corresponding cell np + 2. This stage takes 2 steps. 5.4 Output stage The output stage starts at the 2np + 5 step, and takes 4 steps in the negative case and 2 steps in the affirmative case.
An optimal solution to the SAT problem with tissue P systems 97 -Affirmative answer: In this case, there will exist a cell labelled by np + 2 that will have an object α2np+2, as it represents a truth assignment that makes true the input formula ϕ. With the application of the first rule from 5, it will be interchanged by the object β2np+4 from cell np + 1. At the same time, object γ2np+5 will go inside cell labelled by 1. Since object β2np+4 has been moved from cell np + 2, they will not interact with each other. In the next step, as object α2np+2 is present in the cell np + 1, it will send object yes to the environment. Then, the computation ends. -Negative answer: In this case, all objects α2np+2 will be in the environment, as there is no truth assignment such that it makes true all clauses from ϕ. Therefore, in the previous stage there was at least one object cjin each cell labelled by np+2 and it will send object α2np+2 to the environment. In the first step of this stage, object γ2np+5 will go into cell labelled by np+1. In the next step, objects β2np+4 and γ2np+5 will interact and be sent to a cell labelled by np + 3. Following that, object no will be interchanged with the object β2np+4, and then object no will be sent to the environment. The computation stops here. Theorem 1. SAT ∈PMCT DC(2) Proof. The family of P systems previously constructed verifies the following: •Every system of the family Πis a recognizer P system from T DC(2). •The family Πis polynomially uniform by Turing machines because for each n, p ∈N, the rules of Π(hn, pi) of the family are recursively defined from n, p ∈N, and the amount of resources needed to build an element of the family is of a polynomial order in nand p, as shown below: – Size of the alphabet: 4n2p2+ 10np +p+ 17 ∈Θ(n2p2). – Initial number of cells: np + 3 ∈Θ(np). – Initial number of objects in cells: np +p+ 6 ∈Θ(np). – Number of rules: 2n2p2+np2+ 11np +p+ 7 ∈Θ(n2p2). – Maximal number of objects involved in any rule: 2 ∈Θ(1). •The pair (cod, s) of polynomial-time computable functions defined fulfills the following: for each input formula ϕof SAT problem, s(ϕ) is a natural number, cod(ϕ) is an input multiset for the system Π(s(ϕ)), and for each n∈N,s−1(n) is a finite set. •The family Πis polynomially bounded: indeed, for each input formula ϕof SAT problem, the deterministic P system Π(s(ϕ))+cod(ϕ) takes exactly np+7 steps, being nthe number of variables in ϕand pits number of clauses. •The family Πis sound with regard to (X, cod, s): for each formula ϕ, if the computation of Π(s(ϕ)) + cod(ϕ) is an accepting computation, then ϕis satisfiable. •The family Πis complete with regard to (X, cod, s): for each input formula ϕ such that it is satisfiable, the computation of Π(s(ϕ))+cod(ϕ) is an accepting computation. Corollary 1. NP ∪co −NP ⊆PMCT DC(2)
98 D. Orellana, L. Valencia, M.J. P´erez 6 Conclusions In the framework of membrane computing, as mentioned above, we search for frontiers of efficiency as new ways to attack the Pversus NP problem. For that, it is necessary to have both results of non-efficient classes and efficient classes of membrane systems. The thinner the frontier, the easier would be to try to adapt an efficient solution from the efficient model to the non-efficient model. The SAT problem is the best-known NP-complete problem, since it was the first problem to be demonstrated to be NP-complete [1, 4], and therefore is one of the most studied problems to solve the conjecture. SAT solvers are systems implemented to give an answer to an input SAT instance [2]. Implementations on high-performance computing platforms could be useful to simulate this solution since it could provide a good alternative to current industrial SAT solvers. More precisely, this solution only requires of 2 objects at most in communication rules, that could be an advantage in the implementation. As future work we will continue studying the efficiency of different variants of recognizer membrane systems. Acknowledgements This work was supported in part by the research project TIN2017-89842-P, cofinanced by Ministerio de Econom´ıa, Industria y Competitividad (MINECO) of Spain, through the Agencia Estatal de Investigaci´on (AEI), and by Fondo Europeo de Desarrollo Regional (FEDER) of the European Union. References 1. S. Cook. The complexity of theorem proving procedures. Proceedings of the Third Annual ACM Symposium on Theory of Computing, 1971, pp. 151–158. (doi:10.1145/800157.805047). 2. C.P. Gomes, H.A. Kautz, A. Sabharwal, B. Selman. Satisfiability Solvers. Handbook of Knowledge Representation (2008). 3. R. Guti´errez-Escudero, M.J. P´erez-Jim´enez, M. Rius-Font. Characterizing tractability by tissue-like P systems. Membrane Computing, 10th International Workshop, WMC 2009, Curtea de Arges, Romania, August 24-27, 2009, Revised Selected and Invited Papers. Lecture Notes in Computer Science, 5957 (2010), 289-300 (doi:10.1007/978-3-642-11467-0 21) A preliminary version in Gh. Paun, M.J. P´erez-Jim´enez, A. Riscos (eds.) Proceedings of the Tenth Workshop on Membrane Computing, Curtea de Arges (Romania), August 24-27, 2009, pp. 269-281. 4. R.M. Karp. Reducibility Among Combinatorial Problems. In R.E. Miller; J.W. Thatcher (eds.) Complexity of Computer Computations (1972). New York: Plenum. pp. 85-103. ISBN 0-306-30707-3. 5. C. Mart´ın-Vide, J. Pazos, Gh. P˘aun, A. Rodr´ıguez Pat´on. A new class of symbolic abstract neural nets: tissue P systems. Lecture Notes in Computer Science,2387 (2002), pp. 290-299
An optimal solution to the SAT problem with tissue P systems 99 6. Gh. P˘aun, M.J. P´erez-Jim´enez, A. Riscos-N´u˜nez. Tissue P systems with cell division. International Journal of Computers, Communications & Control,3, 3 (2008), pp. 295-303 7. M.J. P´erez-Jim´enez. An Approach to Computational Complexity in Membrane Computing. In G. Mauri, Gh. P˘aun, M.J. P´erez-Jim´enez, G. Rozenberg, A. Salomaa (eds.) Membrane Computing. WMC 2004. Lecture Notes in Computer Science, 3365 (2005). Springer, Berlin, Heidelberg, pp. 125-148. 8. M.J. P´erez–Jim´enez. A Computational Complexity Theory in Membrane Computing. In Gh. P˘aun, M.J. P´erez-Jim´enez, A. Riscos-N´u˜nez, G. Rozenberg, A. Salomaa (eds.) Membrane Computing. WMC 2009. Lecture Notes in Computer Science, 5957 (2010). Springer, Berlin, Heidelberg, pp. 85-109. 9. A.E. Porreca, N. Murphy, M.J. P´erez-Jim´enez. An Optimal Frontier of the Efficiency of Tissue P Systems with Cell Division. In M.´ A. Mart´ınez-del-Amor, Gh. P˘aun, I. P´erez-Hurtado, F.J. Romero-Campero (eds.) Proceedings of the Tenth Brainstorming Week on Membrane Computing, Report RGNC 01/2012, 2012, pp. 141-166.