Narrowing Frontiers of Efficiency with Evolutional Communication Rules and Cell Separation

Narrowing Frontiers of Efficiency with Evolutional Communication Rules and Cell Separation David Orellana-Mart´ın1, Luis Valencia-Cabrera1, Bosheng Song2, Linqiang Pan2,3,MarioJ.P´erez-Jim´enez1 1Research Group on Natural Computing, Department of Computer Science and Artificial Intelligence, Universidad de Sevilla Avda. Reina Mercedes s/n, 41012 Sevilla, Spain E-mail: {dorellana, lvalencia, marper}@us.es Key 2Laboratory of Image Information Processing and Intelligent Control of Education Ministry of China, School of Automation, Huazhong University of Science and Technology, Wuhan, Hubei, 430074, China E-mail: boshengsong@163, [email protected] 3School of Electric and Information Engineering, Zhengzhou University of Light Industry, Zhengzhou 450002, China Summary. In the framework of Membrane Computing, several efficient solutions to computationally hard problems have been given. To find new borderlines between families of P systems that can solve them and the ones that cannot is an important way to tackle the Pversus NP problem. Adding syntactic and/or semantic ingredients can mean passing from non-efficiency to presumably efficiency. Here, we try to get narrow frontiers, setting the stage to adapt efficient solutions from a family of P systems to another one. In order to do that, a solution to the SAT problem is given by means of a family of tissue P systems with evolutional symport/antiport rules and cell separation with the restriction that both the left-hand side and the right-hand side of the rules have at most two objects. Key words: Membrane Computing, symport/antiport rules, the Pversus NP problem, SAT problem. 1 Introduction Membrane Computing is a bio-inspired computing paradigm based on the structure and behavior of living cells. There are several classes of P systems, the computational models of this paradigm. It was first introduced in [7], defining one of the main models, cell-like P systems that abstract the hierarchical arrangement of membranes within a single cell. In [4], the idea of the interactions of networks of cells (placed in the nodes of a directed graph) between cells and between cells 140 D. Orellana-Mart´ın et al. and their environment is used to develop tissue-like P systems, named by the ensemble of cells in living beings. Another approach with the same structure are the so-called spiking neural P systems [2], SN P systems for short, inspired by the way that neurons communicate with each other by means of short electrical impulses (spikes). Within these models, several variants can be defined only by changing syntactic and/or semantic ingredients, such as kinds of rules possible, length of rules, parallelism permitted, number of objects and so on. Computational complexity theory in the framework of Membrane Computing uses special variants of P systems called recognizer membrane systems, devices that, given an initial configuration depending on an instance of a decision problem, return yes or no depending of the answer to such instance. A deep vision of complexity can be seen in [8, 9]. Tissue P systems have been widely investigated from this point of view, giving characterizations for most of their variants. For instance, in [1] and [11], the borderline of efficiency for tissue P systems with symport/antiport rules and cell division by means of the length of communication rules is given, that is, passing from 1 to 2 means passing from non-efficiency to presumably efficiency. In [5] and [10], a similar result is given for tissue P systems with symport/antiport rules and cell separation, but in this case, rules with length at most 3 are needed in order to solve efficiently computationally hard problems. Thus, three frontiers of efficiency can be found here: two described before by means of the length of the rules, and the third one when using rules with length at most 2, between separation and division rules. In [12], a new variant of these systems is defined. Based on the chemical reactions within cells and how reactives evolve into new components, evolutional communication rules are described as a movement of components between different cells or a cell and the environment but within the reaction objects can change into something new. It is interesting to study these systems from the computational complexity theory point of view, and in [6], an efficient solution to the SAT problem is given by these systems with some restrictions about the length of their rules, but the narrowest borderline is not defined. The purpose of this paper is to tight it. The paper is organized as follows: first, we recall some concepts that are going to be used through the work. In Section 3 the framework of tissue P systems with evolutional symport/antiport rules is introduced. After that, Sections 4 and 5 are devoted to give a solution to SAT by means of a family of P systems with evolutional symport/antiport rules with cell separation and rules with length at most (2,2) and a formal verification of a design. Finally, some conclusions and open research lines are exposed. 2 Preliminaries In order to make this work self-contained, we introduce some notions that are going to be used through the paper. Narrowing Frontiers of Efficiency 141 2.1 Alphabets and sets An alphabet Γis a non-empty set and their elements are called symbols.Astring u over Γis an ordered finite sequence of symbols, that is, a mapping from a natural number n∈Nonto Γ.Thenumbernis called the length of the string uand it is denoted by |u|. The empty string (with length 0) is denoted by λ.Thesetofall strings over an alphabet Γis denoted by Γ∗.Alanguage over Γis a subset of Γ∗. Amultiset over an alphabet Γis an ordered pair (Γ, f)wherefis a mapping from Γonto the set of natural numbers N.Thesupport of a multiset m=(Γ, f) is defined as supp(m)={x∈Γ|f(x)>0}. A multiset is finite (resp., empty) if its support is a finite (resp., empty) set. We denote by ∅the empty multiset and we denote by M(Γ) the set of all multisets over Γ. Let m1=(Γ, f1), m2=(Γ, f2) be multisets over Γ, then the union of m1and m2, denoted by m1+m2, is the multiset (Γ, g), when g(x)=f1(x)+f2(x)foreach x∈Γ. 2.2 Decision problems A decision problem Xcan be informally defined as one whose solution 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∈ EX|θX(u)=1}. Conversely, every language Lover an alphabet Σhas associated a decision problem XL=(IXL,θ XL) as follows: IXL=Σ∗and θXL(u)=1ifand only if u∈L. Then, given a decision problem Xwe have XLX=X,andgivena language Lover an alphabet Σwe have LXL=L. It is worth pointing out that any Turing machine M(with input alphabet ΣM) has associated a decision problem XM=(IM,θ M) defined as follows: IM=Σ∗ M, and for every u∈Σ∗ M,θM(u) = 1 if and only if Maccepts u. Obviously, the decision problem XMis solvable by the Turing machine. 3 Tissue P systems with evolutional communication rules Definition 1. A recognizer tissue P system with evolutional symport/antiport rules and cell separation of degree q≥1is a tuple Π=(Γ, Γ0,Γ 1,Σ,M1,...,Mq,R,i out) where: •Γand Eare finite alphabets whose elements are called objects; •Γ0and Γ1is a partition of Γ; •E⊆Γ; 142 D. Orellana-Mart´ın et al. •M q,...,Mqare multisets over Γ; •Ris a finite set of rules, of the following forms: 1. Evolutional communication rules: a) [u]i[] j→[] i[u]j,where1≤i, j ≤q,i=j,u∈M+ f(Γ)and u∈Mf(Γ)(evolutional symport rules); b) [u]i[v]j→[v]i[u]j,where1≤i, j ≤q,i=j,u, v ∈M+ f(Γ)and u,v∈Mf(Γ)(evolutional antiport rules); 2. [a]i→[Γ0]i[Γ1]i,wherei∈{1,...,q},i =iout and a∈Γ; (separation rules); •iout ∈{0,1,...,q}. A recognizer tissue P system with evolutional symport/antiport rules and cell separation of degree q≥1 Π=(Γ, Γ0,Γ 1,E,M1,...,Mq,R,i out) canbeviewedasasetofqcells, labelled by 1,...,q such that (a) M1,...,Mq represent the multisets of objects initially placed in the qcells of the system; (b) E is the set of objects initially located in the environment of the system, all of them available in an arbitrary number of copies; (c) iout represents a distinguished region which will encode the output of the system. We use the term region i(0 ≤i≤q) to refer to cell iin the case 1 ≤i≤qand to refer to the environment in the case i=0. Aconfiguration at any instant of a tissue P system with evolutional symport/antiport rules and cell separation is described by the multisets of objects in each cell and the multiset of objects over Γ\E in the environment at that moment. The initial configuration of Π=(Γ, Γ0,Γ 1,E,M1,...,Mq,R,i out)is M1,...,Mq;∅). An evolutional symport rule [ u]i[] j→[] i[u]jis applicable at a configuration Ctat an instant tif there is a region ifrom Ctwhich contains multiset u. By applying an eovlutional symport rule, the multiset of objects in region ifrom Ctis consumed and the multiset of objects uis generated in region jfrom Ct+1. An evolutional symport rule [ u]i[v]j→[v]i[u]jis applicable at a configuration Ctat an instant tif there is a region ifrom Ctwhich contains multiset uand there is a region jwhich contains multiset v. By applying an eovlutional symport rule, the multiset of objects uin region iand multiset of objects vin region jfrom Ctare consumed and the multiset of objects uis generated in region jand the multiset of objects vin region ifrom Ct+1. A separation rule [ a]i→[Γ0]i[Γ1]iis applicable at a configuration Ctat an instant tif there is a cell ifrom Ctwhich contains object aand i=iout.By applying a separation rule to such a cell i, (a) object ais consumed from such cell; (b) two new cells with label iare generated at configuration Ct+1; and (c) objects from Γ0from the original cell are placed in one of the new cells, while objects from Γ1from the original cell are placed in the other one. The rules of a tissue P system with evolutional symport/antiport rules and cell separation are applied in a maximally parallel manner, following the previous Narrowing Frontiers of Efficiency 143 remarks, and taking into account that when a cell iis being separated at one transition step, no other rules can be applied to that cell iat that step. A transition from a configuration Ctto another configuration Ct+1 is obtained by applying rules in a maximally parallel manner following the previous remarks. A computation of the system is a (finite or infinite) sequence of transitions starting from the initial configuration, where any term of the sequence other than the first one is obtained from the previous configuration in one transition step. If the sequence is finite (called halting computation) then the last term of the sequence is a halting configuration, that is, a configuration where no rule is applicable to it. A computation gives a result only when a halting configuration is reached, and that result is encoded by the multiset of objects present in the output region iout. A natural framework to solve decision problems is to use recognizer P systems. Definition 2. A recognizer tissue P system with evolutional symport/antiport rules and cell separation of degree q≥1is a tuple Π=(Γ, Γ0,Γ 1,E,Σ,M1,...,Mq,R,i in,i out), where – the tuple (Γ, Γ0,Γ 1,E,M1,...,Mq,R,i out)is a tissue P system with evolutional symport/antiport rules of degree q≥1,whereΓstrictly contains an (input) alphabet Σand two distinguished objects yes and no,andMi(1≤i≤q) are multisets over Γ\Σ; –iin ∈{1,...,1}is the input cell and iout is the label of the environment; – for each multiset mover the input alphabet Σ,anycomputationofthesystem Πwith input mstarts from the configuration of the form (M1,...,Miin + m,...,Mq;∅), it always halts and either object yes or object no (but not both) must appear in the environment at the last step. For each ordered pair of natural numbers (k1,k 2) greater or equal to 1, the class of recognizer P systems with evolutional symport/antiport rules and cell separation with evolutional communication rules of length at most (k1,k 2)isdenoted by TSEC(k1,k 2). This means that, given an evolutional communication rule [ u]i[v]j→[v]i[u]jthe LHS (resp., RHS) of any evolutional communication rule in a system from TSEC(k1,k 2) involves at most k1=|u|+|v|objects (resp., k2=|u|+|v|objects). Next, we define the concept of solving a problem in a uniform way and in polynomial time by a family of recognizer tissue P systems with evolutional symport/antiport rules and cell separation. Definition 3. A decision problem X=(IX,θ X)is solvable in a uniform way and in polynomial time by a family Π={Π(n)|n∈N)}of recognizer tissue P systems with evolutional symport/antiport rules and cell separation if the following conditions hold: 1. the family Πis polynomially uniform by Turing machines; and 144 D. Orellana-Mart´ın et al. 2. there exists a polynomial encoding (cod, s)of IXin Πsuch that (a) for each instance u∈IX,s(u)is a natural number and cod(u)is an input multiset of the system Π(s(u));(b)foreachn∈N,s−1(n)is a finite set; and (c) the family Πis polynomially bounded, sound and complete with regard to (X, cod, s). The set of all decision problems that can be solved by recognizer tissue P systems with evolutional symport/antiport rules and cell separation with evolutional communication rules of length at most (k1,k 2) in a uniform way and polynomial time is denoted by PMCTSEC(k1,k2). 4SolutiontoSAT with evolutional communication rules and separation rules In [6] an efficient solution to the SAT problem is given by means of a family of P systems from TSEC(3,2). A frontier of efficiency is given, but some open problems remain, as indicate Figure 1 of such work. It shows that the class of problems that can be solved by P systems from TSEC(2,k) with k≥2 is unknown. In this work we improve this borderline closing the previous open questions, giving an efficient solution of the SAT problems by means of a family of P systems from TSEC(2,2). Let us briefly recall the description of the SAT problem: given a boolean formula in conjunctive normal form (CNF), to determine whether or not there exists an assignment to its variables, called truth assignment, on which it evaluates true. Theorem 1. SAT ∈PMCTSEC(2,2) For each n, p ∈N, we consider the recognizer P system Π(n, p)=(Γ, Γ0,Γ 1,Σ,E,M1,...,Mq,R,i in,i out) from TSEC(2,2) defined as follows: 1. Working alphabet Γ: {yes,no,y 1,y 2,n 1,n 2,#}∪ {ai,j |1≤i≤n, 0≤j≤i}∪ {a i,j |2≤i≤n, 0≤j≤i−1}∪ {aL i,j ,a R i,j |2≤i≤n, 1≤j≤i−1}∪ {αj,α  j,α L j,α R j|1≤j≤p+1}∪ {ti,f i,t  i,t  if i,t L i,t R i,fL i,fR i|1≤i≤n}∪ {βl,k,β l,k,βL l,k,βR l,k |0≤k≤n, 1≤l≤n}∪ {xi,j,k, xi,j,k,x ∗ i,j,k |1≤i≤n, 1≤j≤p, 1≤k≤n+j−1}∪ {x i,j,k, x i,j,k,x ∗ i,j,k,x  i,j,k, x i,j,k,x ∗ i,j,k,x  i,j,k, x i,j,k,x ∗ i,j,k,| 0≤i≤n, 1≤j≤p, 1≤k≤n}∪ {cj,k |1≤j≤p, j ≤k≤p}∪{δi|0≤i≤4n+p+2}∪ {δ i|0≤i≤4n+p}. Narrowing Frontiers of Efficiency 145 2. Γ1=Γ\Γ0,Γ0={aL i,j |2≤i≤n, 1≤j≤i−1}∪ {αL j|1≤j≤p+1}∪{tL i,fL i|1≤i≤n}∪ {βL l,k |0≤k≤n, k +1≤l≤n} 3. Input alphabet Σ:{xi,j,0, xi,j,0,x ∗ i,k,0|1≤i≤n, 1≤j≤p}. 4. Environment alphabet E:{γ}. 5. M1={δ0,δ 0}∪{βn+p+1 l,0|1≤l≤n}, M2={ai,0|1≤i≤n}∪{αj|1≤j≤p+1}. 6. The set of rules Rconsists of the following rules: 1.1 Rules for (4k+ 1)-th steps. [ai,i−1]2[γ]0→[a i,i−1t i]2[] 0,for 1 ≤i≤n [ti]2[γ]0→[t i]2[] 0 [fi]2[γ]0→[f i]2[] 0for 1 ≤i≤n [ai,j ]2[γ]0→[a i,j ]2[] 0,for 2 ≤i≤n, 0≤j≤i−2 [αj]2[γ]0→[α j]2[] 0,for 1 ≤j≤p+1 [βl,k ]1[γ]0→[β l,k ]1[] 0for 0≤k≤n, k+1≤l≤n [xi,j,k ]1[γ]0→[x i,j,k ]1[] 0 [xi,j,k ]1[γ]0→[x i,j,k ]1[] 0 [x∗ i,j,k ]1[γ]0→[x∗ i,j,k ]1[] 0 ⎫ ⎬ ⎭ for 1≤i≤n, 1≤j≤p, 0≤k≤n−1 1.2 Rules for (4k+ 2)-th steps. [a i,i−1]2[γ]0→[ai,i fR i]2[] 0 [t i]2[γ]0→[tL i]2[] 0for 1 ≤i≤n [t i]2[γ]0→[tL itR i]2[] 0 [f i]2[γ]0→[fL ifR i]2[] 0for 1 ≤i≤n [a i,j ]2[γ]0→[aL i,j+1 aR i,j+1 ]2[] 0,for 2≤i≤n, 0≤j≤i−1 [α j]2[γ]0→[αL jαR j]2[] 0,for 1 ≤j≤p+1 [β l,k ]1[γ]0→[βL l,k+1 βR l,k+1 ]1[] 0,for 0≤k≤n, k+1≤l≤n [x i,j,k ]1[γ]0→[x2 i,j,k+1 ]1[] 0 [x i,j,k ]1[γ]0→[x2 i,j,k+1 ]1[] 0 [x∗ i,j,k ]1[γ]0→[x∗2 i,j,k+1 ]1[] 0 ⎫ ⎬ ⎭ 1≤i≤n, 1≤j≤p, 0≤k≤n−1 1.3 Rules for (4k+ 3)-th steps. [ai,i ]2→[Γ0]2[Γ1]2,for 1 ≤i≤n [βO k,k ]1[] 0→[] 1[βO k,k ]0 [βO l,k ]1[] 0→[] 1[βl,k ]0for O∈{L, R}, 1≤k≤n, k+1≤l≤n [x i,j,k ]1[γ]0→[x i,j,k ]1[] 0 [x i,j,k ]1[γ]0→[x i,j,k ]1[] 0 [x∗ i,j,k ]1[γ]0→[x∗ i,j,k ]1[] 0 ⎫ ⎬ ⎭ for 1≤i≤n, 1≤j≤p, 1≤k≤n 1.4 Rules for (4k)-th steps. 146 D. Orellana-Mart´ın et al. [aO i,j ]2[βO k,k ]0→[ai,j ]2[] 0 [rO i]2[βO k,k ]0→[ri]2[] 0for O∈{L, R}, r∈{t, f}, 1≤i≤n, 1≤j≤n, 1≤k≤n [αO j]2[βO k,k ]0→[αj]2[] 0,for O∈{L, R}, 1≤j≤p+1, 0≤k≤n [x i,j,k ]1[γ]0→[xi,j,k ]1[] 0 [x i,j,k ]1[γ]0→[xi,j,k ]1[] 0 [x∗ i,j,k ]1[γ]0→[x∗ i,j,k ]1[] 0 ⎫ ⎬ ⎭ for 1≤i≤n, 1≤j≤p, 0≤k≤n [] 1[βl,k ]0→[βl,k ]1[] 0,for 0 ≤k≤n, k +1≤l≤n 2.1 Rules to check satisfied clauses. [ti]2[xi,j,n+j−1]1→[cj,j ti]2[] 1 [ti]2[xi,j,n+j−1]1→[ti]2[] 1 [ti]2[x∗ i,j,n+j−1]1→[ti]2[] 1 [fi]2[xi,j,n+j−1]1→[fi]2[] 1 [fi]2[xi,j,n+j−1]1→[cj,j fi]2[] 1 [fi]2[x∗ i,j,n+j−1]1→[fi]2[] 1 ⎫ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎬ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎭ for 1 ≤i≤n, 1≤j≤p [xi,j,n+k]1[γ]0→[xi,j,n+k+1 ]1[] 0 [xi,j,n+k]1[γ]0→[xi,j,n+k+1 ]1[] 0 [x∗ i,j,n+k]1[γ]0→[x∗ i,j,n+k+1 ]1[] 0 ⎫ ⎬ ⎭ for 1≤i≤n, 1≤j≤p, 0≤k≤j−2 [cj,k ]2[γ]0→[cj,k+1 ]2[] 0,for 1 ≤j≤p, j ≤k≤p−1 3.1 Rules to check if all clauses are satisfied by a truth assignment. [αp+1 ]2[δ 4n+p]1→[α p+1 ]2[] 0 [αjcj,p ]2[] 0→[] 2[#] 0,for 1 ≤j≤p 4.1 General counters. [δi]1[γ]0→[δi+1 ]1[] 0,for 0 ≤i≤4n+p+1 [δ 4i+1 ]1[γ]0→[δ2 4i+2 ]1[] 0,for 0 ≤i≤n−1 [δ 4i+k]1[γ]0→[δ 4i+k+1 ]1[] 0,for 0 ≤i≤n−1,k∈{0,2,3} [δ 4n+i]1[γ]0→[δ 4n+i+1 ]1[] 0,for 0 ≤i≤p−1 4.2 Rules to give a negative answer. [αjα p+1 ]2[] 0→[] 2[n1]0,for 1 ≤j≤p [] 2[n1]0→[n1]2[] 0 [n1]2[δ4n+p+2 ]1→[n2]2[] 1 [n2]2[] 0→[] 2[no ]0 4.3 Rules to give an affirmative answer. [α p+1 ]2[δ4n+p+2 ]1→[y1]2[] 1 [y1]2[γ]0→[y2]2[] 0 [y2]2[] 0→[] 2[yes ]0 7. The input cell is the cell labelled by 1 (iin = 1) and the output region is the environment (iout =env). Narrowing Frontiers of Efficiency 147 Let ϕ=C1∧ ···∧Cpan instance of SAT problem consisting of pclauses Cj=lj,1∨···∨lj,rj,1≤j≤p,whereVar(ϕ)={x1,...,x n},andlj,k ∈{xi,¬xi| 1≤i≤n},1≤j≤p, 1≤k≤rj. Let us assume that the number of variables, n, and the number of clauses, p,ofϕ, are greater than or equal to 2. We consider the polynomial encoding (cod, s)fromSAT in Πdefined as follows: for each ϕ∈ISAT with nvariables and pclauses, s(ϕ)=n, pand cod(ϕ)={xi,j,0|xi∈Cj}∪{xi,j,0|¬xi∈Cj}∪{x∗ i,j,0|xi∈ Cj,¬xi∈ Cj} For instance, the formula ϕ=(x1∨x2∨¬x3)∧(¬x2∨x4)∧(¬x2∨x3∨¬x4) is encoded as follows: cod(ϕ)=⎛ ⎝ x1,1,0x2,1,0x3,1,0x∗ 4,1,0 x∗ 1,2,0x2,2,0x∗ 3,2,0x4,2,0 x∗ 1,3,0x2,3,0x3,3,0x4,3,0 ⎞ ⎠ We define codk(ϕ)asthesetofelementsofcod(ϕ) when the third subscript equals k. In the same way, we define cod k(ϕ), cod k(ϕ)andcod k(ϕ)asthesets of elements of cod(ϕ) when the third subscript equals kand elements are primed, double primed and triple primed, respectively. For notation convenience, we define codj k(ϕ) the subset of elements of codk(ϕ) with elements of Cj,...,C p. For instance, cod2 4(ϕ) would be the following set: cod2 4(ϕ)=x∗ 1,2,4x2,2,4x∗ 3,2,4x4,2,4 x∗ 1,3,4x2,3,4x3,3,4x4,3,4 The Boolean formula ϕwill be processed by the system Π(s(ϕ)) + cod(ϕ). Next, we informally describe how that system works. The solution proposed follows a brute force algorithm in the framework of recognizer tissue P systems with separation and evolutional communication rules, and it consists of the following stages: •Generation stage: Using separation rules each 4 steps, we produce 2nmem- branes labelled by 2 containing each possible truths assignment. At the same time, we generate 2ncopies of codn(ϕ). This stage spends ncomputation steps exactly, being nthe numer of variables of ϕ. •First checking stage:Withrulesfrom2.1, we can check which clauses from the input formula ϕhave been satisfied by a specific truth assignment. This stage takes exactly psteps. •Second checking stage:Withrulesfrom3.1, we remove objects αjsuch that they are removed from a membrane if and only if the truth assignment associated to that membrane makes true clause Cj. This stage takes exactly one step. •Output stage:Withrulesfrom4.2 and 4.3, we can give an affirmative or a negative answer depending on if the input formula is satisfiable or not. This stage spends exactly 4 steps, regardless of whether the formula is satisfiable or not. 154 D. Orellana-Mart´ın et al. –objectsr1,...,r n,beingr∈{t, f}; –objectsα1,...,α p+1;and –objectsc1,k,...,c k,k,wherecj,k represents that clause Cjhas been satisfied by the truth formula encoded in such membrane. (b)C4n+p(1) = {δ4n+p,δ2n 4n+p},andthereare2nmembranes labelled by 2 such that each of them contains objects α1,...,α p+1, a different subset {r1,...,r n} and objects cjwhen clause Cjis satisfied in that membrane. Proof. (a) is going to be demonstrated by induction on k. (a) The base case k= 0 is trivial because at the initial configuration we have: C4n(1) = {δ4n,δ2n 4n,cod 4n(ϕ)}and there exist 2nmembranes labelled by 2 containing objects α1,...,α p+1 and a different subset {r1,...,r n},being r∈{t, f}. Then, configuration C4nyields configuration C4n+1 by applying the rules: [ti]2[xi,1,n ]1→[c1,1ti]2[] 1 [ti]2[xi,1,n ]1→[ti]2[] 1 [ti]2[x∗ i,1,n ]1→[ti]2[] 1 [fi]2[xi,1,n ]1→[fi]2[] 1 [fi]2[xi,1,n ]1→[c1,1fi]2[] 1 [fi]2[x∗ i,1,n ]1→[fi]2[] 1 ⎫ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎬ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎭ for 1 ≤i≤n, 1≤j≤p [xi,j,n+k]1[γ]0→[xi,j,n+k+1 ]1[] 0 [xi,j,n+k]1[γ]0→[xi,j,n+k+1 ]1[] 0 [x∗ i,j,n+k]1[γ]0→[x∗ i,j,n+k+1 ]1[] 0 ⎫ ⎬ ⎭ for 1 ≤i≤n, 2≤j≤p [δ4n]1[γ]0→[δ4n+1 ]1[] 0 [δ 4n]1[γ]0→[δ 4n+1 ]1[] 0 Thus, C4n+1(1) = {δ4n+1,δ2n 4n+1,cod 2 4n+1(ϕ)2n}and in C4n+1 there exist 2n membranes labelled by 2 such that their contents are objects α1,...,α p+1,a different subset {r1,...,r n},beingr∈{t, f}and objects c1,1if some literal present in Cjsatisfies it2. Hence, the result holds for k=1. Supposing that, by induction, result is true for k(0 ≤k≤p−1); that is, •C 4n+k(1) = {δ4n+k,δ2n 4n+k,cod k+1 n(ϕ)2k} •There are 2nmembranes labelled by 2 such that each of them contains – objects r1,...,r n,beingr∈{t, f}; – objects α1,...,α p+1;and – objects c1,k,...,c k,k,wherecj,k represents that clause Cjhas been satisfied by the truth formula encoded in such membrane. Then, configuration C4n+kyields configuration C4n+k+1 by applying the rules: 2Here, objects # are created, but they are not used anymore, so they are not going to be noted here. Narrowing Frontiers of Efficiency 155 [ti]2[xi,k+1,n+k]1→[ck+1,k+1 ti]2[] 1 [ti]2[xi,k+1,n+k]1→[ti]2[] 1 [ti]2[x∗ i,k+1,n+k]1→[ti]2[] 1 [fi]2[xi,k+1,n+k]1→[fi]2[] 1 [fi]2[xi,k+1,n+k]1→[ck+1,k+1 fi]2[] 1 [fi]2[x∗ i,k+1,n+k]1→[fi]2[] 1 ⎫ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎬ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎭ for 1 ≤i≤n, 1≤j≤p [xi,j,n+k]1[γ]0→[xi,j,n+k+1 ]1[] 0 [xi,j,n+k]1[γ]0→[xi,j,n+k+1 ]1[] 0 [x∗ i,j,n+k]1[γ]0→[x∗ i,j,n+k+1 ]1[] 0 ⎫ ⎬ ⎭ for 1 ≤i≤n, k +2≤j≤p [cj,k ]2[γ]0→[cj,k+1 ]2[] 0,for 1 ≤j≤p, k ≤k≤p−1 [δ4n+k]1[γ]0→[δ4n+k+1 ]1[] 0 [δ 4n+k]1[γ]0→[δ 4n+k+1 ]1[] 0 Thus, C4n+k+1(1) = {δ4n+k+1,δ2n 4n+k+1,cod k+2 4n+k+1(ϕ)2n}and in C4n+k+1 there exist 2nmembranes labelled by 2 such that their contents are objects α1,...,α p+1, a different subset {r1,...,r n},beingr∈{t, f}and objects c1,k,...,c k,k if some literal present in Cjsatisfies them. In order to demonstrate (b) it is enough to notice that, on the one hand, from (a) configuration C4n+p−1holds: •C 4n+p−1(1) = {δ4n+p−1,δ2n 4n+p−1,cod p n(ϕ)2n} •There are 2nmembranes labelled by 2 such that each of them contains – objects r1,...,r n,beingr∈{t, f}; – objects α1,...,α p+1;and – objects c1,p−1,...,c p−1,p−1,wherecj,p−1represents that clause Cjhas been satisfied by the truth formula encoded in such membrane. On the other hand, configuration C4n+p−1yields configuration C4n+pby applying the rules: [ti]2[xi,p,n+p−1]1→[cp,p ti]2[] 1 [ti]2[xi,p,n+p−1]1→[ti]2[] 1 [ti]2[x∗ i,p,n+p−1]1→[ti]2[] 1 [fi]2[xi,p,n+p−1]1→[fi]2[] 1 [fi]2[xi,p,n+p−1]1→[cp,p fi]2[] 1 [fi]2[x∗ i,p,n+p−1]1→[fi]2[] 1 ⎫ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎬ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎭ for 1 ≤i≤n, 1≤j≤p [cj,p−1]2[γ]0→[cj,p ]2[] 0,for 1 ≤j≤p−1 [δ4n+p−1]1[γ]0→[δ4n+p]1[] 0 [δ 4n+p−1]1[γ]0→[δ 4n+p]1[] 0 Then, we have C4n+p(1) = {δ4n+p,δ2n 4n+p},andinC4n+pthere are 2nmem- branes labelled by 2 such that each of them contains a different subset {r1,...,r n}, being r∈{t, f}3, objects α1,...,α p+1 and objects cj,p when clause Cjhas been satisfied by the truth assignment encoded in such membrane.  3This subset is not used anymore, so it will not be noted from now on. 156 D. Orellana-Mart´ın et al. Second checking stage Here, when rules from 3.1 are fired at the (4n+p+ 1)-th step, objects αjwithin a membrane labelled by 2 are removed if and only if the truth assignment associated to that membrane makes true clause Cj, that is, if there is at least one object cjin such membrane. At configuration C4n+pwe have C4n+p(1) = {δ4n+p,δ2n 4n+p}and each membrane labelled by 2 contains objects α1,...,α pand objects cjsuch that the corresponding truth assignment satisfies the clause Cj. By applying rules from 3.1 and rule [ δ4n+p]1[γ]0→[δ4n+p+1 ]1[] 0, object δ4n+pevolves into δ4n+p+1 within the membrane labelled by 1, and in each membrane labelled by 2, objects αjsuch that their corresponding object cj,p are “removed” from the system, and let the next stage to check whether or not they are present, besides the object αp+1, that is prepared, evolving to α p+1, to react with the remaining objects αj. This stage takes exactly one step. Output stage The output phase starts at the (4n+p+ 2)-th step, and takes exactly four steps, regardless of whether the input formula ϕis satisfied or not by some truth assignment. •Affirmative answer: If the input formula ϕof SAT problem is satisfiable then at least one of the truth assignments from a membrane with label 2 has satisfied all clauses. Then, there will be a membrane labelled by 2 such that all objects αj,with1≤j≤phave dissapeared in the previous step. At configuration C4n+p+1,wehaveC4n+p+1(1) = {δ4n+p+1}and in each membrane labelled by 2 there remain objects αjif the corresponding truth assignment does not make true clause Cjand one object α p+1. In this step, only rule [ δ4n+p+1 ]1[γ]0→ [δ4n+p+2 ]1[] 0will be fired and rules [ αjα p+1 ]2[] 0→[] 2[n1]0will be fired in membranes labelled by 2 such that at least one clause is not satisfied by the corresponding truth assignment. Then, at configuration C4n+p+2,we have C4n+p+2(1) = {δ4n+p+2,n t 1},beingtthe number of truth assignments that have at least one clause not satisfied by the corresponding truth assignment, and membranes labelled by 2 contains an object α p+1 if and only if the corresponding truth assignment makes true all clauses from ϕ,andcancontain objects αj,1≤j≤p, if clause Cjis not satisfied by the corresponding truth assignment. In the next step, applying rules [ ]2[n1]0→[n1]2[] 0and [ α p+1 ]2[δ4n+p+2 ]1→ [y1]2[] 1,weobtainanobjecty1in a membrane labelled by 2 if and only if the corresponding truth assignment makes true the input formula. Let us remark that more than one membrane labelled by 2 can contain a truth assignment that makes true ϕ, but in this case, we as we want to know if at least one truth assignment makes true the input formula ϕ, we only want one object y1. Then, at configuration C4n+p+3 we have that C4n+p+3(1) = ∅andinmembranesla- Narrowing Frontiers of Efficiency 157 belled by 2, we can have objects n14, adding up to tin all membranes labelled by 2, being tthe number of truth assignments that do not make true the input formula, an object α p+1 if the corresponding truth assignment makes true all clauses, excepting one membrane labelled by 2 which corresponding truth assignment makes true the input formula that will contain an object y1,and can contain objects αj,1≤j≤p, if clause Cjis not satisfied by the corresponding truth assignment. In the next step the only rule that can be fired is [y1]2[γ]0→[y2]2[] 0, that will be useful to synchronize the affirmative and the negative answer. Let us note that rule [ n1]2[δ4n+p+2 ]1→[n2]2[] 1can- not be fired because object δ4n+3 has been consumed in the previous step by an object α p+1. Then, at configuration C4n+p+4,wehavethatC4n+p+4(1) = ∅ and in membranes labelled by 2, we can have objects n1, adding up to tin all membranes labelled by 2, being tthe number of truth assignments that do not make true the input formula, an object α p+1 if the corresponding truth assignment makes true all clauses, excepting one membrane labelled by 2 which corresponding truth assignment makes true the input formula that will contain an object y2, and can contain objects αj,1≤j≤p, if clause Cjis not satisfied by the corresponding truth assignment. At the last step of the computation, rule [ y2]2[] 0→[] 2[yes ]0is fired, sending an object yes to the environment. Then, at configuration C4n+p+5,wehavethatC4n+p+5(1) = ∅ and in membranes labelled by 2, we can have objects n1, adding up to tin all membranes labelled by 2, being tthe number of truth assignments that do not make true the input formula, an object α p+1 if the corresponding truth assignment makes true all clauses, excepting one membrane labelled by 2 which corresponding truth assignment makes true the input formula, and can contain objects αj,1≤j≤p, if clause Cjis not satisfied by the corresponding truth assignment, and there will be an object yes in the environment. Here, the computation halts and returns an affirmative answer. •Negative answer: If the input formula ϕof SAT problem is not satisfiable then none of the truth assignments encoded by a membrane labelled by 2 makes the formula ϕtrue. Thus, some object αj(1 ≤j≤p) will be within all membranes labelled by 2 will not remain in such membranes. At configuration C4n+p+1,wehaveC4n+p+1(1) = {δ4n+p+1}and in each membrane labelled by 2 there remain objects αjif the corresponding truth assignment does not make true clause Cj. In this step, only rules [ αjα p+1 ]2[] 0→[] 2[n1]0,for 1≤j≤pand rule [ δ4n+p+1 ]1[γ]0→[δ4n+p+2 ]1[] 0will be fired. Then, at configuration C4n+p+2 we have in the environmet 2ncopies of object n1, C4n+p+2(1) = {δ4n+p+2}and membranes labelled by 2 will contain objects αj (1 ≤j≤p) when clauses Cjare not satisfied by the corresponding truth assignment. In the (4n+p+ 3)-th step, rule [ ]2[n1]0→[n1]2[] 0will be fired. Here, objects n1will be sent to a membrane labelled by 2. Then, 4Let us note that a membrane containing an object n1does not say that the corresponding truth assignment does not makes true the input formula. In fact, we can have more than one object n1within a single membrane labelled by 2. 158 D. Orellana-Mart´ın et al. at configuration C4n+p+3 we have C4n+p+3(1) = {δ4n+p+2}and membranes labelled by 2 contain objects αj(1 ≤j≤p) if clause Cjis not satisfied by the corresponding truth assignment, and can contain tobjects n1(0 ≤t≤2n). At the (4n+p+4)-th step rule [ n1]2[δ4n+p+2 ]1→[n2]2[] 1is fired, since object δ4n+3 has not been consumed by any rule from 4.3, creating an object n2in a membrane labelled by 2. Then, at configuration C4n+p+4 we have C4n+p+4(1) = ∅and membranes labelled by 2 contain objects αj(1 ≤j≤p) if clause Cjis not satisfied by the corresponding truth assignment, and can contain tobjects n1(0 ≤t≤2n), and one of them contains an object n2. At the last step of the computation, rule [ n2]2[] 0→[] 2[no ]0is fired, sending an object no to the environment. Then, at configuration C4n+p+5 we have that C4n+p+5(1) = ∅ and membranes labelled by 2 contain objects αj(1 ≤j≤p) if clause Cjis not satisfied by the corresponding truth assignment, and can contain tobjects n1(0 ≤t≤2n), and there will be an object no in the environment. Here, the computation halts and returns a negative answer. Result Proof. The family of P systems previously constructed verifies the following: •Every system of the family Πis a recognizer P systems from TSEC(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 alphabet: 9n2p+6n2+3np2 2−3np + 22n+p2 2+13p 2+14 ∈ Θ(max{n2p, np2}). – Initial number of cells: 2 ∈Θ(1). – Initial number of objects in cells: n2+n(p+1)+p+3∈Θ(n2). – Number of rules: 8n3+27n2p 2+4n1+19np 2+ 23n+p2 2+17p 2+11∈Θ(n3). – 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 input formula ϕof 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 for each input formula ϕof SAT problem, the deterministic P system Π(s(ϕ)) + cod(ϕ) takes exactly 4n+p+5 steps, being nthe number of variables of ϕand pthe number of clauses. •The family Πis sound with regard to (X, cod, s): indeed, for each formula ϕ, 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 input formula ϕsuch that it is satisfiable, the computation of Π(s(ϕ)) + cod(ϕ)is an accepting computation.  Narrowing Frontiers of Efficiency 159 Corollary 1. NP ∪co −NP ⊆PMCTSEC(2,2). Proof. It suffices to notice that SAT problem is a NP-complete problem, SAT ∈ PMCTSEC(2,2), and the complexity class PMCTSEC(2,2) is closed under polynomialtime reduction and under complement.  6 Conclusions and future work In [6] a tight frontier of efficiency in the framework of tissue P systems with evolutional symport/antiport rules and cell separation is defined by the length of the RHS, that is, passing from 1 to 2 is enough to pass from non-efficiency to presumably efficiency while the length of the LHS is at least 3. This result is demonstrated giving a solution of the SAT problem by means of a family of P system from TSEC(3,2). But an open problem remains open here: what happens with P systems from TSEC(k,2) (k≥2)? Can we solve computationally hard problems restricting the length of the LHS to 2? In this paper, an efficient solution to the SAT problem is given by means of a family of P systems from TSEC(2,2), so the previous problem is solved. Then, we can conclude here with a similar figure to the presented in [6] but with the new results included. Of course, after this work we can define several clear research lines to continue investigating these kinds of P systems. – What happens when the environment “dissapear”? – Do the structure matter? By this we mean using cell-like structure with this kind of rules. – In [12] another definition of length is given. Let kbe the length of the rule defined as follows: if r≡[u]i[v]j→[v]i[u]j,k=|u|+|v|+|u|+|v|.Then the complexity class of tissue P systems with evolutional communication rules with at most length kand cell separation is denoted by PMCTSEC(k).What are the borderline here? – What is the upper bound of these systems? In [3] a characterization of tissue P systems with symport/antiport rules and both cell division and separation is given matching their efficiency to the class P#P, and it seems that this class of P system can reach the same complexity class. Acknoledgements This work was supported by Project TIN2017-89842-P of the Ministerio de Econom´ıa y Competitividad of Spain and by Grants No 61320106005 of the National Natural Science Foundation of China. 160 D. Orellana-Mart´ın et al. LHS RHS 1234567 1 2 3 4 5 6 7 P=PMCTSEC(k1,k2)NP ∪co −NP ⊆PMCTSEC(k1,k2) References 1. R. Guti´errez-Naranjo, M.J. P´erez-Jim´enez, M. Rius–Font. Characterizing tractability by tissue–like P systems. In R. Guti´errez–Escudero, M.A. Guti´errez–Naranjo, Gh. P˘aun, I. P´erez–Hurtado and A. Riscos N´u˜nez (eds.) Proceedings of the Seventh Brainstorming Week on Membrane Computing,F´enix Editora, Seville, 2009, pp. 169–180. 2. M. Ionescu, Gh. P˘aun, T. Yokomori. Spiking Neural P Systems. Fundamenta Informaticae,71, 2,3 (2006), 279–308. 3. A.Leporati,L.Manzoni,A.E.Porreca,C.Zandron.Characterisingthecomplexity of tissue P systems with fission rules. Journal of Computer and System Sciences,90 (2017), 115–128. 4. C. Mart´ın-Vide, Gh. P˘aun, J. Pazos, A. Rodr´ıguez-Pat´on. Tissue P systems. Theoretical Computer Science,296, Issue 2, 2003, 295–326. 5. L. Pan, M.J. P´erez-Jim´enez, A. Riscos-N´u˜nez, M. Rius-Font. New frontiers of the efficiency in tissue P systems. L. Pan, Gh. P˘aun, T. Song (eds.) Pre-proceedings of Asian Conference on Membrane Computing (ACMC 2012), Huazhong University of Science and Technology, Wuhan, China, October 15-18, 2012, pp. 61-73. 6. L. Pan, B. Song, L. Valencia-Cabrera, M.J. P´erez-Jim´enez. The computational complexity of tissue P systems with evolutional symport/antiport rules. Complexity,21 pages, 2018. 7. Gh. P˘aun. Computing with membranes. Journal of Computer and System Sciences, 61, 1 (2000), 108–143, and Turku Center for CS-TUCS Report No. 208, 1998 Narrowing Frontiers of Efficiency 161 8. M.J. P´erez-Jim´enez. An approach to computational complexity in Membrane Computing. In G. Mauri, Gh. P˘aun, M.J. P´erez-Jim´enez, G. Rozenberg, A. Salomaa (eds.). Membrane Computing, International Workshop, WMC5, Milano, Italy, 2004, Selected Papers, Lecture Notes in Computer Science,3365 (2005), 85-109. 9. M.J. P´erez-Jim´enez, ´ A. Romero-Jim´enez, F. Sancho-Caparrini. Complexity classes in models of cellular computing with membranes. Natural Computing,2, 3 (2003), 265–285. 10. M.J. P´erez-Jim´enez, P. Sos´ık. Improving the efficiency of tissue P systems with cell separation.InM.Garc´ıa-Quismondo, L.F. Mac´ıas-Ramos, Gh. P˘aun, I. P´erez- Hur- tado, L. Valencia-Cabrera (eds.) Proceedings of the Tenth Brainstorming Week on Membrane Computing, Volume II, Seville, Spain, January 30 - February 3, 2012, Report RGNC 01/2012, F´enix Editora, 2012, pp. 105-140. 11. A.E. Porreca, N. Murphy, M.J. P´erez-Jim´enez. An Optimal Frontier of the Efficiency of Tissue P Systems with Cell Division. In M.´ A. Mart´ınez-del-Amor, Gh. P˘aun, I. P´erez–Hurtado and F.J. Romero-Campero (eds.) Proceedings of the Tenth Brainstorming Week on Membrane Computing, Volume II, Seville, Spain, January 30 - February 3, 2012, Report RGNC 01/2012, F´enix Editora, 2012, 141–166. 12. B. Song, C. Zhang, L. Pan. Tissue-like P systems with evolutional symport/antiport rules. Information Sciences,378 (2017), 177-.193.