Decision P Systems and the P =NP Conjecture

Decision P Systems and the P=NP Conjecture Mario J. P´erez Jim´enez, ´Alvaro Romero Jim´enez, and Fernando Sancho Caparrini Abstract. We introduce decision P systems, which are a class of P systems with symbol-objects and external output. The main result of the paper is the following: if there exists an NP–complete problem that cannot be solved in polynomial time, with respect to the input length, by a deterministic decision P system constructed in polynomial time, then P=NP. From Zandron-Ferreti-Mauri’s theorem it follows that if P= NP, then no NP–complete problem can be solved in polynomial time, with respect to the input length, by a deterministic P system with active membranes but without membrane division, constructed in polynomial time from the input. Together, these results give a characterization of P=NP in terms of deterministic P systems. 1 Introduction In [2] a new model of computation, called P Systems, is introduced within the framework of Natural Computing (bio-inspired compu ting). It is based upon the notion of membrane structure that is u sed to enclose computing cells in order to make them independent computing units. Also, a membrane serves as a communication channel between a given cell and other cells adjacent to it. This model starts from the observation that the processes which take place in the complex structure of a living cell can be considered as computations. Since these compu ting devices were introdu ced several variants have been considered. A fairly complete compendium about P systems can be found at [8]. In particular, P systems with external output are studied in [4]. The different variants of P systems found in the literature are in general generating devices. Many of them have been proved to be computationally complete: they compute all Turing compu table sets of natu ral nu mbers or all recursively enumerable languages, depending on the variant considered. The model we consider here works with symbol–objects and it has two characteristics that have seldom been considered before: we work with decision devices whose work is triggered by certain input data. The aim is to use this kind of P systems to deal with decision problems. The main goal of this paper is to show a sufficient condition for the relation P = NP to be verified: if there exists an NP–complete problem that cannot be solved in polynomial time, with respect to the input length, by any family of deterministic decision P systems, constructed in polynomial time, then P=NP. To achieve this, we prove that every decision problem which can be solved by a deterministic Turing machine in polynomial time can also be solved by a family of deterministic decision P systems in polynomial time. The paper is organized as follows: Section 2 briefly presents some basic concepts about P systems with external output; Section 3 introduces the new model (with symbol–objects) of decision P systems; Section 4 shows how to simulate deterministic Turing machines by families of such P systems; Section 5 establishes our main results about decision P systems and the P=NP conjecture. 2 Multisets, Membrane Structures, Evolution Rules Amultiset over a set, A, is a mapping m:A→IN ; m(a) is the number of copies of a∈Ain the multiset m. The set {a∈A:m(a)>0}is called the support of m and it is denoted by supp(m). A multiset, m, is said to be empty (resp. finite) if its support is empty (resp. finite). If mis a finite multiset over A, we will denote it m={{a1,...,a m}}, where the elements ai∈supp(m) are possibly repeated. We write M(A) for the set of all the multisets over A. For two multisets m1,m2 over Awe define their union by (m1∪m2)(a)=m1(a)+m2(a), for each a∈A. The set of membrane structures,MS, is defined by recursion as follows: 1. [ ] ∈MS;2.Ifµ1,...,µ n∈MS, then [µ1...µ n]∈MS. A membrane structure, µ, can also be seen as a rooted tree, V(µ),E(µ). Then, the nodes of this tree are called membranes, the root node the skin membrane, and the leaves elementary membranes. The degree of a membrane structure is the number of membranes in it. The membrane structure with environment associated with the membrane structure, µ,isµE=[ Eµ]E. If we consider µEas a rooted tree, then the root node is called the environment of µ. Given an alphabet, Γ, we associate with every membrane of a membrane structure a finite multiset of elements of Γ, which are called the objects of the membrane. We also associate with every one of these membranes a finite set of evolution rules. An evolution rule over Γis a pair (u, v), usually written u→v, where u is a string over Γand v=vor v=vδ, where vis a string over Γ×({here, out}∪{inl:l∈V(µ)}) and δis a special symbol not in Γ. The idea behind a rule is that the objects in u“evolve” into the objects in v, moving or not to another membranes and possibly dissolving the original membrane. The length of a rule is the number of symbols involved in the rule (for instance, the length of u→vis |u|+|v|+ 1). 3 Decision P Systems Definition 1. A decision P system is a construct Π=(Γ,Σ,µΠ,i Π,M1,...,Mp,(R1,ρ 1),...,(Rp,ρ p)), where: –Σis an alphabet, called the input alphabet. –Γis an alphabet such that Σ⊆Γ; its elements are called objects; there are two distinguished objects, Y ES,NO ∈Γ−Σ. –µΠis a membrane structure of degree p, the membranes of which we suppose labeled from 1to p. –iΠ∈{1,...,p}is the input membrane of Π. –Miis a multiset over Γ−Σassociated with the membrane labeled by i, for every i=1,...,p. –Riis a finite set of evolution rules over Γassociated with the membrane labeled by i, and ρiis a strict partial order over Ri, for every i=1,...,p. To formalize the semantics of this model we define first what a configuration of such a P system is, and then the notion of computation. Definition 2. Let Πbe a decision P system with external output. 1. A configuration of Πis a pair (µE,M), where µis a membrane structure such that V(µ)⊆V(µΠ)and it has the same root than µΠ, and Mis an application from V(µE)into M(Γ). For every node nd ∈V(µE)we denote Mnd =M(nd). 2. The initial configuration of Πfor the multiset m∈M(Σ)is the pair (µE,M), where µ=µΠ,ME=∅,MiΠ=m∪M iΠand Mj=Mj, for every j=iΠ. The idea is that for every input multiset m∈M(Σ), we add that multiset to the input membrane, iΠ, of the P system and then start the work of Π. We can pass, in a non-deterministic manner, from one configuration of Π to another by applying to its multisets the evolution rules associated with their corresponding membranes. This is done as follows: given a rule u→vof a membrane i, the objects in uare removed from Mi; then, for every (ob, out)∈v an object ob is put into the multiset associated with the parent membrane (or the external environment if iis the skin membrane); for every (ob, here)∈van object ob is added to Mi; finally, for every (ob, inj)∈van object ob is added to Mj(if jis not a child membrane of i, then the rule cannot be applied). Finally, if δ∈v, then the membrane iis dissolved (if iis the skin membrane, the rule cannot be applied), that is, it is removed from the membrane structure. The objects of a dissolved membrane remain in the region surrounding it, while the rules are removed. Moreover, the priority relation among the rules forbids the application of a rule if another one of higher priority is applied. Given two configurations, Cand C,ofΠ, we say that Cis obtained from C in one transition step, and we write C⇒C, if we can pass from the first to the second one by using the evolution rules appearing in the membrane structure of Cin a parallel and maximal way in each membrane, and for all the membranes at the same time. Definition 3. Let Πbe a decision P system. A computation, C,ofΠwith input m∈M(Σ)is a sequence, possibly infinite, of configurations of Π,C0⇒C1⇒ ...⇒Cq,q≥0, such that –C0is the initial configuration of Π, with the multiset mplaced in membrane iπ. –Each Ci(1 ≤i≤q)is obtained from the previous configuration by one transition step. We say that Cis a halting computation of Πif there is no rule applicable to the objects present in its last configuration. In this case, we say that Cqis the halting configuration of C. We say that Πis deterministic if for each m∈M(Σ)there exists an unique computation with input m. The philosophy of the P systems with external output is that we cannot know what is happening inside the membrane structure, but we can only collect the information sent out from it to the environment. Thus, it is natural that the halting computations of these P systems report to the environment when they have reached their final configurations (accepting or rejecting). Furthermore, the idea behind the decision P systems is to use them as languages decision devices. These considerations lead us to the following notions. Definition 4. A deterministic decision P system, Π, is said to be valid when the following is verified: –All computations of Πhalt. –For each computation of Πonly one rule of the form u→v(ob, out), where ob =Y ES or ob =NO, may be applied in the skin membrane of µΠ, and only in the last step of the computation. Definition 5. Let Πbe a deterministic valid decision P system. We say that a configuration (µE,M)of Πis an accepting (resp., rejecting) configuration if Y ES ∈ME(resp., NO ∈ME). We say that Cis an accepting (resp., rejecting) computation of Πif its associated halting configuration is an accepting (resp., rejecting) configuration. Definition 6. A deterministic valid decision P system, Π, accepts (respectively, rejects) a multiset m∈M(Σ)if the computation of Πwith input mis an accepting (resp. rejecting) computation. We denote by Dthe class of all deterministic valid decision P systems. 4 Simulating Turing Machines by Decision P Systems In what follows we are going to define what we mean by simulating a Turing machine (as a languages generating device) through a family of deterministic decision P systems. This has to be done in such a way that every solution for a decision problem given by a Turing machine provides a solution for the same problem by a decision P system. Moreover, the additional costs of the reduction from one solution to another must be polynomial in terms of the input size. We take as a model the concept of complexity classes in membrane systems introduced by G. P˘aun in [1]. Definition 7. We say that a deterministic Turing machine, TM, is simulated in polynomial time by a family of deterministic valid decision P systems ΠTM = (ΠTM(1),Π TM(2),...,Π TM(k),...)if: 1. The family ΠTM is D–consistent; that is, for each k∈N+,ΠTM(k)is a deterministic valid decision P system. 2. The family ΠTM is TM–uniform; that is, there exists a deterministic Turing machine, TM, which constructs ΠTM(k)in polynomial time starting from k≥1(there exists a polynomial p(k)depending on TM such that for each k,TM(k)halts in less than p(k)steps and its output is ΠTM(k)). 3. The family ΠTM is polynomially bounded; that is, there exists a polynomial p(k), depending on TM, such that every computation of ΠTM(k)always halts in less than p(k)steps. 4. The family ΠTM is TM–sound; that is, the Turing machine TM accepts (resp. rejects) the input string ai1...a ikif and only if ΠTM(k)accepts (resp. rejects) g(ai1...a ik)(gis a suitable polynomial encoding of strings by multisets). Note 1. The fact that the family ΠTM is D–consistent has the consequence that for each k≥1, the P system ΠTM(k) has a polynomial size in the following sense: the size of the working alphabet, the number of membranes, the size of the initial multisets, and the sum of the lengths of all the rules, is bounded by kr, for some constant rdepending on TM. Note 2. A suitable polynomial encoding, g, of strings by input multisets of ΠTM(k) means the following: there exists a Turing machine, TM, and a polynomial q(k) depending on TM such that for each input data wof TM we have that TM(w) halts in less than q(|w|) steps and its output is g(w) (an input multiset of the P system ΠTM(|w|)). Theorem 1. Each deterministic Turing machine can be simulated in polynomial time by a family of deterministic valid decision P systems. Proof. We consider deterministic Turing machines following [6]. Suppose we have QTM ={qN,q Y,q 0,...,q n},ΓTM ={B, -, a1,...,a m}, ΣTM ={a1,...,a p}, with p≤m, and δTM(qi,a j)=(qQ(i,j),a A(i,j),D(i, j)) as set of states, working alphabet, input alphabet and transition function for TM, respectively. We denote aB=Band a0=-. We construct a family of deterministic decision P systems ΠTM =(ΠTM(1), ΠTM(2),...,Π TM(k),...) which simulates TM as follows: for each k∈N, the decision P system ΠTM(k) is: •Input alphabet: Σk={a, i:a∈ΣTM,1≤i≤k} •Working alphabet: Γk={a, i:a∈ΣTM,0≤i≤k}∪{ti:1≤i≤k}∪ {s− i,s + i,s i:i∈{T1,T 2,F,S,1,...,9}} ∪ {qN,q Y,h,h ,YES,NO}∪ {qi:0≤i≤n}∪{bi,b  i,b  i,c i:0≤i≤m} •Membranes structure: µΠ=[ 1]1. •Input membrane: iΠ=1. •Initial multisets: M1={{q0,b 0,s − T1,s − T2,s − F,s − S,s − 1,...,s − 9,s T1}}. •Evolution rules: R=R0∪R1∪R2∪R3∪R4, where: •R0=R0,1∪R0,2∪R0,3∪R0,4,with R0,1≡sT1s− T1→s+ T1>s − T1→s− T1>ai,j→ai,jtj(1≤i≤p,1≤j≤k) s+ T1→s− T1sT2 R0,2≡sT2s− T2→s+ T2>s − T2→s− T2>t 2 1s+ T2→s− T2sF>···> >t 2 ks+ T2→s− T2sF>t 1...t ks+ T2→s− T2sS>s + T2→s− T2sF R0,3≡sFs− F→s+ F>s − F→s− F>     s− T1s− T2s− Ss− 1...s − 9s+ Fq0b0→(NO, out) ai,j→λ(1≤i≤p,1≤j≤k) tj→λ(1≤j≤k) R0,4≡     sSs− S→s+ S>s − S→s− S>ai,j→ai,j−12(1≤i≤p,1≤j≤k) ai,0→bi(1≤i≤p) >s + S→s− Ss1 •R1=R1,1∪R1,2∪R1,3,with R1,1≡s1s− 1→s+ 1>s − 1→s− 1>     h→hh bi→bib i(0≤i≤m) s+ 1→s− 1s2 R1,2≡           hs2s− 2→s+ 2>s 2→s3>s − 2→s− 2> >b 2 i→b i(0≤i≤m)>     b i→λ(0≤i≤m) b i→b i(0≤i≤m) s+ 2→s− 2s2 R1,3≡s3s− 3→s+ 3>s − 3→s− 3>b2 i→λ(0≤i≤m) s+ 3→s− 3s4 •R2=R2,1∪R2,2,with R2,1≡s4s− 4→s+ 4>s − 4→s− 4>h→hh s+ 4→s− 4s5 R2,2≡s5s− 5→s+ 5>s − 5→s− 5>   Rules for the transition function s+ 5→s− 5s6 The rules for the transition function, δTM, are the following: Case 1: state qr, element as=B Movement Rules left qrb sh→qQ(r,s)b scA(r,s),if A(r, s)=B qrb sh→qQ(r,s)b s,if A(r, s)=B stand qrb s→qQ(r,s)b scA(r,s),if A(r, s)=B qrb s→qQ(r,s)b s,if A(r, s)=B right qrb s→qQ(r,s)b scA(r,s)h, if A(r, s)=B qrb s→qQ(r,s)b sh, if A(r, s)=B Case 2: state qr, no element Movement Rules left qrh→qQ(r,s)cA(r,s),if A(r, s)=B qrh→qQ(r,s),if A(r, s)=B stand qr→qQ(r,s)cA(r,s),if A(r, s)=B qr→qQ(r,s),if A(r, s)=B right qr→qQ(r,s)cA(r,s)h, if A(r, s)=B qr→qQ(r,s)h, if A(r, s)=B To avoid conflicts, every rule in case 1 has higher priority than any rule in case 2. •R3=R3,1∪R3,2,with R3,1≡hs6s− 6→s+ 6>s 6→s7>s − 6→s− 6>     b i→b2 i(0≤i≤m) ci→c2 i(0≤i≤m) s+ 6→s− 6s6 R3,2≡s7s− 7→s+ 7>s − 7→s− 7>     bib i→λ(0≤i≤m) ci→bi(0≤i≤m) s+ 7→s− 7s8 •R4=R4,1∪R4,2,with R4,1≡s8s− 8→s+ 8>s − 8→s− 8>     qY→qYs9,q N→qNs9 qi→qis1(0≤i≤n) s+ 8→s− 8 R4,2≡s9s− 9→λ>s − 9→s− 9>                s− 1...s − 8→λ qY→(Y ES, out) qN→(NO, out) h→λ bi→λ(0≤i≤m) Let us see that ΠTM =(ΠTM(1),Π TM(2),...,Π TM(k),...) is a family of deterministic valid decision P systems which simulates TM. Obviously it is a family of deterministic valid decision P systems. Moreover, ΠTM is an uniform family. Indeed, let TM be a deterministic Turing machine such that the set of states has size n+ 2, the working alphabet has size m+2 and the input alphabet has size p(with p≤m). The necessary resources to construct ΠTM(k) are the following: 1. The size of the working alphabet Γkis p·k+4m+n+ 45; that is, in the order θ(k·m+n). 2. The degree of the P system is 1. 3. The size of the initial configuration for each x∈Σk TM is k+16∈θ(k). 4. The total number of rules is in the order of O(p·k+n·m)=O(k·m+n·m) 5. The greatest length of a rule is 16 ∈O(1). Let us see now that, for each k∈N,ΠTM(k)issound: let Lbe the language decided by TM. In order to decide if a string ai1...a ik∈ΣTM, of length k, belongs to L, we encode it by the multiset {{ai1,1,... ,aik,k}} which is the input given to ΠTM(k). The rules of this P system have been carefully chosen in such a way that its work goes through the following main stages: 1. Check that the multiset received as input codes a string of length k. For this, we have to verify that for each j=1,...,k there exists one and only one pair whose second component is equal to j. Otherwise, the P system halts and rejects the multiset. 2. Transform the input multiset into another multiset which encodes the string in base 2 (in order to specify the symbol written in each cell of the tape). 3. Read the element in the cell scanned by the head. 4. Compute the new element to be writen in the cell, move the head and change state (according to the transition function). 5. Erase the old element and write the new element. 6. Check if a final state is reached: if not, repeat from stage 2; if qYis the final state reached, then accept the string; if qNis the final state reached, then reject the string. These stages will be carried out in several small steps, each of them managed by a group of rules. To avoid rules from distinct steps being applied together, we will use s− jas forbidding objects and s+ jas permitting objects;ifs− jis present in the P system, then rules for step jcannot be executed; if, instead, s+ jis the object present, then rules for step jmust be executed (if possible). Of course, at any time, for each step only the corresponding forbidding or permitting object will be present. Also, there will always exist only one permitting object in the system. To indicate that we want to perform a step, we will use sjas promoter objects. When sjappears in the P system, it will transform its corresponding forbidding object s− jinto the permitting one s+ j, thus allowing the rules for step jto be applied. Then the permitting object will transform itself again into the forbidding one, and into a suitable promoter object. The first two stages take care of filtering the input multisets: those which do not encode a string of size kare rejected; those which do encode such strings are transformed in such a way that we have a code in base 2 of the symbols in the cells of the tape of the Turing machine. These operations are perfomed by the rules in R0. For a multiset to correctly encode a string of size k, it has to verify two conditions: for each j=1,...,k, it has to contain no more than one pair with second component equal to j; for each j=1,...,k, it has to contain at least one pair with second component equal to j. These two conditions are checked by rules in R0,1and R0,2, using objects tjas signals for the second components of the pairs. If the check fails, all objects in the P system are eliminated and it sends out the object NO, to reject the multiset. If the check passes, then we double jtimes each pair of the form a, j, changing them at the end by a bj. For a detailed description of the simulation of the running of the Turing machine over a correct multiset see [6]. We only recall here how we represent the Turing machine inside the P system. To represent the states we will use objects qN,q Y,q 0,...,q n. During the simulation, objects b0,...,b mwill represent, in base 2, the cells which contain symbols a0,...,a m, respectively (note that, at any time, the number of non-empty cells in the tapes of the Turing machine is finite); objects b 0,...,b  m,b  0,...,b  mwill be used as working copies of the previous objects; the single prime objects will also be useful to indicate the symbols read from the cells, and objects c0,...,c mwill be useful to indicate the new symbols to write into them. The cell scanned by the head, numbered from zero, will be represented by the object h, in base one; object hwill be used, when needed, as a working copy of object h; it will be used as a counter. Finally, let us see that the family ΠTM is polynomially bounded. Indeed, if x∈Σk TM is an input string of size kof the Turing machine, then we have: 1. The check for a multiset to correctly encode a string of size kneeds four steps in the affirmative case and six steps in the negative one (in this last case, the P system halts). 2. The generation of the multiset encoding, in base 2, the non-empty cells in the initial configuration of TM for xrequires k+ 3 steps of the P system. 3. The simulation of each transition step of the Turing machine requires a cost in the order of O(5j+12), where jis the cell being read by the head of TM.