The P Versus NP Problem Through Cellular Computing with Membranes

The P Versus NP Problem Through Cellular Computing with Membranes Mario J. P´erez-Jim´enez, Alvaro Romero-Jim´enez, and Fernando Sancho-Caparrini Abstract. We study the P versus NP problem through membrane systems. Language accepting P systems are introduced as a framework allowing us to obtain a characterization of the P = NP relation by the polynomial time unsolvability of an NP–complete problem by means of a P system. 1 Introduction The P versus NP problem [2] is the problem of determining whether every language accepted by some non-deterministic algorithm in polynomial time is also accepted by some deterministic algorithm in polynomial time. To define the above problem precisely we must have a formal definition for the concept of an algorithm. The theoretical model to be used as a computing machine in this work is the Turing machine, introduced by Alan Turing in 1936 [10], several years before the invention of modern computers. A deterministic Turing machine has a transition function providing a functional relation between configurations; so, for every input there exists only one computation (finite or infinite), allowing us to define in a natural way when an input is accepted (through an accepting computation). In a non-deterministic Turing machine, for a given configuration several successor configurations can exist. Therefore, it could happen that for a given input different computations exist. In these machines, an input is accepted if there exists at least one finite accepting computation associated with it. The class P is the class of languages accepted by some deterministic Turing machine in a time bounded by a polynomial on the length (size) of the input. From an informal point of view, the languages in the class P are identified with the problems having an efficient algorithm that gives an answer in a feasible time; the problems in P are also known as tractable problems. The class NP is the class of languages accepted by some non-deterministic Turing machine where for every accepted input there exists at least one accepting computation taking an amount of steps bounded by a polynomial on the length of the input. Every deterministic Turing machine can be considered as a non-deterministic one, so we have P⊆NP. In terms of the previously defined classes, the Pversus NP problem can be expressed as follows: is it verified the relation NP ⊆P? The P? =NP question is one of the outstanding open problems in theoretical computer science. The relevance of this question does not lie only in the inherent pleasure of solving a mathematical problem, but in this case an answer to it could provide an information of a high practical interest. For instance, a negative answer to this question would confirm that the majority of current cryptographic systems are secure from a practical point of view. On the other hand, a positive answer could not only entail the vulnerability of cryptographic systems, but this kind of answer is expected to come together with a general procedure which will provide a deterministic algorithm solving any NP-complete problem in polynomial time. Moreover, the problems known to be in the class NP but not known to be in Pare varied and of highest practical interest. An NP–complete problem is a hardest (in certain sense) problem in NP; that is, any problem in NP could be efficiently solved using an efficient algorithm which solves a fixed NP–complete problem. These problems are the suitable candidates to attack the Pversus NP problem. In the last years several computing models using powerful and inherent tools inspired from nature have been developed (because of this reason, they are known as bio-inspired models) and several solutions in polynomial time to problems from the class NP have been presented, making use of non-determinism or of an exponential amount of space. This is the reason why a practical implementation of such models (in biological, electronic, or other media) could provide a quantitative improvement for the resolution of NP-complete problems. In this work we focus on one of these models, the cellular computing model with membranes, specifically, on one of its variants, the language accepting P systems, in order to develop a computational complexity theory allowing us to attack the Pversus NP problem from other point of view than the classical one. The paper is structured as follows. The next section is devoted to the definition of language accepting P systems. In section 3 a polynomial complexity class for the above model is introduced. Sections 4 and 5 provides simulations of deterministic Turing machines by P systems and language accepting P systems by deterministic Turing machines. Finally, in section 6 we establish a characterization of the Pversus NP problem through P systems. 2 Language Accepting P Systems Until the end of 90’s decade several natural computing models have been introduced simulating the way nature computes at the genetic level (genetic algorithms and DNA based molecular computing) and at the neural level (neural networks). In 1998, Gh. P˘aun [5] suggests a new level of computation: the cellular level. Cells can be considered as machines performing certain computing processes; in the distributed framework of the hierarchical arrangement of internal vesicles, the communication and alteration of the chemical components of the cell are carried out. Of course, the processes taking place in the cell are complex enough for not attempting to completely model them. The goal is to create an abstract cell-like computing model allowing to obtain alternative solutions to problems which are intractable from a classical point of view. The first characteristic to point out from the internal structure of the cell is the fact that the different units composing the cell are delimited by several types of membranes (in a broad sense): from the membrane that separates the cell from the environment into which the cell is placed, to those delimiting the inner vesicles. Also, with regard to the functionality of these membranes in nature, it has to be emphasized the fact that they do not generate isolated compartments, but they allow the chemical compounds to flow between them, sometimes in selective forms and even in only one direction. Similar ideas were previously considered, for instance, in [1] and [3]. P systems are described in [4] as follows: a membrane structure consists of several membranes arranged in a hierarchical structure inside a main membrane (called the skin) and delimiting regions (each region is bounded by a membrane and the immediately lower membranes, if there are any). Regions contain multisets of objects, that is, sets of objects with multiplicities associated with the elements. The objects are represented by symbols from a given alphabet. They evolve according to given evolution rules, which are also associated with the regions. The rules are applied non-deterministically, in a maximally parallel manner (in each step, all objects which can evolve must do so). The objects can also be moved (communicated ) between regions. In this way, we get transitions from one configuration of the system to the next one. This process is synchronized: a global clock is assumed, marking the time units common to all compartments of the system. A sequence (finite or infinite) of transitions between configurations constitutes a computation; a computation which reaches a configuration where no rule is applicable to the existing objects is a halting computation. With each halting computation we associate a result,bytaking into consideration the objects collected in a specified output membrane or in the environment. For an exhaustive overview of transition P systems and of their variants and properties, see [4]. Throughout this paper, we will study the capacity of cellular systems with membranes to attack the efficient solvability of presumably intractable decision problems. We will focus on a specific variant of transition P systems: language accepting P systems. These systems have an input membrane,andworkinsuch a way that when introducing in the input membrane a properly encoded string, a “message” is sent to the environment, encoding whether this string belongs or not to a specified language. Definition 1. Amembrane structure isarootedtree,wherethenodesarecalled membranes, the root is called skin,andtheleavesarecalledelementary membranes. Definition 2. Let µ=(V(µ),E(µ)) be a membrane structure. The membrane structure with external environment associated with µis the rooted tree such that: (a) the root of the tree is a new node that we denote by env; (b) the set of nodes is V(µ)∪{env}; and (c) the set of edges is E(µ)∪{{env, skin}}. The node env is called environment of the structure µ. So, every membrane structure has associated in a natural way an environment. Definition 3. Alanguage accepting P system (with input membrane and external output) is a tuple Π=(Σ,Γ,Λ,#,µ Π,M1, ..., Mp,(R1,ρ 1), ..., (Rp,ρ p),i Π) verifying the following properties: –The input alphabet of Πis Σ. –The working alphabet of Πis Γ,withΣΓand #∈Γ−Σ. –µΠis a membrane structure consisting of pmembranes, with the membranes (and hence the regions) injectively labelled with 1,2,...,p. –iΠis the label of the input membrane. –The output alphabet of Πis Λ={Yes,No}. –M1, ..., Mpare multisets over Γ−Σ, representing the initial contents of the regions of 1,2,...,p of µΠ. –R1, ..., Rpare finite sets of evolution rules over Γassociated with the regions 1,2,...,p of µΠ. –ρi,1≤i≤p, are partial order relations over Rispecifying a priority relation among rules of Ri. An evolution rule is a pair (u, v), usually represented u→v,whereuis a string over Γand v=vor v=vδ,withvastringover Γ×{here, out}∪{ini|i=1,...,p}. Consider a rule u→vfrom a set Ri. To apply this rule in membrane imeans to remove the multiset of objects specified by ufrom membrane i(the latter must contain, therefore, sufficient objects so that the rule can be applied), and to introduce the objects specified by v, in the membranes indicated by the target commands associated with the objects from v. Specifically, for each (a, out)∈van object awill exit the membrane iand will become an element of the membrane immediately outside it (that is, the father membrane of membrane i), or will leave the system and will go to the environment if the membrane iis the skin membrane. If vcontains a pair (a, here), then the object awill remain in the same membrane iwhere the rule is applied (when specifying rules, pairs (a, here) are simply written a, the indication here is omitted). For each (a, inj)∈van object ashould be moved in the membrane with label j, providing that this membrane is immediately inside membrane i (that is, membrane iis the father of membrane j); if membrane jis not directly accesible from membrane i(that is, if membrane jis not a child membrane of membrane i), then the rule cannot be applied. Finally, if δappears in v,then membrane iis dissolved; that is, membrane iis removed from the membrane structure, and all objects and membranes previously present in it become elements of the immediately upper membrane (the father membrane) while the evolution rules and the priority relations of the dissolved membrane are removed. The skin membrane is never dissolved; that is, no rule of the form u→vδis applicable in the skin membrane. All these operations are done in parallel, for all possible applicable rules u→v, for all occurrences of multisets uin the membrane associated with the rules, and for all membranes at the same time. TherulesfromthesetRi,1≤i≤p, are applied to objects from membrane isynchronously, in a non-deterministic maximally parallel manner; that is, we assign objects to rules, non-deterministically choosing the rules and the objects assigned to each rule, but in such a way that after this assignation no further rule can be applied to the remaining objects. Therefore, a rule can be applied in the same step as many times as the number of copies of objects allows it. On the other hand, we interpret the priority relations between the rules in astrong sense:aruleu→vin a set Rican be used only if no rule of a higher priority exists in Riand can be applied at the same time with u→v. Aconfiguration of Πis a tuple (µ, ME,M i1,...,M iq), where µis a membrane structure obtained by removing from µΠall membranes different from i1,...,i q (of course, the skin membrane cannot be removed), MEis the multiset of objects contained in the environment of µ,andMijis the multiset of objects contained in the region ij. For every multiset mover Σ(the input alphabet of the P system), the initial configuration of Πwith input misthetuple(µΠ,∅,M1, ..., MiΠ∪m, ..., Mp). That is, in any initial configuration of Πthe environment is empty. We will denote by IΠthe collection of possible inputs for the system Π. Given a configuration Cof a P system Π, applying properly the evolution rules as described above, we obtain, in a non-deterministic way, a new configuration C.WedenotebyC⇒ΠC, and we say that we have a transition from C to C.Ahalting configuration is a configuration in which no evolution rule can be applied. Acomputation Cof a P system is a sequence of configurations, {Ci}i<r, where: C0is an initial configuration of the system; Ci⇒ΠCi+1, for every i<r; and, either r∈N+(that is, it is a non-zero natural number) and Cr−1is a halting configuration,orr=∞, in which case it is said that Cis not halting. For a computation C={Ci}i<r we will denote by Mj Ethe content of the environment in the configuration Cj. Next we define the output of the P system. Definition 4. The output of a computation C={Ci}i<r is: Output(C)=     Yes,if Cis halting, Yes∈Mr−1 Eand No ∈ Mr−1 E, No,if Cis halting, No ∈Mr−1 Eand Yes∈ Mr−1 E, not defined,otherwise. If Csatisfies any of the two first conditions, then we say that it is a successful computation. Definition 5. A language accepting P system is said to be valid if every halting computation is a successful computation and every halting computation, and only them, sends out the symbol #(and only in the last step). We denote by LA the class of valid language accepting P systems. Next we define what it means that such P systems accept or decide alanguage. Definition 6. Let Lbe a language over an alphabet Ω. We say that the system Π∈LAaccepts the language Lif the following properties are verified: –There exists a total function, cod :Ω∗→IΠ, computable and injective, encoding strings over Ωby means of multisets over the input alphabet of Π. –For every string w∈Ω∗it is verified that: •If w∈L, then there exists acomputation Cof Πwith input cod(w)such that Cis halting and Output(C)=Yes. •If there exists acomputation Cof Πwith input cod(w)such that Cis halting and Output(C)=Yes,thenw∈L. Definition 7. Let Lbe a language over an alphabet Ω. We say that the system Π∈LAdecides the language Lif the following properties are verified: –Every computation of Πis halting. –There exists a total function, cod :Ω∗→IΠ, computable and injective, encoding strings over Ωby means of multisets over the input alphabet of Π. –For every string w∈Ω∗it is verified that: •If w∈L, then for every computation Cof Πwith input cod(w)it is verified that Output(C)=Yes. •If w∈ L, then for every computation Cof Πwith input cod(w)it is verified that Output(C)=No. 3 A Polynomial Complexity Class in Cellular Systems In order to give a formal definition of computational complexity classes in this model, we have to first specify what we mean by a decision problem. Definition 8. Adecision problem,X,isapair(IX,θ X)such that IXis a language (over a finite alphabet) whose elements are called instances of the problem and θXis a total Boolean function over IX. A decision problem Xis solvable by a Turing machine TM if IXis the set of inputs of TM, for any w∈IXthe Turing machine halts over w,andwis accepted if and only if θX(w)=1. To solve a problem by means of P systems, we usually construct a family of such devices so that each element decides the instances of equivalent size,ina certain sense which will be specified below. Definition 9. Let g:N+→N+be a total computable function. We say that a decision problem Xis solvable by a family of valid language accepting P systems, in a time bounded by g, and we denote this by X∈MCLA(g),ifthereexistsa family of P systems, Π=Π(n)n∈N+, with the following properties: 1. For every n∈Nit is verified that Π(n)∈LA. 2. There exists a Turing machine constructing Π(n)from nin polynomial time (we say that Πis polynomially uniform by Turing machines). 3. There exist two functions, cod :IX→n∈N+IΠ(n)and s:IX→N+, computable in polynomial time, such that: –For every w∈IX,cod(w)∈IΠ(s(w)). –The family Πis bounded, with regard to (X, cod, s, g); that is, for each w∈IXevery computation of the system Π(s(w)) with input cod(w)is halting and, moreover, it performs at most g(|w|)steps. –The family Πis sound, with regard to (X, cod, s); that is, for each w∈IX if there exists an accepting computation of the system Π(s(w)) with input cod(w),thenθX(w)=1. –The family Πis complete, with regard to (X, cod, s); that is, for each w∈IXif θX(w)=1, then every computation of the system Π(s(w)) with input cod(w)is an accepting computation. Note that we impose a certain kind of confluence of the systems, in the sense that every computation with the same input must return the same output. As usual, the polynomial complexity class is obtained using as bounds the polynomial functions. Definition 10. The class of decision problems solvable in polynomial time by a family of cellular computing systems belonging to the class LA,is PMCLA = gpoly. MCLA(g). This complexity class is closed under polynomial-time reducibility. Proposition 1. Let Xand Ybe two decision problems such that Xis polynomial-time reducible to Y.IfY∈PMCLA,thenX∈PMCLA. 4 Simulating Deterministic Turing Machines by P Systems In this section we consider deterministic Turing machines as language decision devices. That is, the machines halt over any string on the input alphabet, with the halting state equal to the accepting state, in the case that the string belongs to the decided language, and with the halting state equal to the rejecting state in the case that the string does not belong to the language. It is possible to associate with a Turing machine a decision problem, and this will permit us to define what means that such a machine is simulated by a family of P systems. Definition 11. Let TM be a Turing machine with input alphabet ΣTM.The decision problem associated with TM is the problem XTM =(I,θ),whereI= Σ∗ TM, and for every w∈Σ∗ TM,θ(w)=1if and only if TM accepts w. Obviously, the decision problem XTM is solvable by the Turing machine TM. Definition 12. We say that a Turing machine TM is simulated in polynomial time by a family of systems of the class LA,ifXTM ∈PMCLA. Next we state that every deterministic Turing machine can be simulated in polynomial time by a family of systems of the class LA. Proposition 2. Let TM be a deterministic Turing machine working in polynomial time. Then XTM ∈PMCLA. See chapter 9 of [8], which follows ideas from [9], for details of the proof. 5 Simulating Language Accepting P Systems by Deterministic Turing Machines In this section we are going to prove that if a decision problem can be solved in polynomial time by a family of language accepting P systems, then it can also be solved in polynomial time by a deterministic Turing machine. For the design of the Turing machine we were inspired by the work of C. Zandron, C. Ferretti and G. Mauri [11], with the difference that the mentioned paper deals with P systems with active membranes. Proposition 3. For every decision problem solvable in polynomial time by a family of valid language accepting P systems, there exists a Turing machine solving the problem in polynomial time. Proof. Let Xbe a decision problem such that X∈PMCLA. Then, there exists a family of valid language accepting P systems Π=Π(n)n∈N+such that: 1. The family Πis polynomially uniform by Turing machines. 2. There exist two functions cod :IX→n∈N+IΠ(n)and s:IX→N+, computable in polynomial time, such that: –For every w∈IX,cod(w)∈IΠ(s(w)). –The family Πis polynomially bounded, with regard to (X, cod, s). –The family Πis sound and complete, with regard to (X, cod, s). Given n∈N+,letAnbe the number of symbols in the input alphabet of Π(n), Bnthe number of symbols in the working alphabet, Cnthe number of symbols in the output alphabet, Dnthe number of membranes, Enthe maximum size of the multisets initially associated with them, Fnthe total number of rules of the system, and Gnthe maximum length of them. Since the family Πis polynomially uniform by Turing machines, these numbers are polynomial with respect to n. Let mbe an input multiset of the system Π(n). Given a computation Cof Π(n) with input m,wedenotebyHn(m) the maximum number of digits, in base 2, of the multiplicities of the objects contained in the multisets associated with the membranes of the systems and with the environment, in any step of C. Naturally, this number depends on C, but what we are interested in, and we will prove at the end of the proof, is that any computation of the system Π(s(w)) with input cod(w) verifies that Hs(w)(cod(w)) is polynomial in the size of the string w. Next, we associate with the system Π(n) a deterministic Turing machine, TM(n), with multiple tapes, such that, given an input multiset mof Π(n), the machine reproduces aspecific computation of Π(n)overm. The input alphabet of the machine TM(n) coincides with that of the system Π(n). On the other hand, the working alphabet contains, besides the symbols of the input alphabet of Π(n) the following symbols: a symbol for each label assigned to the membranes of Π(n); the symbols 0 and 1, that will allow to operate with numbers represented in base 2; three symbols indicating if a membrane has not been dissolved, has to be dissolved or has been dissolved; and three symbols that will indicate if a rule is awaiting, is applicable or is not applicable. Subsequently, we specify the tapes of this machine. –We have one input tape, that keeps a string representing the input multiset received. –For each membrane of the system we have: •One structure tape, that keeps in the second cell the label of the father membrane, and in the third cell one of the three symbols that indicate if the membrane has not been dissolved, if the membrane has to dissolve, or if the membrane has been dissolved. •For each object of the working alphabet of the system: ∗One main tape, that keeps the multiplicity of the object, in base 2, in the multiset contained in the membrane. ∗One auxiliary tape, that keeps temporary results, also in base 2, of applying the rules associated with the membrane.