A path to computational efficiency through membrane computing

A path to computational efficiency through membrane computing David Orellana-Martín, Luis Valencia-Cabrera, Agustín Riscos-Núñez, Mario J. Pérez-Jiménez Research Group on Natural Computing, Department of Computer Science and Artificial Intelligence, Universidad de Sevilla, Avda. Reina Mercedes s/n, 41012, Sevilla, Spain a b s t r a c t Keywords: Membrane computing P system with symport/antiport Membrane division Computational complexity The search for new mechanisms and tools allowing us to tackle the famous Pversus NP problem from new perspectives is an important task, due to the relevance of that problem. The concept of efficiency of computing models is associated with the ability to solve intractable (in a classical sense) problems in polynomial time. Assuming that P = NP, that concept is equivalent to the capability to solve NP-complete problems in an efficient way. Different frontiers of the efficiency have been given in Membrane Computing in terms of syntactical or semantic ingredients of the models. In particular, in the framework of tissue P systems with cell division using symport/antiport rules, the length of communication rules (passing from length 1 to length 2) provides an optimal borderline of the efficiency. Cell-like P systems with symport/antiport rules and membrane division is a restricted variant of such tissue P systems in both its structure (rooted tree versus undirected graph) and in the way membranes communicate with each other and with the environment. The limitations of efficient computations in such kind of P systems which use non-cooperative communication rules have been previously established. In this paper, a uniform polynomial time solution for the Hamiltonian cycle problem, a well known NP-complete problem, by means of cell-like P systems with membrane division using minimal cooperation in communication rules (at most two objects are involved), is provided. Hence, a new optimal boundary between tractability and NP-hardness, is provided: passing from non-cooperative rules to cooperative rules in cell-like P systems with symport/antiport rules and membrane division amounts to passing from non-efficiency to efficiency. 1. Introduction The Pversus NP problem is one of the most important open problems that have been formulated in theoretical computer science. This is the first problem of the famous list of the Millenium Prize Problems, including the seven greatest unsolved mathematical problems. Solving this problem might produce a huge economic impact. In an informal way, we can say that this problem analyzes whether or not finding solutions is harder than checking the correctness of possible solutions. It is widely believed that it is harder to solve a problem than to check that a solution is valid/good; that is, it is conjectured that E-mail addresses: dor[email protected] (D. Orellana-Martín), lv[email protected] (L. Valencia-Cabrera), [email protected] (A. Riscos-Núñez), [email protected] (M.J. Pérez-Jiménez). P= NP. The classical approach to solve this conjecture consists of considering a single NP-complete problem and trying to prove whether that problem belongs to the class Por not. In computing models, new tools to tackle the Pversus NP problem can be provided in terms of syntactical or semantic ingredients in the model. In this context, it is interesting to determine ingredients that allow us to efficiently solve computationally hard problems, and then investigate which ones should be removed in order to reduce the power so that only problems from Pcan be efficiently solved. The use (or not) of such ingredients provides a frontier between tractability and NP-hardness. Membrane computing is a flexible and versatile branch of natural computing, which arises as an abstraction of the compartmentalized structure of living cells, and the way biochemical substances are processed in (or moved between) membrane-bounded regions [18]. Inspired by the structure of living cells, two main classes of membrane systems have been investigated: a hierarchical (cell-like) arrangement of membranes, inspired from the structure of the cell [18] and a network of membranes (placed in the nodes of a directed graph), inspired from the cell-interconnection in tissues [13]or inspired from the way that neurons communicate with each other by means of short electrical impulses (spikes), emitted at precise moments of time [6]. All classes of computing devices considered in the field of membrane computing are generally called P systems, which are parallel and distributed computational models based on processing multisets of objects in cell-like or tissue-like structures by means of rewriting rules. A P system is cooperative if it contains rules that need more than one object to be triggered. A comprehensive information in membrane computing can be found in [20] and [22], and for the most up-to-date source of this area, please refer to [30]. Cell-like P systems with symport/antiport rules were introduced in [16], aiming to abstract the biological phenomenon of trans-membrane transport of pairs of chemical substances, in the same or in opposite directions. On the other hand, tissue P systems with symport/antiport rules were introduced in [17]by abstracting networks of elementary cells such that some of them are linked by “communication channels”. In eukaryotic cells, there are two relevant processes: mitosis and membrane fission. The first one is a process of nuclear division in eukaryotic cells during which one cell gives rise to two genetically identical children cells. Membrane fission occurs when a membrane leads to two separated membranes; that is, whenever a vesicle is produced or a larger subcellular compartment is divided into smaller discrete units. These processes have been a source of inspiration to incorporate new syntactical ingredients in membrane computing in order to be able to produce exponential workspace (by means of compartments) in polynomial — often linear — time. Specifically, inspired by the mitosis process, membrane division rules were defined in the framework of cell-like P systems providing computing devices called Psystems with active membranes [19]. With respect to the membrane fission process, P systems with membrane separation were introduced in [14]. These concepts were also considered in the framework of tissue-like P systems: tissue P systems with cell division [21] and tissue P systems with cell separation [15]. In previous works [4,5,8,7,15,23,25,26], new tools to tackle the Pversus NP problem are given in the framework of Membrane Computing. Let us recall that using families of non-cooperative tissue P systems with symport rules involving only one object and cell division, only problems in the complexity class Pcan be solved in polynomial time; that is P =PMCTDC(1) [3]. Nevertheless, families of tissue P systems with cell division and symport/antiport rules involving at most two objects (minimal cooperation) can solve NP-complete problems in polynomial time, which implies NP ∪co −NP ⊆PMCTDC(2)[29]. Hence, cooperation in communication rules provide a frontier of the efficiency in the framework of tissue P systems with symport/antiport rules and cell division, assuming that P = NP. This paper deals with cell-like P systems with symport/antiport rules and membrane division whose processor units are called membranes. This kind of P systems have important differences with respect to the tissue-like approach, where processor units are called cells: (a) the underlying structure is a rooted tree instead of a directed graph; (b) the rules are associated with the membranes instead of with the whole system; (c) the communication is only produced between a parent membrane and one of its child membranes instead of any two arbitrary cells; (d) only the skin membrane, the most external one, can communicate with the environment instead of each cell; and (e) only elementary membranes can be divided instead of each arbitrary cell. By using families of recognizer cell-like P systems with membrane division which use communication rules with length at most 3, uniform polynomial-time solutions to NP-complete problems have been provided [12]. In this paper, the previous result is improved showing that minimal cooperation (at most two objects involved in communication rules) is enough in order to solve NP-complete problems in uniform polynomial-time. Besides, it is known that with noncooperative rules, only problems in the class Pcan be solved efficiently [10]. In this manner, similar complexity results that in tissue-like P systems with symport/antiport rules and cell division have been obtained, but in a more restrictive syntactical context. The paper is structured as follows. In Section 2, some concepts needed for a more comprehensive reading of the paper are presented. The framework of recognizer cell-like P systems with symport/antiport rules and membrane division is introduced at Section 3. A uniform polynomial-time solution of the HAM-CYCLE problem by means of a family of P systems with membrane division using symport/antiport rules of length at most 2, is described in Section 4. Conclusions and some open problems are formulated in the last section. 2. Preliminaries In order to provide a self-contained paper, some basic concepts and notations are introduced in this section. 2.1. Languages and multisets An alphabet is a non-empty set and its elements are called symbols. A string u over is a mapping from a natural number n ∈Nonto . Number nis called length of the string uand it is denoted by |u|. The empty string (with length 0) is denoted by λ. A language over is a set of strings over . A multiset over an alphabet is an ordered pair (, f), where fis a mapping from onto the set of natural numbers N.For each x ∈we say that f(x)is the multiplicity of xin that multiset. The support of a multiset m =(, f)is defined as supp(m) ={x ∈ | f(x) >0}. A multiset is finite if its support is a finite set. We denote by ∅the empty multiset. The size of a finite multiset m =(, f)is x∈f(x), and it is denoted by |m|. 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 ∈. We say that m1is contained in m2and we denote it by m1⊆m2, if f1(x) ≤f2(x)for each x ∈. The relative complement of m2in m1, denoted by m1\m2, is the multiset (, g), where g(x) =f1(x) −f2(x)if f1(x) ≥f2(x), and g(x) =0otherwise. Let us note that a set is a particular case of a multiset when each symbol of the support has multiplicity 1. Notation: given a sequence x1, ..., xnof symbols of an alphabet, we denote by x1, ...,  xk, ..., xnthe sequence x1, ..., xk−1, xk+1, ..., xn; that is, the k-th term, xk, does not appear in that sequence. 2.2. Graphs and Hamiltonian cycles We recall some concepts from graph theory that are used in this paper. For more details on graph theory, please refer to [1]. A rooted tree is a connected, acyclic, undirected graph in which one of the vertices (called the root of the tree) is distinguished from the others. Given a node x(different from the root) in a rooted tree, if the last edge on the (unique) path from the root to node xis {x, y}(so x = y), then yis the parent of node x, and xis a child of node y. We denote it by y =p(x) and x ∈ch(y). The root is the only node in the tree with no parent. A node with no children is called a leaf. Let G =(V, E)be a directed graph, where the set of nodes is Vand the set of arcs is E⊆V×V. We say that a finite sequence γ=(xi1, xi2, ..., xir, xir+1)of nodes of Gis a simple path of Gfrom xi1to xir+1of length r≥1if (xij, xij+1) ∈Efor each 1 ≤j ≤r, and xij= xijfor each pair 1 ≤j <j≤r+1. A finite sequence γ=(xi1, xi2, ..., xir, xir+1)with xir+1=xi1is a simple cycle of length r, if the sequence (xi1, xi2, ..., xir)is a simple path and (xir, xir+1) ∈E. A Hamiltonian cycle of Gis a simple cycle γ=(uα1, uα2, ..., uαr, uα1)of Gsuch that V={uα1, uα2, ..., uαr}. Let (xi1, xi2, ..., xir, xir+1)be a simple path of a directed graph G =(V, E)with V={1, ..., n}. It is also denoted by the set {(xi1, xi2)1, ..., (xir, xir+1)r}. That is, the labelled arc (xik, xik+1)kcan be interpreted as the k-th arc of the path γ, for each k(1 ≤k ≤r). Throughout this work we denote AG={(i,j)k|1≤i,j,k≤n,(i,j)∈E}; A G={(i,j) k|1≤i,j,k≤n,(i,j)∈E}; A G={(i,j) k|1≤i,j,k≤n,(i,j)∈E}. It is easy to prove the following result: Proposition 2.1. Let G =(V, E)be a directed graph, V={1, ..., n}and AG={(i, j)k|1 ≤i, j, k ≤n, (i, j) ∈E}. If B ⊆AG, then the following assertions are equivalent: (1) B is a Hamiltonian cycle. (2) |B| =nand the following holds: for each i, i, j, j, k, k∈{1, ..., n}, (a)if (i, j)k∈B, (i, j)k∈B, and (i, j)k= (i, j)k, then k = k; (b)if (i, j)k∈B, (i, j)k∈B, and (i, j)k= (i, j)k, then i = i; (c)if (i, j)k∈B, (i, j)k∈B, and (i, j)k= (i, j)k, then j = j; (d)if (i, j)k∈B, and (i, j)k+1∈B, then j =i. As a consequence, the following are true: Remark 1. Let B ⊆AGbe a Hamiltonian cycle of G. For each i, i, j, j, k, k∈{1, ..., n}, the following holds: •if (i, j)k∈Band j = j, then (i, j)k/∈B; •if (i, j)k∈Band i = i, then (i, j)k/∈B; •if (i, j)k∈Band (i, j) = (i, j), then (i, j)k/∈B; •if (i, j)k∈Band j = i, then (i, j)k+1/∈B. Remark 2. If (xi1, xi2, ..., xin, xi1)is a Hamiltonian cycle of G, then we can describe it by the set B1={(xi1, xi2)1, (xi2, xi3)2, ..., (xin, xi1)n} ⊆AG. But (xi2, xi3, ..., xin, xi1, xi2)also represents the same Hamiltonian cycle and can be described as B2={(xi2, xi3)1, (xi3, xi4)2, ..., (xi1, xi2)n}, and so on up to Bn. Thus, given a Hamiltonian cycle of G, there are exactly n different subsets of AGcodifying that cycle. Remark 3. Let us suppose that the total number of Hamiltonian cycles of Gis q. Then, the number of different subsets Bof AGverifying conditions (a), (b), (c), and (d) from Proposition 2.1 is exactly n ·q. 2.3. 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 ∈IX|θ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 L over an alphabet we have LXL=L. The complement problem Xof a decision problem X=(IX, θX)is the decision problem (IX, ¬θX); that is, LX=∗ X\LX: for each instance the answer of Xis “yes” if and only if the answer of Xis “no”. 2.4. The Cantor pairing function The Cantor pairing function encodes pairs of natural numbers by single natural numbers and it is defined as follows: for each m, n ∈N m,n=(m+n)(m+n+1) 2+m The Cantor pairing function is a primitive recursive bijective function from N ×Nonto N. Then, for each t∈Nthere exists a unique natural number m, n ∈Nsuch that t=m, n. 3. P systems with symport/antiport rules and division rules A kind of cell-like P systems that use communication rules capturing the biological phenomenon of trans-membrane transport of several chemical substances was introduced in [16]. Specifically, two processes were considered. The first one allows a multiset of chemical substances to pass through a membrane in the same direction. In the second one, two multisets of chemical substances (located in different biological membranes) only pass with the help of each other (an exchange of objects between both membranes). This is the computing framework where this paper is developed. Next, recognizer P systems with symport/antiport rules and membrane division are briefly introduced (see [9]for more details). Recognizer membrane systems were introduced in [28], and they provide a natural framework to solve decision problems by means of families of membrane systems. We adapt this definition to P systems with symport/antiport rules and membrane division in a natural way. Definition 3.1. A recognizer P system with symport/antiport rules and membrane division of degree q ≥1is a tuple =(,E,,μ,M1,...,Mq,R1,...,Rq,iin,iout) where: –, E, are finite alphabets such that has two distinguished symbols yes and no, E,  and E⊆ \. –μis a rooted tree whose nodes are injectively labelled with 1, ..., q(the root of the tree is labelled with 1). –M1, ..., Mqare finite multisets over  \such that at least one copy of yes and no is present in some of them. –Ri, 1 ≤i ≤q, are finite sets of rules over of the following forms: ∗Communication rules: Symport rules: (u, out)or (u, in), where uis a multiset over such that |u| >0. Antiport rules: (u, out; v, in), where u, vare multisets over such that |u| >0 and |v| >0. ∗Division rules: [ a ]i→[ b ]i[ c]i, where a, b, c∈, i ∈{2, ..., q}, i = iout, and iis the label of a leaf of the tree μ. –iin ∈{1, ..., q}and iout =0(0 is the label of the environment). –All computations halt. –If Cis a computation of , then either symbol yes or symbol no (but not both) must have been released into the environment, and only at the last step of the computation. For each multiset mover , the initial configuration of with input multiset m is M1, ..., Miin +m, ..., Mq, that is, the input multiset mis added to the contents of the input membrane. We denote by  +mthe system with input multiset m. A computation of is a finite sequence of configurations such that the first term of the sequence is the initial configuration of the system and each non-first term of the sequence from the previous configuration by applying rules of the system in a non-deterministic maximally parallel manner; that is, no more rules could be applied to such configuration. If no rules can be applied to a configuration, we say that it is a halting configuration and the system finishes the computation. We say that a computation Cof is an accepting computation (respectively, rejecting computation) if object yes (respectively, object no) appears in the environment associated with the corresponding halting configuration of C, and neither object yes nor no appears in the environment associated with any non-halting configuration of C. For each natural number k ≥1, CDC(k)(respectively, CDA(k)or CDS(k)) denotes the class of all recognizer P systems with symport/antiport rules (respectively, only antiport rules or only symport rules) and membrane division such that the length of the communication rules is at most k. Next, the concept of efficient solvability for decision problems by means of families of recognizer membrane systems (see [24]for more details) is adapted to the new framework in a natural way. Definition 3.2. A decision problem Xis solvable in uniform polynomial-time by a family ={(n) |n ∈N}of recognizer P systems with symport/antiport rules and membrane division, if the following holds: –the family is polynomially uniform by Turing machines; that is, there exists a deterministic Turing machine working in polynomial time which constructs the system (n); –there exists a pair (cod, s)of polynomial-time computable functions over IXsuch that: for each instance u ∈IX, s(u)is a natural number and cod(u)is an input multiset of the system (s(u)); for each n ∈N, s−1(n)is a finite set; the family is polynomially bounded with regard to (X, cod, s); the family is sound and complete with regard to (X, cod, s) The instance u ∈IXwill be processed by the system (s(u)) with input multiset cod(u). Furthermore, from the soundness and completeness is deduced that (s(u)) +cod(u)is a confluent system, in the sense that all possible computations of (s(u)) +cod(u)must give the same answer. If Ris a class of recognizer P systems with symport/antiport rules and membrane division, then we denote by PMCRthe set of all decision problems which can be solved in uniform polynomial-time by means of recognizer P systems from R. The class PMCRis closed under complement and polynomial-time reductions (see [27]for details). In [10], the limitations of efficient computations in recognizer P systems with symport/antiport rules and membrane division when communication rules are non-cooperative rules have been established. Specifically, in the cited paper it has been shown that PMCCDC(1)=P. This result has been obtained by applying the dependency graph technique (a directed graph is associated with each P system verifying the following: there exists an accepting computation of if and only if there exists a path between two distinguished nodes in the dependency graph associated with it). From a complexity point of view, what happens if minimal cooperation is considered in communication rules? Do these systems have the ability to solve computationally hard problems in uniform polynomial-time? 4. On the presumed efficiency of CDC(2) This section is devoted to justifying the presumed efficiency of recognizer P systems with membrane division which use minimal cooperation in communication rules. In [12], an efficient solution to the SAT problem was given by using a family of systems from CDC(3). In this section, this result is improved by giving a uniform polynomial-time solution to the HAM-CYCLE problem (given a directed graph, to determine whether or not there exists a Hamiltonian cycle in the graph), a well-known NP-complete problem [2], by means of a family of systems from CDC(2). 4.1. A uniform polynomial-time solution of the HAM-CYCLE problem in CDC(2) For each m, n ∈N, being nthe number of nodes and mthe number of edges of a directed graph G, we consider the recognizer P system with symport/antiport rules and membrane division of degree 11 +2n +n3 (m,n)=(,E,,μ,Mr(1≤r≤11), Ma1,j(1≤j≤n), Ma2,j(1≤j≤n), Mei,j,k(1≤i,j,k≤n), Rr(1≤r≤11), Ra1,j(1≤j≤n), Ra2,j(1≤j≤n), Rei,j,k(1≤i,j,k≤n), iin,iout) defined as follows (parameter mis involved in the definition of some rules): –The working alphabet is: ∪E∪{b r,b r,b r,c r,c r,c r,c r|1≤r≤n3}∪ {βr|0≤r≤n3+7}∪{(i,j) k,(i,j) k|1≤i,j,k≤n}∪ {(i,j) k,r|1≤i,j,k≤n∧1≤r≤n3}∪ {α0,a,a,a,b,b,b,b,c,c,c,c,c,yes,no}, where the input alphabet is  ={(i, j)k|1 ≤i, j, k ≤n}, and the alphabet of the environment is E={αr|1 ≤r≤n3+6} – Membrane structure μ: the set of nodes is V={1,...,11}∪{a1,j,a2,j|1≤j≤n}∪{ei,j,k|1≤i,j,k≤n} The root is labelled by 1 and the remaining nodes are its children. – Initial multisets: M1={α0}∪{βr|1≤r≤n3+7}∪ {b r,b r,b r,c r,c r,c r,c r|1≤r≤n3−1}; M2={an,b,c}; M3={b n3}; M4={b n3}; M5={b n3}; M6={c n3}; M7={c n3}; M8={c n3}; M9={c n3}; M10 ={yes}; M11 ={no,β 0}; Ma1,j={a n3},Ma2,j={a n3},for 1 ≤j≤n; Mei,j,k={(i,j) k,n3},for 1 ≤i,j,k≤n. –Rules of the system: Rules in R1 –Rules to control the output of the computations by counters αr: {(αr, out ; αr+1, in) |0 ≤r≤n3+5}(1.1) –Rule to produce an affirmative answer: (yes , out)(1.2) –Rule to produce a negative answer: (no αn3+6, out)(1.3) Rules in R2 –Rules to produce all possible subsets of A Gin membranes labelled by 2 at configuration Cn3+1: {[ (i, j)k]2→[ (i, j) k]2[ # ]2|1 ≤i, j, k ≤n}(2.1) –Rules to move objects a, a, b, b, c, c, c, c and c into membranes labelled by 2 at configurations Cn3+2, Cn3+3, Cn3+4and Cn3+5, respectively. (a, out ; a, in); (a, out ; a, in) (2.2) (b , out ; b, in); (b, out ; b , in); (b , out ; b , in)(2.3) (c, out; c, in); (c, out; c, in); (c, out; c, in); (c, out; c, in)(2.4) (a b , out); (b c , out) (2.5) –Rules to produce in each membrane labelled by 2 at configuration Cn3+2a subset of A Gfrom a subset of A Gat configuration Cn3+1: {((i, j) k, out ; (i, j) k, in) |1 ≤i, j, k ≤n}(2.6) –Rules to generate in each membrane labelled by 2 at configuration Cn3+1a subset of A Gencoding a possible Hamiltonian cycle. (2.7) ⎧ ⎪ ⎪ ⎨ ⎪ ⎪ ⎩ {((i,j) k(i,j) k,out)|1≤i,i,j,j,k,k≤n}∪ {((i,j) k(i,j) k,out)|1≤i,i,j,j,k,k≤n}∪ {((i,j) k(i,j) k+1,out)|1≤i,i,j,j,k,k≤n,j= i}∪ {((i,j) k(i,j) k,out)|1≤i,i,j,j,k,k≤n} –Rules to check if the subset represented by each membrane with label 2 at configuration Cn3+3encodes a Hamiltonian cycle of the input graph: {(a (i, j) k, out) |1 ≤i, j, k ≤n}(2.8) Rules in R3 Rules to produce 2n·mcopies of object bin the skin membrane of configuration Cn3+1: {(b r, out ; b r−1, in) |n ·m +1 ≤r≤n3}(3.1) {[ b r]3→[ b r−1]3[ b r−1]3|2 ≤r≤n ·m}(3.2) [ b 1]3→[ b]3[ b]3(3.3) (b, out) (3.4) Rules in R4 Rules to produce 2n·mcopies of object b in the skin membrane at configuration Cn3+1: {(b r, out ; b r−1, in) |n ·m +1 ≤r≤n3}(4.1) {[ b r]4→[ b r−1]4[ b r−1]4|2 ≤r≤n ·m}(4.2) [ b 1]4→[ b ]4[ b ]4(4.3) (b , out) (4.4) Rules in R5 Rules to produce 2n·mcopies of object b in the skin membrane at configuration Cn3+1: {(b r, out ; b r−1, in) |n ·m +1 ≤r≤n3}(5.1) {[ b r]5→[ b r−1]5[ b r−1]5|2 ≤r≤n ·m}(5.2) [ b 1]5→[ b ]5[ b ]5(5.3) (b , out) (5.4) Rules in R6 Rules to produce 2n·mcopies of object cin the skin membrane at configuration Cn3+1: {(c r, out ; c r−1, in) |n ·m +1 ≤r≤n3}(6.1) {[ c r]6→[ c r−1]6[ c r−1]6|2 ≤r≤n ·m}(6.2) [ c 1]6→[ c]6[ c]6(6.3) (c, out) (6.4) Rules in R7 Rules to produce 2n·mcopies of object c in the skin membrane at configuration Cn3+1: {(c r, out ; c r−1, in) |n ·m +1 ≤r≤n3}(7.1) {[ c r]7→[ c r−1]7[ c r−1]7|2 ≤r≤n ·m}(7.2) [ c 1]7→[ c ]7[ c ]7; (7.3) (c , out) (7.4) Rules in R8 Rules to produce 2n·mcopies of object c in the skin membrane at configuration Cn3+1: {(c r, out ; c r−1, in) |n ·m +1 ≤r≤n3}(8.1) {[ c r]8→[ c r−1]8[ c r−1]8|2 ≤r≤n ·m}(8.2) [ c 1]8→[ c ]8[ c ]8(8.3) (c , out) (8.4) Rules in R9 Rules to produce 2n·mcopies of object c in the skin membrane at configuration Cn3+1: {(c r, out ; c r−1, in) |n ·m +1 ≤r≤n3}(9.1) {[ c r]9→[ c r−1]9[ c r−1]9|2 ≤r≤n ·m}(9.2) [ c 1]9→[ c ]9[ c ]9(9.3) (c , out) (9.4) Rules in R10 Rules to produce an affirmative answer: (αn3+6c , in) ; (c yes , out) (10.1) Rules in R11 Rules to control the negative answer of the computations by counters βr: {(βrout ; βr+1, in) |0 ≤r≤n3+6}(11.1) (βn3+7no , out) (11.2) Rules in Ra1,j,1≤j≤n Rules to produce 2n3copies of object ain the skin membrane at configuration Cn3+1: {[ a r]a1,j→[ a r−1]a1,j[ a r−1]a1,j|2 ≤r≤n3}(a1,j.1) [ a 1]a1,j→[ a]a1,j[ a]a1,j(a1,j.2) (a, out) (a1,j.3) Rules in Ra2,j,1≤j≤n Rules to produce 2n3copies of object a in the skin membrane at configuration Cn3+1: {[ a r]a2,j→[ a r−1]a2,j[ a r−1]a2,j|2 ≤r≤n3}(a2,j.1) [ a 1]a2,j→[ a ]a2,j[ a ]a2,j(a2,j.2) (a , out) (a2,j.3) Rules in Rei,j,k,1≤i,j,k≤n Rules to produce 2n3copies of object (i, j) kin the skin membrane at configuration Cn3+1: {[(i, j) k,r]ei,j,k→[(i, j) k,r−1]ei,j,k[(i, j) k,r−1]ei,j,k| 2 ≤r≤n3}(ei,j,k.1) [ (i, j) k,1]ei,j,k→[ (i, j) k]ei,j,k[ (i, j) k]ei,j,k(ei,j,k.2) ((i, j) k, out) (ei,j,k.3) (5) The input membrane is the membrane labelled by 2 and the output region is the environment of the system (labelled by 0). According with the previous description, for each m, n ∈Nthe recognizer P system (m, n)is in the class CDC(2). In the next subsection, we will give an overview how each system (m, n)will process all directed graphs with nnodes and marcs. 4.2. An overview of the computations We consider the polynomial encoding (cod, s)from HAM-CYCLE to defined as follows: cod(G) ={(i, j)k|(i, j) ∈E, 1 ≤ k ≤n}and s(G) =m, n, for each instance G =({1, ..., n}, {(i1, j1), ..., (im, jm)}). The expression (i, j)kin cod(G)can be interpreted as follows: arc (i, j)is “placed” in “position k” in a potential path of G. According to this encoding, graph Gwill be processed by system (s(G)) +cod(G). In what follows, we informally describe how system (s(G)) +cod(G)works. The solution proposed implements the following stages: •Generation Stage: All possible combinations of arcs from the input graph, including a code of their position in potential paths, are generated by using cell division in an adequate way. •Checking Stage: It is checked whether or not the different combinations of arcs generated in the previous stage encode Hamiltonian cycles of the input graph. •Output Stage: The system sends the right answer to the environment according to the results obtained in the previous stage. Generation stage At this stage, the system generates all the possible subsets of arcs of the graph (in fact, subsets of A G) which contain their potential positions in a path according to the notations introduced in Subsection 2.2. In this way, by applying rules of type 2.1 at configuration Cn3, there will be 2n·mmembranes labelled by 2 such that each of them encodes a different combination of arcs from the input graph. For this, rules from R2produce two new membranes for each object (i, j)k: one containing its primed version, and other one not containing it. It produces that each membrane labelled by 2 will contain a different subset of A G, and therefore a different path if it is correct. Simultaneously, by applying rules of types 1, 2 and 3 from R3, R4, R5, R6, R7, R8and R9, 2n·mcopies of objects b, b, b, c, c, c and c are produced in membranes labelled by 3, 4, 5, 6, 7, 8, 9, respectively, and 2n3copies of objects a, a and (i, j) kare produced in membranes labelled by a1,j, a2,j, and ei,j,k, respectively. The generation stage takes n3steps. Proposition 4.1. Let C=(C0, C1, ..., Cq)be a computation of the system (s(G)) +cod(G). Then at configuration Cn3, the following holds: 1. There are 2n·mmembranes labelled by 2 such that each of them contains a different subset of A G={(i, j) k|1 ≤i, j, k ≤n, (i, j) ∈ E}as well as object b, object cand n copies of object a. 2. There are 2n·mmembranes labelled by 3(respectively, by 4, 5, 6, 7, 8, 9) such each of them only contains object b(respectively, b, b, c, c, c and c). 3. For each i, j, k(1 ≤i, j, k ≤n)there are 2n3membranes labelled by ei,j,k, each of them only containing object (i, j) k. 4. For each j(1 ≤j ≤n)there are 2n3membranes labelled by a1,j, each of them only containing object a, and there are 2n3 membranes labelled by a2,j, each of them only containing object a. 5. There is a membrane labelled by 10 and a membrane labelled by 11 such that Cn3(10) ={yes}, Cn3(11) ={no ,β n3}. 6. The contents of the skin membrane, labelled by 1, is Cn3(1)={αn3,β 0,...,  βn3,...,β n3+7,b 1,...b n3−1,b 1,...b n3−1,b 1,...b n3−1, c 1,...c n3−1,c 1,...c n3−1,c 1,...c n3−1,c 1,...c n3−1}. Checking stage This stage takes 5steps. At this stage, the system checks whether or not there exists a membrane labelled by 2at configuration Cn3+5which contains a subset of A Gthat encodes a Hamiltonian cycle of G. At step n3+1, the contents of membranes labelled by 3, 4, 5, 6, 7, 8, 9, a1,j(1 ≤j ≤n), a2,j(1 ≤j ≤n)and ei,j,k(1 ≤ i, j, k ≤n)are sent to the skin membrane by applying rules 3.4, 4.4, 5.4, 6.4, 7.4, 8.4, 9.4, a1,j.2, a2,j.2, ei,j,k.3. From this moment on, these membranes do not participate in the evolution of the configurations. Proposition 4.2. Let C=(C0, C1, ..., Cq)be a computation of the system (s(G)) +cod(G). Then, omitting the empty membranes, at configuration in Cn3+1we have the following: 1. There are 2n·mmembranes labelled by 2such that each of them contains a different subset of A G={(i, j) k|1 ≤i, j ≤m, 1 ≤k ≤ n, (i, j) ∈E}as well as object b, object cand n copies of object a. 2. There is a membrane labelled by 10 and a membrane labelled by 11 such that Cn3+1(10) ={yes}, Cn3+1(11) ={no ,β n3+1}. 3. The skin membrane, labelled by 1, contains 2n3copies of each of the following objects: (i, j) k, (i, j) k(1 ≤i, j, k ≤n), a, a, b, b, b, c, c, c, c; also, it contains the following set of objects: {αn3,β 0,..., βn3+1,...,β n3+7,b 1,...b n3−1,b 1,...b n3−1,b 1,...b n3−1, c 1,...c n3−1,c 1,...c n3−1,c 1,...c n3−1,c 1,...c n3−1}. At step n3+2, objects a, b, cin membrane labelled by 2 at configuration Cn3+1are substituted by objects a, b, cfrom the skin membrane by applying rules 2.2,2.3, and 2.4. Simultaneously, by applying rules 2.6, each subset of A Gcontained in a membrane labelled by 2 at configuration Cn3+1produces the “corresponding” subset of A G. Besides, Cn3+2(10) ={yes} and Cn3+2(11) ={βn3+2, no}. At step n3+3, by applying rules 2.3 and 2.4, objects a, b, cin membranes labelled by 2 at configuration Cn3+2are substituted by objects a, b, c from the skin membrane, and simultaneously by applying rules of type 2.7 each subset contained in a membrane labelled by 2 at configuration Cn3+2is transformed into a subset encoding all possible paths in the input graph. In this manner, according to Proposition 2.1, we have that the input graph (with nnodes and marcs) has a Hamiltonian cycle if and only if at configuration Cn3+3, there exists some membrane labelled by 2 at configuration Cn3+3 such that the subset of A Gcontained in it has size equal to n. Besides, Cn3+3(10) ={yes}and Cn3+3(11) ={βn3+3, no}. At step n3+4, by applying rules 2.3 and 2.4, objects b, c in membranes labelled by 2 are substituted by objects b, c from the skin membrane, and simultaneously by applying rules 2.8 each object contained in the subset associated to each membrane labelled by 2 at configuration Cn3+3, is sent to the skin membrane cooperating with object a. Then, the number of copies of object a appearing in a membrane labelled by 2 at configuration Cn3+4is equal to n −γ, where γis the size of the path in the input graph encoded by that membrane. Then, the input graph (with nnodes and marcs) has a Hamiltonian cycle if and only if there exists a membrane labelled by 2 at configuration Cn3+4such that it does not contain any object a. At step n3+5, by applying rules of type 2.5, objects a and b in membrane labelled by 2 at configuration Cn3+5are sent to the skin membrane and, simultaneously, rule (c , out ; c , in)produces an object c in each membrane labelled by 2 at configuration Cn3+5. Hence, we can deduce the following proposition. Proposition 4.3. Let C=(C0, C1, ..., Cq)be a computation of the system (s(G)) +cod(G). Then, the input graph has a Hamiltonian cycle if and only if there exists a membrane labelled by 2 at configuration Cn3+5such that it contains an object b. Besides, Cn3+5(10) = {yes}and Cn3+5(11) ={βn3+5, no}. Output stage Finally, the output stage takes 3steps. Only membranes labelled by 2 at configuration Cn3+5which contain some object b (that is, membrane encoding a Hamiltonian cycle) can evolve and only rule (c , out ; c , in) ∈R2is applicable to that membrane. In this case, an object c will appear in each membrane labelled by 2 at that configuration. Furthermore, if a membrane with label 2 at the mentioned configuration does not encode a Hamiltonian cycle of the input graph, then it contains objects b, so the rule (a b , out) ∈R2will be applied. That is, the input graph has a Hamiltonian cycle if and only if some object c appears in the skin membrane at configuration Cn3+6. Besides, Cn3+6(10) ={yes}and Cn3+6(11) = {βn3+6, no}. If the input graph has a Hamiltonian cycle, then only rules (αn3+6c , in) ∈R10 and (βn3+6, out ; βn3+7, in) ∈R11 are applicable to configuration Cn3+6. Otherwise, only rule (βn3+6out ; βn3+7, in)is applicable to that configuration. So, the answer to the problem is affirmative if and only if Cn3+7(10) ={αn3+6c , yes}. Besides, in any case, Cn3+7(11) ={βn3+7, no}. Then, if there exists a Hamiltonian path then rules (c yes , out) ∈R10 and (βn3+7no , out) ∈R11 are applicable to configuration Cn3+7. Otherwise, only rule (βn3+7no , out) ∈R11 is applicable to that configuration. Hence, the answer to the problem is affirmative if and only if the skin membrane at configuration Cn3+8contains object yes (together with objects c, βn3+7, no) but no object αn3+6. Otherwise, the skin membrane at configuration Cn3+8contains objects βn3+7, no, αn3+6 but no object yes. At the last step, in case of an affirmative answer, rule (yes , out)is applied to configuration Cn3+8producing an object yes in the environment and the computation halts. Otherwise, rule (no αn3+6, out)is applied to that configuration producing a negative answer. Remark. When we provide a polynomial-time solution for an NP-hard problem by means of a family of recognizer membrane system, we are trading space for time, that is, an exponential number of membranes and/or objects are used along the computations. Let us notice that in the solution for the HAM-CYCLE problem, the maximum number of membranes used in any configuration is (2n +n3) ·2n3+8 ·2n·m+3, and the maximum number of objects used in any configuration is (2n +n3) ·2n3+(n +10) ·2n·m+8n3+3. 4.3. Main result Theorem 4.4. HAM-CYCLE ∈PMCCDC(2).