Cell-like P systems with evolutional symport/antiport rules and membrane creation

Cell-like P systems with evolutional symport/antiport rules and membrane creation ✩ Bosheng Song a,∗, Kenli Li a, David Orellana-Martín b, Luis Valencia-Cabrera b, Mario J. Pérez-Jiménez b a College of Information Science and Engineering, Hunan University, and the National Supercomputing Center in Changsha, 410082, Hunan, China b 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: Bio-inspired computing Membrane computing Cell-like P system Evolutional symport/antiport rule Membrane creation Cell-like P systems with symport/antiport rules are computing models inspired by the conservation law, in the sense that they compute by changing the places of objects with respect to the membranes, and not by changing the objects themselves. In this work, a variant of these kinds of membrane systems, called cell-like P systems with evolutional symport/antiport rules, where objects can evolve in the execution of such rules, is introduced. Besides, inspired by the autopoiesis process (ability of a system to maintain itself), membrane creation rules are considered as an efficient mechanism to provide an exponential workspace in terms of membranes. The presumed efficiency of these computing models (ability to solve computationally hard problems in polynomial time and uniform way) is explored. Specifically, an efficient solution to the SAT problem is provided by means of a family of recognizer cell-like P systems with evolutional symport/antiport rules and membrane creation which make use of communication rules involving a restricted number of objects. 1. Introduction Membrane Computing is a computational paradigm 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 [29]. The computing models in this paradigm are the so-called P systems or membrane systems. In this framework, three main approaches have been widely studied: cell-like P systems, organized with a hierarchical (cell-like) arrangement of membranes (a rooted tree), simulating the organization within a cell [29]; tissue-like P systems, inspired by the cell-interconnection communication between cells in a living tissue [22,32]; and neural-like P systems, inspired from the way that neurons communicate with each other by means of short electrical impulses (spikes), emitted at precise moments of time [18,19]. ✩The work of B. Song was supported by National Natural Science Foundation of China (61972138, 61602192), the Fundamental Research Funds for the Central Universities (531118010355). The work of D. Orellana-Martín, L. Valencia-Cabrera and M.J. Pérez-Jiménez is supported by the research project TIN2017-89842-P, cofinanced by Ministerio de Economía, Industria y Competitividad (MINECO) of Spain, through the Agencia Estatal de Investigación (AEI), and by Fondo Europeo de Desarrollo Regional (FEDER) of the European Union. *Corresponding author. E-mail addresses: [email protected] (B. Song), [email protected] (K. Li), [email protected] (D. Orellana-Martín), lv[email protected] (L. Valencia-Cabrera), [email protected] (M.J. Pérez-Jiménez). The basic ingredient of cell-like P systems is the membrane structure, which is a hierarchical arrangement of membranes embedded in a unique main membrane, called the skin membrane [29,30,33]. Each membrane delimits a region (also called compartment), where finite sets of symbols (corresponding to the chemicals), finite sets of evolution rules (describing the possible interactions between chemicals) and other membranes can be placed. The outside region of the skin membrane is called environment, where there are no rules placed in it. If a membrane does not contain other membranes, then it is called elementary membrane; otherwise, it is called non-elementary membrane. In terms of types of rules, two main approaches have been investigated. On the one hand, rewriting rules are used as a method to make the objects of a system to evolve and move them through the compartments of itself. P systems with active membranes are a framework where these kinds of rules have defined several frontiers of efficiency in the framework of Membrane Computing. On the other hand, symport/antiport rules can be seen as an abstraction of the movement of chemical compounds between different compartments of a system [6,7,27,28], let it be a single cell or a living tissue. In fact, as it happens in living systems, this communication is not limited to the compartments of the system, but they can interact with the environment too. Membrane division and membrane separation are inspired by the mitosis and the membrane fission processes, which provide a mechanism to generate an exponential workspace in linear time. With the help of this mechanism, various P systems have manifested an excellent performance with respect to address computationally hard problems, including NPcomplete problems [10,11,32,36,44], PSPACE-complete problems [2–4,45,46]. Membrane creation is another mechanism to produce new membranes, which was first considered in [23], inspired from the fact that when a membrane compartment becomes too large, new membranes often appear inside it. Membrane creation differs from membrane division and membrane separation, since no new membranes with new labels are created by means of the execution of a division rule or a separation rule, they only duplicate membranes while maintaining their labels. While using creation rules, we have to take care of how many labels will be used and where can they be used. As expected, P systems with membrane creation can solve NP-complete problem (subset sum) [15], even PSPACE-complete problem (QSAT) [16]in a polynomial time. In [43], this last approach was extended to tissue P systems in such a way that, while classical symport/antiport rules only transport objects between the different compartments [1,5,8,12], evolutional symport/antiport rules are capable of modifying them while they travel to a different compartment. As a new methodology to tackle the Pversus NP problem [13,14,20,21], new frontiers between the non efficiency (only problems in class Pcan be efficiently solved) and the presumed efficiency (ability to solve computationally hard problems in polynomial time and uniform way) have been reached by means of these kinds of membrane systems. While using division rules, passing from rules of length at most (1, n)to (2, n)(the length of an evolutional symport/antiport rule is an ordered pair whose first component is the total number of objects involved in the left hand side of the rule, and the second component is the total number of objects involved in the right hand side of the rule), for every natural number n ≥1, amounts to passing from the non efficiency to the presumed efficiency. If separation rules are used instead of division rules, the non efficiency of tissue P systems with evolutional symport/antiport rules of length at most (1, n)or (n, 1), for every natural number n ≥1, has been established in [25]. In this work, we apply evolutional symport/antiport rules in cell-like P systems, and using membrane creation rules as a mechanism to construct an exponential workspace in terms of membranes in polynomial time. More precisely, an efficient solution to the SAT problem is provided by means of a family of recognizer cell-like P systems with evolutional symport/antiport rules and membrane creation which make use of communication rules involving the left-hand side (LHS) of length at most 2 and the right-hand side (RHS) of length at most 2. We emphasize the following facts that in [17], the SAT problem was solved by P systems with membrane creation using rules of length at most (1, 2), where object evolution rules, communication rules, creation rules and dissolution rules are applied; however, in this work, the SAT problem can be efficiently solved by P systems with evolutional symport/antiport rules and membrane creation using rules of length at most (2, 2), where evolutional communication rules and creation rules are used. Although to a certain extent, evolutional communication rules, evolution rules and communication rules can mutual transform, “dissolution rules” are a very power tool to achieve the desired computational power as described in [14,17], it is shown that dissolution rules provide a borderline between efficiency and non-efficiency for P systems with membrane creation, that is, P systems with membrane creation without dissolution rules characterize standard class P[14]. In the present work, dissolution rules are not allowed for P systems with evolutional symport/antiport rules and membrane creation, and we show that NP-complete problem can be efficiently solved by such kind of P systems. Moreover, in P systems with membrane creation, all rules are noncooperative, that is, the length of left-hand side of rules is at most 1; however, in P systems with evolutional symport/antiport rules and membrane creation, the length of left-hand side of rules can be arbitrary. Hence there exist essential differences between P systems with membrane creation and P systems with evolutional symport/antiport rules and membrane creation. The paper is organized as follows. In the next section, some notations and the computing model of cell-like P system with evolutional symport/antiport rules and membrane creation are presented. In section 3, the result about the computational efficiency of cell-like P systems with evolutional symport/antiport rules and membrane creation is demonstrated. Finally, some conclusions and open problems are presented. 2. Preliminaries and model description Some basic notions used in this work from formal language theory are recalled, one is referred to [33,37]for further information. An alphabet is denoted by , which is a non-empty set, and the elements in are called symbols. A string u over is a finite sequence of symbols from , and the length of the string u(denoted by |u|) from is the number of occurrences in uof symbols. For an alphabet , a multiset over is a pair (, f)where f: →Nis a mapping, Nis the set of natural numbers. Let m1, m2be multisets over . The union of m1and m2, denoted by m1+m2, is the multiset over  defined as (m1+m2)(x) =m1(x) +m2(x)for each x ∈. The relative complement of m2in m1, denoted by m1\m2, is the multiset defined as (m1\m2)(x) =m1(x) −m2(x)if m1(x) ≥m2(x), and (m1\m2)(x) =0otherwise. We denote by ∅the empty multiset and by Mf()the set of all finite multisets over . Next we give the definition of cell-like P systems with evolutional symport/antiport rules and membrane creation. Definition 1. A cell-like P system with evolutional symport/antiport rules and membrane creation of degree q ≥1is a tuple =(,E,H,μ,M1,...,Mq,R,iout), where •is a finite alphabet of objects; •Eis a finite alphabet of objects initially placed in the environment (note that each object initially placed in the environment is available in an arbitrary number of copies), such that E⊆; •His a finite alphabet such that {0, 1, ..., q} ⊆H(the environment is identified by the label 0); •μis a membrane structure (a rooted tree) whose nodes are bijectively labelled with 1, ..., q(the root of the tree is labelled by 1); •Mi, 1 ≤i ≤q, are finite multisets over  \E; •Ris a finite set of rules of the following forms: – Evolutional symport rules: –Among membranes: [ u[ ]i]j→[ [ u]i]j, where i, j ∈H, i = j, u, u∈Mf(), |u| >0 (send-in rules); [ [ u]i]j→[ u[ ]i]j, where i, j ∈H, i = j, u, u∈Mf(), |u| >0(send-out rules); – Between the root and the environment: [ u[ ]1]0→[ [ u]1]0, where u, u∈Mf(), |u| >0, and there exists at least one object a ∈u, such that a ∈ \E(send-in rules); [ [ u]1]0→[ u[ ]1]0, where u, u∈Mf(), |u| >0(send-out rules); – Evolutional antiport rules: [ u[ v]i]j→[ v[ u]i]j, where i, j ∈H∪{0}, i = j, u, v, u, v∈Mf(), |u| >0, |v| >0; –Creation rules: [ a →[ u]i]j, where i, j ∈H, i = j, a ∈, u ∈Mf(); •iout is the output region. A configuration Ctat an instant tof cell-like P system with evolutional symport/antiport rules and membrane creation at any moment is described by the current membrane structure, together with all multisets of objects over associated with the regions of this membrane structure and the multiset of objects over  \Eassociated with the environment at that moment. An evolutional send-in rule [ u[ ]i]j→[ [ u]i]jis applicable to a configuration Ctif there exists a region ifrom Ctwhose parent membrane, labelled by j, contains multiset u. When applying such a rule, the multiset of objects u in region jis consumed and the multiset of objects uis produced in region ifrom Ct+1. An evolutional sent-out rule [ [ u]i]j→[ u[ ]i]jis applicable to a configuration Ctif there is a region ifrom Ctwhich contains multiset uand the parent of iis labelled by j. When applying such a rule, the multiset of objects uin region ifrom Ctis consumed and the multiset of objects uis generated in region jfrom Ct+1. An evolutional antiport rule [ u[ v]i]j→[ v[ u]i]jis applicable to a configuration Ctif there exists a membrane ifrom Ctwhich contains multiset v, whose parent region is labelled by jand contains multiset u. When applying such a rule, the multiset of objects vin membrane iand the multiset of objects uin region jare consumed; simultaneously, the multiset of objects uis produced in membrane ifrom Ct+1and the multiset of objects vis produced in region j. A creation rule [ a →[ u]i]jis applicable to a configuration Ctif there exists a membrane jfrom Ctwhich contains object a. When applying such a rule, under the influence of object a, a new membrane with label ihaving inside the multiset u, is created in such manner that it will be a daughter of the membrane with label j. Following the definition in [25], in this work, we denote by CCEC(k1, k2)(k1, k2are natural numbers, and k1≥1, k2≥1) the class of cell-like P systems with evolutional symport/antiport rules and membrane creation which makes use of evolutional communication rules such that the total number of objects involved in the LHS is at most k1and the total number of objects involved in the RHS is at most k2. The rules of a cell-like P system with evolutional symport/antiport rules and membrane creation are used in the following manner: at each step, a maximal multiset of rules is applied (no further rule can be added being applicable) with the following restriction: when a creation rule is applied to a membrane j, this rule is the only one which is applied for that membrane at that step, that is, the objects inside that membrane do not evolve by means of communication rules. The objects in the new membranes resulting from creation could participate in the interaction with the objects in the (upper or lower) neighbor of membranes by means of communication rules at the next step. The transition of system is defined by transferring from a configuration to a next configuration. The computation of  over the initial configuration is a finite or infinite sequence of transitions. When system runs to a configuration where no rule of the system is applicable in this configuration, the system is said to run to the halting configuration. Only a computation reaching a halting configuration gives a result, which is encoded by the specific objects present in the output region iout. In order to solve decision problems, a recognizer cell-like P system with evolutional symport/antiport rules and membrane creation is given. Definition 2. A recognizer cell-like P system with evolutional symport/antiport rules and membrane creation of degree q ≥1 is a tuple =(,E,,H,μ,M1,...,Mq,R,iin,iout), where •(, E, H, μ, M1, ..., Mq, R, iout)is a cell-like P system with evolutional symport/antiport rules and membrane creation of degree m ≥1, such that has two distinguished objects yes and no, M1, ..., Mqare finite multisets over  \; •is an input alphabet strictly contained in ; •iin ∈{1, ..., q}is the input membrane, and iout =0; •all computations halt; •for each computation of , either object yes or object no (but not both) is released into the environment, at the last step of the computation. We denote by CCEC(k1, k2)the class of all recognizer cell-like P system with evolutional symport/antiport rules and membrane creation such that the total number of objects involved in the LHS of the evolutional communication rules is at most k1and the total number of objects involved in the RHS of the evolutional communication rule is at most k2. Next, following [34,35], the concept of solving a decision problem in a uniform way and polynomial time by means of a family of recognizer membrane systems, is defined. Definition 3. A decision problem X=(IX, θX)is solvable in polynomial time and uniform way by a family  ={(n) |n ∈ N}of membrane systems from CCEC(k1, k2)if the following conditions hold: •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)from n ∈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)); we denote by (s(u)) +cod(u)the system obtained by adding cod(u)to the multiset in the region iin of (s(u)); –for each n ∈N, s−1(n)is a finite set; –the family is polynomially bounded with regard to (X, cod, s), that is, there exists a polynomial function p, such that for each u ∈IXevery computation of (s(u)) with input cod(u)is halting and it performs at most p(|u|)steps; –the family is sound with regard to (X, cod, s), that is, for each u ∈IX, if there exists an accepting computation of (s(u)) with input cod(u), then θX(u) =1; –the family is complete with regard to (X, cod, s), that is, for each u ∈IX, if θX(u) =1, then every computation of (s(u)) with input cod(u)is an accepting one. We denote by PMCCCEC(k1,k2)the set of all decision problems which can be solved in a uniform way and polynomial time by means of recognizer cell-like P system with evolutional symport/antiport rules and membrane creation, where the evolutional communication rules of length at most (k1, k2). 3. An efficient solution to the SAT problem in CCEC(2, 2) In this section the presumed efficiency of CCEC(2, 2)is established, by providing a polynomial-time uniform solution to the SAT problem (one is referred to [24]for the detail of the SAT problem) by means of a family of membrane systems  ={(t) |t∈N}from CCEC(2, 2). For each pair of natural numbers n, p ∈N, we consider the recognizer tissue P system from CCEC(2, 2), (n, p) = (, E, , H, μ, M1, ..., Mq, R, iin, iout), defined as follows: •The working alphabet: =∪{xi,j,t,xi,j,f,¯ xi,j,t,¯ xi,j,f|1≤i≤n,1≤j≤p}∪ {ai,t,ai,f|1≤i≤n+1}∪{cj,t,c j,t,cj,f,cj,Ej,E j|1≤j≤p}∪ {αi,α i|0≤i≤4n+2p+5}∪{a1,b,Ep+1,t,yes,no}. •The input alphabet:  ={xi,j, ¯ xi,j|1 ≤i ≤n, 1 ≤j ≤p}. •The environment alphabet: E={α i|0 ≤i ≤4n +2p +4}. •The set of labels: H={lt, lf |1 ≤l ≤n} ∪{0, 1, 2, n +1}. •The membrane structure: μ =[ [ ]2]1. •The initial multisets: M1={a1, b, α0}, M2=∅. •iin =1is the input membrane. •iout =0is the output region. •The set Rconsists of the following rules: –Rules to generate the 2npossible truth assignments: r1≡[ a1[ ]2]1→[ [ a1]2]1, r2,i,j≡[ xi,j[ ]2]1→[ [ xi,j]2]1, 1 ≤i ≤n, 1 ≤j ≤p, r3,i,j≡[ ¯ xi,j[ ]2]1→[ [ ¯ xi,j]2]1, 1 ≤i ≤n, 1 ≤j ≤p, r4≡[ [ a1]2]1→[ a1,ta1,f[ ]2]1, r5,i,j≡[ [ xi,j]2]1→[ xi,j,txi,j,f[ ]2]1, 1 ≤i ≤n, 1 ≤j ≤p, r6,i,j≡[ [ ¯ xi,j]2]1→[ ¯ xi,j,t¯ xi,j,f[ ]2]1, 1 ≤i ≤n, 1 ≤j ≤p, r7≡[ a1,t→[ a2,ta2,f]1t]1, r8≡[ a1,f→[ a2,ta2,f]1f]1, r9,i,l≡[ ai+1,t→[ ai+2,tai+2,f](i+1)t]il, 1 ≤i ≤n −1, l =t, f, r10,i,l≡[ ai+1,f→[ ai+2,tai+2,f](i+1)f]il, 1 ≤i ≤n −1, l =t, f, r11,j≡[ x1,j,t[ ]1t]1→[ [ cj,tcj,f]1t]1, 1 ≤j ≤p, r12,j≡[ ¯ x1,j,t[ ]1t]1→[ [ λ]1t]1, 1 ≤j ≤p, r13,i,j≡[ xi,j,t[ ]1t]1→[ [ xi,j,txi,j,f]1t]1, 2 ≤i ≤n, 1 ≤j ≤p, r14,i,j≡[ ¯ xi,j,t[ ]1t]1→[ [ ¯ xi,j,t¯ xi,j,f]1t]1, 2 ≤i ≤n, 1 ≤j ≤p, r15,j≡[ x1,j,f[ ]1f]1→[ [ λ]1f]1, 1 ≤j ≤p, r16,j≡[ ¯ x1,j,f[ ]1f]1→[ [ cj,tcj,f]1f]1, 1 ≤j ≤p, r17,i,j≡[ xi,j,f[ ]1f]1→[ [ xi,j,txi,j,f]1f]1, 2 ≤i ≤n, 1 ≤j ≤p, r18,i,j≡[ ¯ xi,j,f[ ]1f]1→[ [ ¯ xi,j,t¯ xi,j,f]1f]1, 2 ≤i ≤n, 1 ≤j ≤p, r19,i,j,l≡[ cj,t[ ](i+1)t]il →[ [ cj,tcj,f](i+1)t]il, 1 ≤i ≤n −1, 1 ≤j ≤p, l =t, f, r20,i,j,l≡[ cj,f[ ](i+1)f]il →[ [ cj,tcj,f](i+1)f]il, 1 ≤i ≤n −1, 1 ≤j ≤p, l =t, f, r21,i,j,l≡[ xi+1,j,t[ ](i+1)t]il →[ [ cj,tcj,f](i+1)t]il, 1 ≤i ≤n −1, 1 ≤j ≤p, l =t, f, r22,i,j,l≡[ ¯ xi+1,j,t[ ](i+1)t]il →[ [ λ](i+1)t]il, 1 ≤i ≤n −1, 1 ≤j ≤p, l =t, f, r23,i,j,l≡[ xi+1,j,f[ ](i+1)f]il →[ [ λ](i+1)f]il, 1 ≤i ≤n −1, 1 ≤j ≤p, l =t, f, r24,i,j,l≡[ ¯ xi+1,j,f[ ](i+1)f]il →[ [ cj,tcj,f](i+1)f]il, 1 ≤i ≤n −1, 1 ≤j ≤p, l =t, f, r25,i,j,k,l≡[ xk,j,t[ ](i+1)t]il →[ [ xk,j,txk,j,f](i+1)t]il, 1 ≤i ≤n −2, 1 ≤j ≤p, i +2 ≤k ≤n, l =t, f, r26,i,j,k,l≡[ ¯ xk,j,t[ ](i+1)t]il →[ [ ¯ xk,j,t¯ xk,j,f](i+1)t]il, 1 ≤i ≤n −2, 1 ≤j ≤p, i +2 ≤k ≤n, l =t, f, r27,i,j,k,l≡[ xk,j,f[ ](i+1)f]il →[ [ xk,j,txk,j,f](i+1)f]il, 1 ≤i ≤n −2, 1 ≤j ≤p, i +2 ≤k ≤n, l =t, f, r28,i,j,k,l≡[ ¯ xk,j,f[ ](i+1)f]il →[ [ ¯ xk,j,t¯ xk,j,f](i+1)f]il, 1 ≤i ≤n −2, 1 ≤j ≤p, i +2 ≤k ≤n, l =t, f, r29,l≡[ an+1,t→[ E1]n+1]nl, l =t, f. –Rules to check if a given truth assignment makes true the input formula ϕ: r30,j,l≡[ cj,t[ ]n+1]nl →[ [ c j,t]n+1]nl, 1 ≤j ≤p, l =t, f, r31,j,l≡[ [ c j,t]n+1]nl →[ cj[ ]n+1]nl , 1 ≤j ≤p, l =t, f, r32,j,l≡[ cj[ Ej]n+1]nl →[ E j[ ]n+1]nl, 1 ≤j ≤p, l =t, f, r33,j,l≡[ E j[ ]n+1]nl →[ [ Ej+1]n+1]nl, 1 ≤j ≤p, l =t, f. –Rules to return the correct answer: r34,l≡[ [ Ep+1]n+1]nl →[ t[ ]n+1]nl, l =t, f, r35,i,l,l≡[ [ t]il](i−1)l→[ t[ ]il](i−1)l, 2 ≤i ≤n, l =t, f, l=t, f, r36,l≡[ [ t]1l]1→[ t[ ]1l]1, l =t, f, r37 ≡[ [ bt ]1]0→[ yes[ ]1]0, r38,i≡[ α i[ αi]1]0→[ [ αi+1]1]0, 0 ≤i ≤4n +2p +4, r39 ≡[ [ bα4n+2p+5]1]0→[ no[ ]1]0. 3.1. An overview of the computation Let us consider the polynomial encoding (cod, s)of the SAT problem in the family defined as follows: for each Boolean formula in CNF and simplified form with nvariables and pclauses, ϕ=C1∨···∨Cp, where Cj=lj 1∧···∧lj mj, 1 ≤j ≤pand 1 1t21f 2t2f2t2f . . . . . . . . . (n−1)t(n−1)f nt nf nt nf n+1n+1n+1n+1 ··· ··· ··· Fig. 1. The membrane structure of the system when the generation stage completes. Numbers at nodes indicate labels of membranes. lj r∈{xi, ¬xi}, 1 ≤i ≤n, 1 ≤r≤mj, we define s(ϕ) =n, pand cod(ϕ) ={xi,j|xi∈Cj} ∪{xi,j|¬xi∈Cj}. Then, the system (s(ϕ)) with input multiset cod(ϕ)(denoted by (s(ϕ)) +cod(ϕ)) will process the formula ϕ, and (s(ϕ)) ∈CCEC(2, 2). The system (s(ϕ)) +cod(ϕ)has been designed following a brute-force algorithm and it consists on the following stages: (a) Generation stage: by using creation rules all truth assignments associated with the set of variables {x1, ..., xn}will be generated and, simultaneously, the clauses satisfied for each truth assignment are checked. (b) Checking stage: truth assignment satisfying all clause of ϕare checked. (c) Output stage: the system sends to the environment an object yes or an object no at the last step of the computation depending on if the formula ϕis or not satisfiable, according to the previous stage. Next, an exhaustive description of each stage is given. Generation stage In this stage, by using membrane creation rules, a binary tree structure with 2nleaves is produced, all truth assignments for the variables associated with ϕ(x1, ..., xn)will be generated (corresponding to the labels of membranes). During this process, the clauses that are satisfied by the corresponding truth assignment are checked. In this way, after completing this stage, there are some of the objects c1,t, c1,f, c2,t, c2,f, ..., cp,t, cp,fin a membrane with label nt or nf , which correspond to the clauses satisfied by the truth assignment. Besides, object αiin membrane 1 is evolved to count the number of steps. In the initial configuration of the system, we have objects a1, b, α0, cod(ϕ)in membrane 1, objects α i(0 ≤i ≤4n +2p +4) in the environment. The processes of assigning truth-assignment of variable xias well as looking for the clauses satisfied by the truthassignment of variable xiare described as follows. Note that from step 1 to step 4n +2p +5, the count object αiis evolved in each step in membrane 1; that is, the subscript of αiis increased by one for each step. At step 1, rule r1is used, object a1is sent into membrane 2; simultaneously, all the input objects cod(ϕ)are sent into membrane 2 by using rules r2,i,j, r3,i,j. At step 2, rules r4, r5,i,j, r6,i,jare enabled and applied, all objects a1, xi,j, ¯ xi,jin membrane 2 are sent to membrane 1 and evolved to a1,ta1,f, xi,j,txi,j,f, ¯ xi,j,t¯ xi,j,f, respectively. With object a1,t(resp., a1,f) appears in membrane 1, rule r7(resp., r8) is applied, object a1,t(resp., a1,f) creates a membrane with label 1t(resp., 1f), where objects a2,t, a2,fare placed. From step 3, rules from r9,i,lto r29,lare selected in a non-deterministic way as follows: as no communication rules can be applied to a membrane that will generate a new membrane within it in the next configuration, then three sets of rules can be applied to a single membrane in a given step: (a) rule r9,i,l, that creates a new membrane labelled by (i +1)tand two new objects ai+2,t, ai+2,fwithin it by consuming one object ai+1,tor rule r29,lto create a membrane labelled by n +1with an object E1to start the next stage; (b) rule r10,i,l, that creates a new membrane labelled by (i +1)fand two new objects ai+2,t, ai+2,fwithin it by consuming one object ai+1,f; and (c) rules r11,j, r12,j, r15,j, r16,j, r21,i,j,l, r22,i,j,l, r23,i,j,l, r24,i,j,l, devoted to check whether a given truth assignment makes a literal satisfy its clause, r13,i,j, r14,i,j, r17,i,j, r18,i,j, r25,i,j,k,l, r26,i,j,k,l, r27,i,j,k,l, r28,i,j,k,l, devoted to move literals from the parent membrane to a child membrane, r19,i,j,l, r20,i,j,l, devoted to duplicate objects cjto send them to the inner membranes. Hence, after 3n +3the generation stage completes, a binary tree structure with 2nleaves is produced (see Fig. 1), where each membrane with label n +1 contains an object E1, each membrane with label nt or nf contains some objects from the set {c1,t, c1,f, c2,t, c2,f, ..., cp,t, cp,f}. Checking stage. When the generation stage completes, the system has 2ncopies of membrane nt or nf , and each of these membranes contains a membrane n +1 and some objects from the set {c1,t, c1,f, c2,t, c2,f, ..., cp,t, cp,f}, which correspond to clauses satisfied by the truth assignment of the variables (note that objects cj,t, cj,fappear in pairs). If there exists at least one membrane nt or nf that contains all the objects c1,t, c2,t, ..., cp,t, then the formula ϕis satisfied by the corresponding truth assignment in that membrane; if there is no membrane nt or nf that contains all the objects c1,t, c2,t, ..., cp,t, then the formula ϕis not satisfied. The checking stage takes 2p +2steps, which consists of a loop with piterations, each iteration takes two steps, and two addition steps. By using rules r30,j,l, r31,j,l, all the objects cj,t(1 ≤j ≤p) evolve to cj. At the first step of the j-th loop (1 ≤j ≤p), rule r32,j,lis enabled if and only if membrane nt or nf encodes a truth assignment making clauses C1, ..., Cjtrue. We remark that for any membrane nt or nf , if it contains a truth assignment that does not make the clause Cjtrue, then the computation will halt in that membrane. By using rule r32,j,l, object cjis sent into membrane n +1 and consumed; simultaneously, object Ejis sent out of membrane n +1 and evolved to E j. At the second step of the j-th loop (1 ≤j ≤p), if a membrane nt or nf contains object E j, then rule r33,j,lis enabled and applied, object E jis sent into membrane n +1 and evolves to Ej+1. Output stage. If the formula ϕis satisfiable, then there exists at least one membrane n +1 that contains object Ep+1after 3n +2p +3 steps. In this case, at step 3n +2p +4, by using rule r34,l, object Ep+1is sent out of membrane n +1 and evolved to t. At the next nsteps, by applying rules r35,i,l,l, r36,l, object twill be sent to membrane 1. At step 4n +2p +5, rule r37 is enabled and used, objects b, tare sent to the environment and evolved to yes. Note that rule r38,iis used from step 1 to step 4n +2p +5. Hence the computation of the system halts, the answer of the system being affirmative. If the formula ϕis not satisfiable, then there is no membrane n +1 that contains object Ep+1after 3n +2p +3steps. In this case, from step 3n +2p +4to step 4n +2p +5, only rule r38,iis enabled and applied, so that object α4n+2p+5will appear in membrane 1. At step 4n +2p +6, rule r39 is applied, objects α4n+2p+5, bare sent to the environment and evolved to no. The computation of the system halts, the answer of the system being negative. 3.2. Formal verification of the solution Next, we prove that the family of recognizer cell-like P systems from CCEC(2, 2), designed in the previous subsection, provides a polynomial time and uniform solution to the SAT problem, according with Definition 3. Theorem 3.1. SAT ∈PMCCCEC(2,2). Proof. The family of P systems previously constructed verifies the following: •Every system of the family is a recognizer P systems from CCEC(2, 2). •The family is polynomially uniform by Turing machines because for each n, p ∈N, the rules of (n, p)of the family are recursively defined from n, p ∈N, and the amount of resources needed to build an element of the family is of a polynomial order in nand p, as shown below: –Size of the working alphabet: 6np +10n +10p +20 ∈(np). –Initial number of membranes: 2 ∈(1). –Initial number of objects: 3 ∈(1). –Number of rules: 8n2p +4np +12n −2p +9 ∈(n2p). –Maximal number of objects involved in any rule: 4 ∈(1). •The pair (cod, s)of polynomial-time computable functions defined fulfill the following: for each instance ϕof the SAT problem, s(ϕ)is a natural number, cod(ϕ)is an input multiset of the system (s(ϕ)), and for each n ∈N, s−1(n)is a finite set. •The family is polynomially bounded: indeed, according to subsection 3.1, for each instance ϕof the SAT problem, the computation of (s(ϕ)) +cod(ϕ)always halts and sends to the environment object yes (it takes at most 4n +2p +5 steps) or object no (at step 4n +2p +6), being nthe number of variables of ϕand pthe number of clauses. •The family is sound with regard to (X, cod, s): indeed, for each instance ϕof the SAT problem, if the computation of (s(ϕ)) +cod(ϕ)is an accepting computation, then ϕis satisfiable. •The family is complete with regard to (X, cod, s): indeed, for each instance ϕof the SAT problem such that it is satisfiable, the computation of (s(ϕ)) +cod(ϕ)is an accepting computation.  Corollary 3.1. NP ∪co −NP ⊆PMCCCEC(2,2). Proof. It suffices to make the following observations: the SAT problem is NP-complete, SAT ∈PMCCCEC(2,2)and the class PMCCCEC(2,2)is closed under polynomial time reduction, and is under complementary.  4. Conclusions and further works In this work, a variant of cell-like P systems with evolutional communication rules, called cell-like P systems with evolutional communication rules and membrane creation has been proposed, and the computational efficiency of such P systems has been studied. In section 3, the presumed efficiency of CCEC(2, 2)has been established by providing a polynomial time and uniform solution to the SAT problem by means of a family of recognizer membrane systems CCEC(2, 2); that is by using recognizer cell-like P systems with evolutional communication rules and membrane creation such that the total number of objects involved in the LHS of the evolutional communication rules is at most 2 and the total number of objects involved in the RHS of the evolutional communication rule is at most 2. The SAT problem has been solved by cell-like P systems from CCEC(2, 2)in Section 3. It seems interesting to study the computational power of cell-like P systems from CCEC(2, 1), CCEC(1, 2)or CCEC(1, 1). In [24,41], a new strategy of using rules, called flat maximal parallelism was proposed, where in each membrane, a maximal set of applicable rules is chosen and each rule in the set is applied exactly once in each step. It would be interesting to investigate the presumed efficiency of cell-like P systems with evolutional communication rules and membrane creation by using rules in a flat maximally parallel way. Time-free solutions to NP-complete problems have been studied widely [26,38–40,42], where the correctness of the solution is irrelevant to the times associated with the involved rules. It deserves to investigate the computational efficiency of cell-like P systems with evolutional communication rules and membrane creation by using rules in a time-free way. The computational power of P systems with symport/antiport rules with respect to the number of objects and the number of membranes was investigated in [9,31]. An interesting open problem for P systems with evolutional symport/antiport rules is to find the minimal number of objects as well as the minimal number of membranes such that all recursively enumerable sets of natural numbers can be generated. Another interesting problem is to find characterizations of the sets of natural numbers for such kind of P systems that do not contain all recursively enumerable sets of natural numbers. Declaration of competing interest The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper. References [1] A. Alhazov, R. Freund, P systems with one membrane and symport/antiport rules of five symbols are computationally complete, in: Proceedings of Third Brainstorming Week on Membrane Computing, Sevilla, Spain, 2005, pp. 19–28. [2] A. Alhazov, C. Martín-Vide, L. Pan, Solving a PSPACE-complete problem by recognizing P systems with restricted active membranes, Fundam. Inform. 58 (2) (2003) 66–77. [3] A. Alhazov, L. Pan, Gh. P˘ aun, Trading polarizations for labels in P systems with active membranes, Acta Inform. 41 (2) (2004) 111–144. [4] A. Alhazov, M.J. Pérez-Jiménez, Uniform solution of QSAT using polarizationless active membranes, Lect. Notes Comput. Sci. 4664 (2007) 122–133. [5] A. Alhazov, Y. Rogozhin, Towards a characterization of P systems with minimal symport/antiport and two membranes, Lect. Notes Comput. Sci. 4361 (2006) 135–153. [6] F. Bernardini, V. Manca, P systems with boundary rules, Lect. Notes Comput. Sci. 2597 (2003) 107–118. [7] M. Cavaliere, Evolution-communication P systems, Lect. Notes Comput. Sci. 2597 (2003) 134–145. [8] G. Ciobanu, L. Pan, Gh. P˘ aun, M.J. Pérez-Jiménez, P systems with minimal parallelism, Theor. Comput. Sci. 378 (1) (2007) 117–130. [9] E. Csuhaj-Varjú, M. Margenstern, G. Vaszil, S. Verlan, On small universal antiport P systems, Theor. Comput. Sci. 372 (2–3) (2007) 152–164. [10] D. Díaz-Pernil, M.A. Gutiérrez-Naranjo, M.J. Pérez-Jiménez, A. Riscos-Núñez, A uniform family of tissue P system with cell division solving 3-COL in a linear time, Theor. Comput. Sci. 404 (1–2) (2008) 76–87. [11] D. Díaz-Pernil, M.J. Pérez-Jiménez, A. Riscos-Núñez, Á. Romero-Jiménez, Computational efficiency of cellular division in tissue-like membrane systems, Rom. J. Inf. Sci. Technol. 11 (3) (2008) 229–241. [12] P. Frisco, H.J. Hoogeboom, P systems with symport/antiport simulating counter automata, Acta Inform. 41 (2) (2004) 145–170. [13] M.R. Garey, D.J. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, San Francisco, 1979. [14] M.A. Gutiérrez-Naranjo, M.J. Pérez-Jiménez, A. Riscos-Núñez, F.J. Romero-Campero, Characterizing tractability with membrane creation, in: Proceedings of the Seventh International Symposium on Symbolic and Numeric Algorithms for Scientific Computing, SYNASC’05, 2005. [15] M.A. Gutiérrez-Naranjo, M.J. Pérez-Jiménez, F.J. Romero-Campero, A linear solution of subset sum problem by using membrane creation, Lect. Notes Comput. Sci. 3561 (2005) 258–267. [16] M.A. Gutiérrez-Naranjo, M.J. Pérez-Jiménez, F.J. Romero-Campero, A linear time solution for QSAT with membrane creation, Lect. Notes Comput. Sci. 3850 (2006) 241–252. [17] M.A. Gutiérrez-Naranjo, M.J. Pérez-Jiménez, F.J. Romero-Campero, A uniform solution to SAT using membrane creation, Theor. Comput. Sci. 371 (1–2) (2007) 54–61. [18] M. Ionescu, Gh. P˘ aun, T. Yokomori, Spiking neural P systems, Fundam. Inform. 71 (2–3) (2006) 279–308. [19] T.-O. Ishdorj, A. Leporati, L. Pan, X. Zeng, X. Zhang, Deterministic solutions to QSAT and Q3SAT by spiking neural P systems with pre-computed resources, Theor. Comput. Sci. 411 (25) (2010) 2345–2358. [20] L.F. Macías-Ramos, M.J. Pérez-Jiménez, A. Riscos-Núñez, L. Valencia-Cabrera, Membrane fission versus cell division: when membrane proliferation is not enough, Theor. Comput. Sci. 608 (2015) 57–65. [21] L.F. Macías-Ramos, B. Song, L. Valencia-Cabrera, L. Pan, M.J. Pérez-Jiménez, Membrane fission: a computational complexity perspective, Complexity 21 (6) (2016) 321–334. [22] C. Martín-Vide, J. Pazos, Gh. P˘ aun, A. Rodríguez-Patón, Tissue P systems, Theor. Comput. Sci. 296 (2) (2003) 295–326. [23] M. Mutyam, K. Krithivasan, P systems with membrane creation: universality and efficiency, Lect. Notes Comput. Sci. 2055 (2001) 276–287. [24] L. Pan, Gh. P˘ aun, B. Song, Flat maximal parallelism in P systems with promoters, Theor. Comput. Sci. 623 (2016) 83–91. [25] L. Pan, B. Song, L. Valencia-Cabrera, M.J. Pérez-Jiménez, The computational complexity of tissue P systems with evolutional symport/antiport rules, Complexity (2018) 3745210. [26] L. Pan, X. Zeng, X. Zhang, Time-free spiking neural P systems, Neural Comput. 23 (2011) 1320–1342. [27] A. P˘ aun, Gh. P˘ aun, The power of communication: P systems with symport/antiport, New Gener. Comput. 20 (3) (2002) 295–305. [28] A. P˘ aun, Gh. P˘ aun, G. Rozenberg, Computing by communication in networks of membranes, Int. J. Found. Comput. 13 (6) (2002) 779–798. [29] Gh. P˘ aun, Computing with membranes, J. Comput. Syst. Sci. 61 (1) (2000) 108–143. [30] Gh. P˘ aun, Membrane Computing: An Introduction, Springer-Verlag, Berlin, 2002. [31] Gh. P˘ aun, J. Pazos, M.J. Pérez-Jiménez, A. Rodríguez-Patón, Symport/antiport P systems with three objects are universal, Fundam. Inform. 64 (1–4) (2005) 353–367. [32] Gh. P˘ aun, M.J. Pérez-Jiménez, A. Riscos-Núñez, Tissue P systems with cell division, Int. J. Comput. Commun. 3(3) (2008) 295–303. [33] Gh. P˘ aun, G. Rozenberg, A. Salomaa (Eds.), The Oxford Handbook of Membrane Computing, Oxford University Press, New York, 2010. [34] M.J. Pérez-Jiménez, Á. Romero-Jiménez, F. Sancho-Caparrini, Complexity classes in models of cellular computing with membranes, Nat. Comput. 2(3) (2003) 265–285. [35] M.J. Pérez-Jiménez, An approach to computational complexity in membrane computing, Lect. Notes Comput. Sci. 3365 (2005) 85–109. [36] M.J. Pérez-Jiménez, P. Sosík, An optimal frontier of the efficiency of tissue P systems with cell separation, Fundam. Inform. 138 (1–2) (2015) 45–60. [37] G. Rozenberg, A. Salomaa (Eds.), Handbook of Formal Languages, 3 vols., Springer, Berlin, 1997. [38] B. Song, Y. Kong, Solution to PSPACE-complete problem using P systems with active membranes with time-freeness, Math. Probl. Eng. (2019) 5793234. [39] T. Song, L.F. Macías-Ramos, L. Pan, M.J. Pérez-Jiménez, Time-free solution to SAT problem using P systems with active membranes, Theor. Comput. Sci. 529 (2014) 61–68. [40] B. Song, M.J. Pérez-Jiménez, L. Pan, An efficient time-free solution to QSAT problem using P systems with proteins on membranes, Inf. Comput. 256 (2017) 287–299. [41] B. Song, M.J. Pérez-Jiménez, Gh. P˘ aun, L. Pan, Tissue P systems with channel states working in the flat maximally parallel way, IEEE Trans. Nanobiosci. 15 (7) (2016) 645–656. [42] B. Song, T. Song, L. Pan, A time-free uniform solution to subset sum problem by tissue P systems with cell division, Math. Struct. Comput. Sci. 27 (1) (2017) 17–32. [43] B. Song, C. Zhang, L. Pan, Tissue-like P systems with evolutional symport/antiport rules, Inf. Sci. 378 (2017) 177–193. [44] P. Sosík, P systems attacking hard problems beyond NP: a survey, J. Membr. Comput. 1(3) (2019) 198–208. [45] P. Sosík, A. P˘ aun, A. Rodríguez-Patón, P systems with proteins on membranes characterize PSPACE, Theor. Comput. Sci. 488 (2013) 78–95. [46] P. Sosík, A. Rodríguez-Patón, Membrane computing and complexity theory: a characterization of PSPACE, J. Comput. Syst. Sci. 73 (1) (2007) 137–152.