An apparently innocent problem in Membrane Computing

An apparently innocent problem in Membrane Computing David Orellana-Mart´ın, Luis Valencia-Cabrera, Agust´ın Riscos-N´u˜nez, 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, ariscosn, marper}@us.es Summary. The search for efficient solutions of computationally hard problems by means of families of membrane systems has lead to a wide and prosperous field of research. The study of computational complexity theory in Membrane Computing is mainly based on the look for frontiers of efficiency between different classes of membrane systems. Every frontier provides a powerful tool for tackling the Pversus NP problem in the following way. Given two classes of recognizer membrane systems R1and R2, being systems from R1non-efficient (that is, capable of solving only problems from the class P) and systems from R2presumably efficient (that is, capable of solving NP-complete problems), and R2the same class that R1with some ingredients added, passing from R1to R2is comparable to passing from the non efficiency to the presumed efficiency. In order to prove that P=NP, it would be enough to, given a solution of an NP-complete problem by means of a family of recognizer membrane systems from R2, try to remove the added ingredients to R2from R1. In this paper, we study if it is possible to solve SAT by means of a family of recognizer P systems from AM0(−d, +n), whose non-efficiency was demonstrated already. Key words: Membrane Computing, polarizationless P systems with active membranes, cooperative rules, the Pversus NP problem, SAT problem. 1 Introduction Membrane Computing is a bio-inspired computing model based on the behavior and the structure of living cells. Introduced by Gh. P˘aun in 1998 [4], it has been used in a wide range of applications, and several variants have been developed depending on the field of study. From the beginning, the research of computational complexity issues from the perspective of membrane systems has been a prosperous field of study, with several papers written and interesting results found. The 128 D. Orellana, L. Valencia, A. Riscos, M.J. P´erez first “solution” to an NP-complete problem, the SAT problem, in linear time is presented in [5]. We say “solution” since there was no definition of solving a problem by means of membrane systems. There was no definition until [8] where recognizer membrane systems (called decision membrane systems in the paper, and accepting membrane systems in a later paper), for a family of membrane systems of a certain type capable of solving a computational problem. In the following years, for demonstrating the non-efficiency of membrane systems (that is, the capability of only solving problems from the class P), some tools were developed, as the simulation technique [7], the algorithmic technique [] and the dependency graph technique [1]. By using the former, in [1] it was demonstrated that P systems from PMCAM0(−d,+n)were capable of solving only problems from the class P. As complexity classes PMCR, being Ra class of recognizer membrane systems, was demonstrated to be closed under polynomial reduction [], finding an efficient solution to any NP-complete problem by means of a family of P systems from AM0(−d, +n) would lead to a negative answer to the P6=NP conjecture; that is, it solving an NP-complete problem in this framework leads to P=NP. It seems interesting then trying to find a solution based on the most common techniques while solving a computationally hard problem. From here, the paper is organized as follows: in the next section, a brief view to the general structure of techniques to solve NP-complete problems by membrane systems is given. Section 3 is devoted to present a “solution” to the SAT problem, such that it depends of the existence of some special machines. These machines are detailed in the following two sections, explaining the structure in Section 4 and the behavior in Section 5. After that, in Section 6, the three kinds of special machines introduced are reduced to a single one, capable of solving each of the problems of the previous machines. Last, the main result is presented in Section 7. The paper ends with some conclusions and interesting open research lines. 2 Solutions to NP-complete problems In the framework of Membrane Computing, several efficient solutions to computationally hard problems have been provided by means of a family of membrane systems; that is, they are solutions that run in polynomial time with respect of the size of the input. Usually, this is done by interchanging time and space, in the sense that we need to create an exponential workspace in terms of membranes or cells in the computation in order to obtain all the possible alternatives to solve the instance, and taking advantage of the inherent parallelism of membrane systems to check them at the same time. For this purpose, a family of membrane systems must be defined, each of its systems solving a subset of all the instances of the problem. Usually, the protocol to solve computationally hard problems is the following one: An apparently innocent problem in Membrane Computing 129 1. Generation stage: In this stage, using division rules [6], separation rules [3] or membrane creation rules [2], among others, we can obtain an exponential workspace in terms of membranes or cells in polynomial (or even linear time). 2. Checking stage: In this stage, the presumed solutions in the previous stage are checked in order to know if any of them is a real solution of the instance. 3. Output stage: This stage consists in sending an object yes or an object no to the environment depending on the solvability or not of the instance. In this sense, an interesting work for the reader is [9], where solutions are analyzed by decomposing the solutions in subroutines. 3 A “solution” to the SAT problem without using dissolution Here we provide a solution to the SAT problem by means of a family of recognizer P systems with active membranes Π={Π(t)|t∈N}from AM0(−d, +n) with a special mechanism whose behavior will be explained later. Given a Boolean formula ϕin CNF and simplified with nvariables and pclauses, the system Π(s(ϕ)) + cod(ϕ) processes it, being s(ϕ) = hn, pi=(n+p)(n+p+1) 2+nand cod(ϕ) = {xi,j,0|xi∈Cj}∪{xi,j,0| ¬xi∈Cj}. For each n, p ∈N, we consider the recognizer P system Π(hn, pi)=(Γ, Σ, µ, M1,M2,M3, multisets(Mi,j )(1 ≤i≤n, 1≤j≤p), multisets(Mi,j,l)(1 ≤i≤ d n 2le,1≤j≤p, 1≤l≤ dlog2ne), multisets(Mj)(1 ≤j≤p), multisets(Md,l)(1 ≤l≤ dlog2ne), multisets(Mr),R, iin, iout), from AM0(−d, +n) where: 1. Working alphabet Γ: {yes,no, a, a0}∪{ai,j |1≤i≤n, 1≤j≤2i−1} ∪ {ti,j, fi,j |1≤i≤n, 2i≤j≤2n−1} ∪ {Ti,j, Fi,j |1≤i≤n, 0≤j≤n−1}∪{Ti, Fi, ti, fi|1≤i≤n} ∪ {xi,j,k, xi,j,k |1≤i≤n, 1≤j≤p, 1≤k≤3n} ∪ {ci,j,l |1≤i≤2n 2l,1≤j≤p, 1≤l≤ dlog2ne} ∪ {cj,l |1≤j≤p, 1≤l≤(j−1)(k+ 2) + 1}∪{dj|1≤j≤p} ∪ {dp,l |1≤l≤ dlog2ne+ 1} ∪ alphabet(Mi,j )(1 ≤i≤n, 1≤j≤p)∪ alphabet(Mi,j,l)(1 ≤i≤ d n 2le,1≤j≤p, 1≤l≤ dlog2ne)∪ alphabet(Mj)(1 ≤j≤p)∪alphabet(Md,l)(1 ≤l≤ dlog2ne)∪alphabet(Mr) 2. Input alphabet Σ: {xi,j,0, xi,j,0|1≤i≤n, 1≤j≤p} 3. Initial multisets: M1=∅,M2=∅,M3={ai,1|1≤i≤n} 4. The rule set Rconsists on the following rules: 130 D. Orellana, L. Valencia, A. Riscos, M.J. P´erez 1.1Rules to create pcopies of every possible truth assignment in each of the 2nmembranes labelled by 2. [ai,j →ai,j+1 ]3for 2 ≤i≤n, 1≤j≤2i−2 [ai,2i−1]3→[ti,2i]3[fi,2i]3for 1 ≤i≤n [an,2n−1]3→[Tn,n+1 ]3[Fn,n+1 ]3 [ [ ]3[ ]3]2→[ [ ]3]2[ [ ]3]2 [ti,j →ti,j+1 ]3 [fi,j →fi,j+1 ]3)for 1 ≤i≤n−1,2i≤j≤2n−2 [ti,2n−1→Ti,i+1 ]3 [fi,2n−1→Fi,i+1 ]3)for 1 ≤i≤n−1 [Ti,j →Ti,j−1]3 [Fi,j →Fi,j−1]3)for 1 ≤i≤n, 1≤j≤i+ 1 [Ti,0]3→Ti,i [ ]3 [Fi,0]3→Fi,i [ ]3)for 1 ≤i≤n [Tn,0]3→Tn[ ]3 [Fn,0]3→Fn[ ]3 [Ti,j →Ti,j+1 ]2 [Fi,j →Fi,j+1 ]2)for 1 ≤i≤n−2, i ≤j≤n−2 [Ti,n−1→Ti]2 [Fi,n−1→Fi]2)for 1 ≤i≤n−1 [Ti→tp i]2 [Fi→fp i]2)for 1 ≤i≤n−1 2.1Rules to check which clauses are satisfied by the truth assignments. [xi,j,k →xi,j,k+1 ]2 [xi,j,k →xi,j,k+1 ]2)for 1 ≤i≤n, 1≤j≤p, 0≤k≤3n−1 xi,j,3n[ ]Mi,j →[a0]Mi,j xi,j,3n[ ]Mi,j →[a0]Mi,j )for 1 ≤i≤n, 1≤j≤p [a0→a]Mi,j for 1 ≤i≤n, 1≤j≤p ti[ ]Mi,j →[a]Mi,j fi[ ]Mi,j →[a]Mi,j )for 1 ≤i≤n, 1≤j≤p Mi,j(3n+ 2) : a2 ci,j,1in ksteps for 1 ≤i≤n, 1≤j≤p An apparently innocent problem in Membrane Computing 131 2.2 Rules to obtain only one copy of each object cj, if possible. c2i−1,j,l [ ]Mi,j,l →[a0]Mi,j,l c2i,j,l [ ]Mi,j,l →[a]Mi,j,l )for 1≤i≤ d n 2le, 1≤j≤p, 1≤l≤ dlog2ne [a0→a]Mi,j,l for 1≤i≤ d n 2le, 1≤j≤p, 1≤l≤ dlog2ne 2l−1membranes of each type Mi,j,l are present in the step 3n+ 1 Mi,j,l((3n+ 3) + 2l+k(l−1)) : a2 ci,j,l+1 a ci,j,l+1 )in ksteps for 1≤i≤ d n 2le, 1≤j≤p, 1≤l≤ dlog2ne − 1 M1,j,dlog2ne((3n+ 3) + (2 + k)dlog2ne − 1) : a2 cj,1 a cj,1)in ksteps for 1 ≤ j≤p 3.1Rules to check if all the clauses are satisfied by a truth assignment. dj−1[ ]Mj→[a0]Mj cj,(j−1)(k+2)+1 [ ]Mj→[a]Mj)for 1 ≤j≤p [cj,l →cj,l+1 ]2for 1 ≤j≤p, 1≤j≤(j−1)(k+ 2) Mj((3n+ 3) + (2 + k)dlog2ne+ 2j+k(j−1)) : a2 djin ksteps for 1 ≤ j≤p 4.1Rules to obtain only one copy of the object dp, if possible. [dp]2→dp,1[ ]2 dp,l [ ]Md,l →[a]Md,l for 1 ≤l≤ dlog2ne 2l−1membranes of each type Md,l are present in the step (3n+ 3) + (2 + k)(dlog2ne+p) Md,l((3n+ 3) + (2 + k)(dlog2ne+p)+2l+k(l−1)) : a2 dp,l+1 a dp,l+1 )for 1 ≤ l≤ dlog2ne 4.2Rules to return the correct answer. dp,dlog2ne+1 [ ]Mr→[a]Mr Mr((3n+ 3) + (2 + k)(2dlog2ne+p+ 1)) : a yes a0 no )in ksteps [yes ]1→yes [ ]1 [no ]1→no [ ]1 5. The input membrane is the membrane labelled by 2 (iin = 2) and the output zone is the environment (iout =env). 132 D. Orellana, L. Valencia, A. Riscos, M.J. P´erez The proposed solution follows a brute force algorithm in the framework of recognizer P systems with active membranes without dissolution rules and division rules for elementary and non-elementary membranes, and it consists on the following stages: 1. Generation stage: Using rules from 1.1, 2nmembranes labelled by 2 and 3 will be produced. Each of the membranes labelled by 2 will contain a different truth assignment for the nvariables. This stage takes 3n+ 1 time steps. 2. First checking stage: In this stage, an object cj,1will be produced in the membranes labelled by 2 whose truth assignment makes true the clause Cj. First of all, with rules from 2.1, multiple copies of objects ci,j,1will be produced, and later with the rules from 2.2will lead to a single copy of objects cj,1if there was at least one object ci,j,1. This stage takes (2 + k)dlog2ne. 3. Second checking stage: In this stage, an object dpwill be produced in a membrane labelled by 2 if the truth assignment associated with it makes true the whole formula ϕ, by using rules from 3.1. This stage takes p(2+k) time steps. 4. Output stage: Finally, by using rules from 4.1, a single object dp,dlog2newill be produced in the skin membrane if there exists at least one truth assignment that makes true the formula ϕ. If such an object exists, the system will send an object yes to the environment. Otherwise, it will return an object no. This is done by using the rules from 4.2. This stage takes dlog2ne+ 4 time steps. 4 Details of the special machines In the previous solution, new syntax with respect to the classical of membrane systems appears. Let us define some kind of “machines” that follows a not-so-much special behavior. A machine Miis no more than a P system from the corresponding family, in this case, from AM0(−d, +n). Given a machine Mi, we say that multisets(Mi) will be the multisets of objects placed initially in the membranes within the structure of the machine Mi,alphabet(Mi) will be the working alphabet of the machine and if there is a rule of the kind Mi(t) : rules, the machine Miwill execute the corresponding rule associated to the number of objects placed in the system at configuration Ct. In ksteps, the machine Miwill return the corresponding answer to the parent membrane. Of course, not all the machines will spend the same amount of time steps, since in the end they are P systems and different machines can spend different times, but for the sake of simplicity, we say that they spend the same number of time steps. Later, we will look for a simple machine that must spend exactly ktime steps, and that machine will be a “sub-routine” used for the ones used in the solution. As opposed to oracles, that in this sense they can be though as machines that start working when they receive some input, these machines are “running” from the first configuration; that is, they are P systems that work as a P system of its family, so it cannot accomplish tasks that are impossible for P systems of its own An apparently innocent problem in Membrane Computing 133 family. We can think that the “machine” can wait until step tby using subscripts and evolution rules. Since division rules are allowed for both elementary and nonelementary rules, we can ensure that we can obtain enough number of machines of each kind. For this purpose, if a machine Mineeds to be replicated into 2kcopies, a single copy of this machine is present at the beginning of the computation. In the skin membrane of this machine, there is a leaf membrane labelled by d, and such that it contains an object: a1. Let us define the following rules: [a2i→a2i+1 ]dfor 1 ≤i≤k−1 [a2i−1]d→[a2i]d[a2i]dfor 1 ≤i≤k [ [ ]d[ ]d]skinMi→[ [ ]d]skinMi[ [ ]d]skinMi By using these rules, we can obtain 2kexact copies of the machine Miin 2k−1 steps. The label dis a label such that it is not used in the whole machine Mi. Since the rest of objects are supposed to be evolving within their corresponding membranes, this process does not affect in this task. 5 Duties of the special machines Five different machines are described in the previous solution. As discussed in the previous section, a machine Misuch that it has a rules defined as Mi(t) : rule, then when the configuration Ctis reached, the rule will be executed from the next transition. In ktime steps, it will return to its parent membrane the corresponding answer. •Mi,j: If there are 2 copies of the object a, then it returns an object ci,j,1. Otherwise, it returns nothing. •Mi,j,l: If there are 1 or 2 copies of the object a, then it returns an object ci,j,l+1. Otherwise, it returns nothing. •Mj: If there are 2 copies of the object a, then it returns an object dj. Otherwise, it returns nothing. •Md,l: If there are 1 or 2 copies of the object a, then it returns an object dp,l+1. Otherwise, it returns nothing. •Mr: If there are 1 copy of the object a, then it returns an object yes. If there are no copies of the object a, it returns no. Otherwise, it returns nothing. As we can observe, three different behaviors are required here. For instance, the answers of Mi,j and Mjare similar. Since they do not return the same object, we can think that we have a single type of machine Mi, and it is within a membrane labelled by M0 i,j (respectively, M0 j). The behavior of this machine is simple: If there are 2 copies of the object a, then it returns yes. Otherwise, it returns no. The corresponding answer would be sent at the (k−1)-th time step to the membrane 134 D. Orellana, L. Valencia, A. Riscos, M.J. P´erez M0 i,j (resp., M0 j). Then, in the k-th time step, the membrane M0 i,j (resp., M0 j) would send to the parent membrane an object ci,j,1(resp., dj) if an object yes appeared in the previous configuration, and it would not send anything if an object no had appeared. 1. Mi,j, Mj: Differentiate between 1 and 2 copies of object a. 2. Mi,j,l, Md,l: Differentiate between 1 or 2 and none copies of object a. 3. Mr: Differentiate between 1 and 0 copies of object a. In fact, taking into account that we are deciding if the number of objects ais equal to a number, then we can generalize these three cases into a single one, in order to have a single problem to be solved. 6 Covering all the cases What we are trying to solve here is deciding if the number of objects of a certain type corresponds to a particular number. Then, the following question could generalize the previous problems: Can we differentiate the existence of a single object from the non-existence or the multiple existence of the object? Or, more formally, if there is a single instance of an object, then return yes. Otherwise, return no. We are going to give a proof on how these three cases can be reduced to this question. 1. The first case is reduced as follows: let Mi,1,Mi,2and Mi,3be three machines that solve the current problem. Then, we can think that the machine Miis formed as follows: Mi Mi,1 a Mi,2 An apparently innocent problem in Membrane Computing 135 For sending objects ato each machine Mi,j, they can be replicated by using object evolution rules and sent to them by using send-in rules (for the order, subscripts can be used). Mi,1will solve the problem normally; that is, if there is only one object a, then it will send an object yes1to Miin ksteps, otherwise, it will return an object no1. At the same time, the problem will be solved in Mi,2, but as there is an object apresent in the system, it will return an object yes2if there are no objects ain Mi, otherwise it will return an object no2. If Mi,1returns an object yes1, it means that there is only one copy of the object a. Therefore, Miwill not send anything to its parent membrane. If Mi,1returns no1, there are two possibilities: On the one hand, there can be no objects a, then Mi,2will return an object yes2. On the other hand, there can be two copies of object a, then Mi,2will return Mi,2will return an object no2. The following table represent the desired output for each possibility: Input Mi,1Mi,2Output n= 0 no1yes2no n= 1 yes1no2no n= 2 no1no2yes Since these three cases are the only possible ones, it is easy to see that if only an object no is present, it must return no (that will not be sent to the parent membrane, since in these situations, there is only one or none copies of object a). The other possible situation is that two objects no appear. In that case, we should return an object yes (that later will be sent to the parent membrane as the corresponding object). It is easy to do it by changing objects noito objects a. If there is a single copy, the machine Miwill return nothing. Otherwise, it will send to the parent membrane the corresponding object. 2. The second case is similar to the first one. In this case, the objective of Miis to return an object when there are 1 or 2 copies of the object a. In the other case; that is, when there are no copies of the object a, it will return nothing. As in the previous case, we will have the following structure: