# The Computational Complexity of Tissue P Systems with Evolutional Symport/Antiport Rules

Authors: Linqiang Pan; Bosheng Song; Luis Valencia-Cabrera; Mario J. Pérez-Jiménez
Journal: Complexity
 (2018)

---

## Abstract

Tissue P systems with evolutional communication (symport/antiport) rules are computational models inspired by biochemical systems consisting of multiple individuals living and cooperating in a certain environment, where objects can be modified when moving from one region to another region. In this work, cell separation, inspired from membrane fission process, is introduced in the framework of tissue P systems with evolutional communication rules. The computational complexity of this kind of P systems is investigated. It is proved that only problems in classP can be efficiently solved by tissue P systems with cell separation with evolutional communication rules of length at most (n,1), for each natural number n≥1. In the case where that length is upper bounded by (3,2), a polynomial time solution to the SAT problem is provided, hence, assuming that P≠NP a new boundary between tractability andNP-hardness on the basis of the length of evolutional communication rules is provided. Finally, a new simulator for tissue P systems with evolutional communication rules is designed and is used to check the correctness of the solution to the SAT problem.


---

## Body

## 1. Introduction

A cell is the basic unit of biological organization that constitutes all living organisms. There are many different types of biological cells, which have different specialized functions that maintain an organism working properly. Inspired by the structure and functioning of living cells, Păun proposed a computing paradigm in 2000 [1], calledmembrane computing, which has become an active research area (for other research domains of natural computing, one can refer to [2, 3]). A large number of theoretical models were proposed [4–6] and they have been used to solve various real problems [7–10]. These distributed and parallel computation models investigated in membrane computing are calledP systems. In general, there exist two main families of P systems:cell-like P systems [1], which have a hierarchical arrangement of membranes described by a rooted tree (corresponding to cell-like membrane structure), andtissue-like P systems [11] orneural-like P systems [12], which have a net of cells or neurons described by a directed graph. An overview of membrane computing can be found in [13]. The present work deals with tissue-like P systems.Inspired by the biological phenomenon of trans-membrane transport of couples of chemicals, communication P systems with symport/antiport rules were proposed in [14], where symport rules move objects (without evolution) between two regions in one direction, and antiport rules move objects (without evolution) between two regions in opposite directions. Later, symport/antiport rules were considered in tissue-like P systems [11], where cells are placed in nodes of a directed graph, and an arc between two nodes corresponds to a communication channel between cells placed in these nodes.Since the notion of tissue P systems was proposed, numerous research topics have been arisen [15–18], and various ingredients (energy, catalyst, mitosis, etc.) from other computational models were considered in the context of tissue P systems. In [19], tissue P systems with channel states controlling the communication between two regions were proposed, and several Turing universality results were achieved, where the systems work in a maximally parallel way with sequential behavior on channels. In [20], a general model of tissue P systems with channel states that allow us to model hybrid cooperating grammar systems was considered, where the results were established for strings and arrays.Tissue P systems have been used to find polynomial time solutions toNP-complete problems. In [21], membrane division rules used in P systems with active membranes have been introduced into tissue P systems yielding tissue P systems with cell division, and a polynomial time uniform solution to the SAT problem was shown. Since then, tissue P systems with cell division were also considered to solve otherNP-complete problems: bin packing [22], subset sum [23], vertex cover [24], and so on. Cell division rules have a replication functioning; that is, two new created cells by a division rule have exactly the same objects except for at most a pair of different objects. Inspired from membrane fission process, cell separation rules are another way to obtain an exponential workspace in polynomial time, but they do not have the duplication functioning; that is, when a cell is separated, the objects in the cell are distributed in each of the newly created cells. Tissue P systems with cell separation have also been used to solveNP-complete problems in polynomial time; one can refer to [25, 26] for these investigations.Computational complexity theory in the framework of tissue P systems was introduced in [21] and it has been studied in [27–30]. It was shown that in the framework of tissue P systems with cell division, only tractable problems can be efficiently solved by using communication rules with length at most one [31] (the length of such a rule is the total number of objects involved in it), but a uniform polynomial time solution to the HAM-CYCLE problem by a family of such P systems using communication rules with length at most two has been given [30]. On the other hand, in the framework of tissue P systems with cell separation, by using communication rules with length at most two, only tractable problems can be efficiently solved, but the SAT problem can be solved by this kind of P systems using communication rules with length at most three [26]. Moreover, frontiers between efficiency and nonefficiency in terms of the length of symport/antiport rules in the framework of cell-like P systems have been investigated in [32].Tissue-like P systems with evolutional symport/antiport rules (TESA P systems, for short) were proposed in [33], where objects are moved from one region to another region and may be evolved during this process. In [33], the computational efficiency of TESA P systems with cell division (TESAD P systems, for short) was investigated. It is shown that a limit on the efficiency of TESAD P systems is provided with evolutional communication rules of length at most 2. However, when using evolutional communication rules of length at most 4, the SAT problem can be solved by TESAD P systems. However, it is still an open problem as formulated in [33] related to the role of evolutional communication rules in tissue P systems with cell separation from a computational complexity point of view.During those computational complexity studies for new variants of P systems, the solutions designed for NP-complete problems are frequently difficult to follow, and requerying makes sure that the evolution of the systems is exactly as expected. In this context, the aid of computer tools to assist in both the design and verification tasks may be crucial, producing much more reliable solutions. In this sense, the development ofP-Lingua [34–36] implied a significant progress. This open source framework includes a standard language aiming to specify the elements of different types of P systems using a notation very close to the researchers in membrane computing community. Besides, it contains simulation engines for a number of P system types. On top of that, MeCoSim [37, 38] provides an additional layer of abstraction with a visual application where researchers can explore at a higher level the evolution of their solutions based on P systems.In this work, we investigate tissue P systems with evolutional symport/antiport rules and cell separation (TESAS P systems, for short) from a computational complexity point of view.Contributions of the present work are summarized as follows:(a)
A variant of tissue P systems with evolutional symport/antiport rules, calledtissue P systems with evolutional symport/antiport rules and cell separation (TESAS P systems, for short), and the corresponding recognizer version are proposed. In TESAS P systems, the length of an evolutional symport/antiport rule r is defined as an ordered pair whose first component is the total number of objects involved in the left hand side (LHS) of the rule and the second component is the total number of objects involved in the right hand side (RHS) of the rule; that is, length(r)=(length(LHS(r)),length(RHS(r))). The set of all recognizer TESAS P systems with evolutional communication rules of length at most (k1,k2) is denoted byTSEC(k1,k2).(b)
The computation efficiency of recognizer TESAS P systems is investigated in terms of the length of evolutional communication rules. It is shown that only tractable problems can be efficiently solved by families of systems fromTSEC(n,1) or fromTSEC(1,n), for each natural number n≥1. We further show that the SAT problem can be solved in polynomial time by a family of systems fromTSEC(3,2), hence, assuming that P≠NP, a new boundary between tractability andNP-hardness on the basis of the length of evolutional communication rules, is provided.(c)
A new simulatorMeCoSim is designed in order to check the correctness of the solution to the SAT problem. By using the software MeCoSim, we can analyse the designed P systems, then run the simulation, and obtain the computation results.


## 2. Tissue P Systems with Evolutional Symport/Antiport Rules and Cell Separation

Let us start this section by recalling some notions from formal language theory used in this work; the reader can find details in [39].An alphabetΓ is a nonempty set. Any sequence u of elements from Γ is called astring over Γ. Thelength of u, denoted by u, is the number of occurrences in u of symbols from Γ.Amultiset over an alphabet Γ is a function m from Γ to the set of natural numbers N. The multiplicity of a symbol a∈Γ in the multiset m is m(a). Thesupport of m is the set of symbols a such that m(a)>0. A multiset is finite and its support is a finite set. The set of all finite multisets over Γ is denoted by Mf(Γ), and by Mf+(Γ) we denote the set of all nonempty finite multisets over an alphabet Γ, and the empty multiset is denoted by ∅. The cardinal of a finite multiset m, denoted by m, is the sum of all multiplicities of elements in the support of m. If m1 and m2 are multisets over Γ, then we define the union of m1 and m2, denoted by m1+m2, as follows: (m1+m2)(a)=m1(a)+m2(a), for each a∈Γ.Definition 1.
A tissue P system with evolutional symport/antiport rules and cell separation of degreeq≥1 is a tuple (1)Π=Γ,Γ0,Γ1,E,M1,…,Mq,R,iout,where (i)
Γ and E are finite alphabets such that E⊆Γ;(ii)
Γ0, Γ1 are nonempty sets such that Γ0∪Γ1=Γ and Γ0∩Γ1=∅;(iii)
M1,…,Mq are multisets over Γ;(iv)
R is a finite set of rules of the following forms:
(1)
evolutional communication rules:
(a)
[u]i[]j→[]i[u′]j, where 0≤i,j≤q, i≠j, u∈Mf+(Γ), u′∈Mf(Γ) (evolutional symport rules);(b)
[u]i[v]j→v′iu′j, where 0≤i,j≤q, i≠j, u,v∈Mf+(Γ), u′,v′∈Mf(Γ) (evolutional antiport rules);(2)
separation rules:
(a)
ai→Γ0iΓ1i, where i∈{1,…,q}, i≠iout, a∈Γ;(v)
iout∈{0,1,…,q}.A tissue P system with evolutional symport/antiport rules and cell separation of degreeq≥1, Π=(Γ,Γ0,Γ1,E,M1,…,Mq,R,iout), can be viewed as a set of q cells, labelled by 1,…,q such that (a) M1,…,Mq represent the multisets of objects initially placed in the q cells 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; and (c) iout represents a distinguishedregion which will encode the output of the system. We use the termregioni (0≤i≤q) to refer to cell i in the case 1≤i≤q and to refer to the environment in the case i=0.Aconfiguration at any instant of a TESAS P system is described by 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,iout) is (M1,…,Mq,∅).An evolutional symport ruleui[]j→[]i[u′]j is enabled at a configuration Ct at an instant t if there is a region i from Ct which contains multiset u. By applying an evolutional symport rule, the multiset of objects u in region i from Ct is consumed and the multiset of objects u′ is generated in region j from Ct+1. An evolutional antiport rule ui[v]j→[v′]i[u′]j is enabled at a configuration Ct at an instant t if there is a region i from Ct which contains multiset of objects u and a region j from Ct which contains multiset of objects v. By applying an evolutional antiport rule, (a) the multiset of objects u in region i from Ct and the multiset of objects v in region j from Ct are consumed; (b) the multiset of objects u′ is generated in region j from configuration Ct+1; and (c) the multiset of objects v′ is generated in region i from configuration Ct+1. The length of an evolutional symport/antiport rule r is an ordered pair of natural numbers: length(r)=(length(LHS(r)),length(RHS(r))).A separation ruleai→[Γ0]i[Γ1]i is enabled at a configuration Ct at an instant t if there is a cell i from Ct which contains object a and i≠iout. By applying a separation rule to a such a cell i, (a) object a is consumed from such cell; (b) two new cells with label i are generated at configuration Ct+1; (c) in the original cell i, the objects from Γ0 are placed in one of the new cells, while the other objects from Γ1 are placed in another one.The rules of a TESAS P system are applied in a maximally parallel manner, and we have the restriction that when a celli is separated at one transition step, no other rules can be applied for that cell i at that step.A transition from a configurationCt to another configuration Ct+1 is obtained by applying rules in a maximally parallel manner following the previous remarks. Acomputation 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 is obtained from the previous configuration in one transition step. If the sequence is finite (calledhalting computation) then the last term of the sequence is ahalting configuration, that is, a configuration where no rule is applicable to it. A computation gives a result only when an 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; one can refer to [21, 29] for further details.Definition 2.
A recognizer tissue P system with evolutional symport/antiport rules and cell separation of degreeq≥1 is a tuple (2)Π=Γ,Γ0,Γ1,E,Σ,M1,…,Mq,R,iin,iout,where(i)
the tuple(Γ,Γ0,Γ1,E,M1,…,Mq,R,iout) is a TESAS P system of degree q≥1, where Γ strictly contains an (input) alphabet Σ and two distinguished objects yes, no, and Mi (1≤i≤q) are multisets over Γ∖Σ;(ii)
iin∈{1,…,q} is the input cell and iout is the label of the environment;(iii)
for each multisetm over the input alphabet Σ, any computation of the system Π with input m starts from the configuration of the form (M1,…,Miin+m,…,Mq;∅) andalways halts and either object yes or object no (but not both) must appear in the environment at the last step.It is worth pointing out that, in any recognizer TESAS P systems, all computations halt. Then, any symport rule of the type[u]0[]j→[]0[u′]j must verify the following condition: multiset u contains some object from Γ∖E.For each ordered pair of natural numbers(k1,k2) greater than or equal to 1, the class of recognizer TESAS P systems with cell separation and with evolutional communication rules of length at most (k1,k2) is denoted by TSEC(k1,k2). This means that the LHS (resp., RHS) of any evolutional communication rule in a system from TSEC(k1,k2) involves at most k1 objects (resp., k2 objects).Next, we define the concept of solving a problem in a uniform way and in polynomial time by a family of recognizer TESAS P systems (see [40] for details).Definition 3.
A decision problemX=(IX,θX) is solvable in a uniform way and in polynomial time by a family Π=(Π(n))n∈N of recognizer TESAS P systems if the following conditions hold:(i)
the familyΠ is polynomially uniform by Turing machines;(ii)
there exists a polynomial encoding(cod,s) of IX in Π 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) for each n∈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 TESAS P systems with evolutional communication rules of length at most(k1,k2) in a uniform way and polynomial time is denoted by PMCTSEC(k1,k2).


## 3. The Computational Complexity of Tissue P Systems with Evolutional Symport/Antiport Rules

### 3.1. The Limitation on the Efficiency ofTSEC(2,1)

In this subsection, we use tissue P systems with cell separation and evolutional communication rules of length at most(2,1) to provide a new characterization of the classical complexity class P.The proof uses a similar technique as in [32]. Firstly, some representations of TESAS P systems Π=(Γ,Γ0,Γ1,E,Σ,M1,…,Mq,R,iin,iout) from TSEC(2,1) are given. By RC (resp., RS) we denote the set of communication rules (resp., separation rules) of Π. We will fix a total order in RC and a total order in RS. Because several cells with the same label are generated by using separation rules, in order to identify the different cells with the same label, the following recursive definition is used to modify the labels of the new generated cells:(i)
We denote the label of a cell as a pair(i,σ), where 1≤i≤q and σ∈{0,1} is a binary string.(ii)
If a separation rule is applied to a cell with label(i,σ), then the new created two cells will be labelled by (i,σ0) and (i,σ1), respectively. We mention that, for the system during any computation, we consider a lexicographical order over the set of labels of cells.Note that if communication rules occur in two cells, then the labels of these two cells do not change.A configuration at an instantt of a tissue P system from TSEC(2,1) is described by the multisets of objects over Γ contained in each cell and the multiset of objects over Γ∖E in the environment. Hence, a configuration of Π can be described as follows: (3)a,i,σ∣a∈Γ∪λ,1≤i≤q,σ∈0,1∗∪a,0∣a∈Γ∖E.Letr=[ab]i[]j→[]icj, 1≤i,j≤q, be an evolutional symport rule of Π and n∈N. We denote by n·LHS(r,(i,σi),(j,σj)) the multiset of objects (a,i,σi)n(b,i,σi)n and the corresponding n·RHS(r,(i,σi),(j,σj)) the multiset of objects (c,j,σj)n. In a similar way, n·LHS(r,(i,σi),(j,σj)) and n·RHS(r,(i,σi),(j,σj)) are defined when r is of the form [a]i[]j→[]i[c]j.Letr=[ab]i[]j→[]i[λ]j, 1≤i,j≤q, be an evolutional symport rule of Π and n∈N. We denote by n·LHS(r,(i,σi),(j,σj)) the multiset of objects (a,i,σi)n(b,i,σi)n, and the corresponding n·RHS(r,(i,σi),(j,σj)) is ∅. In a similar way, n·LHS(r,(i,σi),(j,σj)) and n·RHS(r,(i,σi),(j,σj)) are defined when r is of the form [a]i[]j→[]i[λ]j.Letr=[ab]0[]j→[]0[c]j, 1≤j≤q, be an evolutional symport rule of Π and n∈N. We denote by n·LHS(r,(j,σj),0) the multiset of objects (4)a,0nb,0n,ifa,b∈Γ∖E;a,0n,ifa∈Γ∖E,b∈E;b,0n,ifb∈Γ∖E,a∈E;∅,otherwise;and we denote by the corresponding n·RHS(r,(j,σj),0) the multiset of objects (c,j,σj)n. In a similar way, n·LHS(r,(j,σj),0) and n·RHS(r,(j,σj),0) are defined when r is of the form [a]0[]j→[]0[λ]j.Letr=[ab]0[]j→[]0[λ]j, 1≤j≤q, be an evolutional symport rule of Π and n∈N. We denote by n·LHS(r,(j,σj),0) the multiset of objects (5)a,0nb,0n,ifa,b∈Γ∖E;a,0n,ifa∈Γ∖E,b∈E;b,0n,ifb∈Γ∖E,a∈E;∅,otherwise.The corresponding n·RHS(r,(j,σj),0) is ∅. In a similar way, n·LHS(r,(j,σj),0) and n·RHS(r,(j,σj),0) are defined when r is of the form [a]0[]j→[]0[λ]j.Letr=[a]i[b]j→[c]i[λ]j, 1≤i,j≤q, be an evolutional antiport rule of Π and n∈N. We denote by n·LHS(r,(i,σi),(j,σj)) the multiset of objects (a,i,σi)n(b,j,σj)n and the corresponding n·RHS(r,(i,σi),(j,σj)) the multiset of objects (c,i,σi)n. In a similar way, n·LHS(r,(i,σi),(j,σj)) and n·RHS(r,(i,σi),(j,σj)) are defined when r is of the form [a]i[b]j→[λ]i[c]j.Letr=[a]i[b]j→[λ]i[λ]j, 1≤i,j≤q, be an evolutional antiport rule of Π and n∈N. We denote by n·LHS(r,(i,σi),(j,σj)) the multiset of objects (a,i,σi)n(b,j,σj)n, and the corresponding n·RHS(r,(i,σi),(j,σj)) is ∅.Letr=[a]0[b]j→[c]0[λ]j, 1≤j≤q, be an evolutional antiport rule of Π and n∈N. We denote by n·LHS(r,(j,σj),0) the multiset of objects (6)a,0nb,jn,ifa∈Γ∖E;b,jn,otherwise;and we denote by the corresponding n·RHS(r,(j,σj),0) the multiset of objects (7)c,0n,ifc∈Γ∖E;∅,otherwise.Letr=[a]0[b]j→[λ]0[c]j, 1≤j≤q, be an evolutional antiport rule of Π and n∈N. We denote by n·LHS(r,(j,σj),0) the multiset of objects (8)a,0nb,jn,ifa∈Γ∖E;b,jn,otherwise;and we denote by the corresponding n·RHS(r,(j,σj),0) the multiset of objects (c,j,σj)n.Letr=[a]0[b]j→[λ]0[λ]j, 1≤j≤q, be an evolutional antiport rule of Π and n∈N. We denote by n·LHS(r,(j,σj),0) the multiset of objects (9)a,0nb,jn,ifa∈Γ∖E;b,jn,otherwise.The corresponding n·RHS(r,(j,σj),0) is ∅.IfCt is a configuration of Π, then the multiset obtained by replacing in Ct every occurrence of (x,i,σ) by (x,i,σ′) is denoted by Ct+{(x,i,σ)/σ′}. Moreover, we denote by Ct+m (resp., Ct∖m) a multiset m of labelled objects added to (resp., removed from) the configuration Ct.Next, we show that TESAS P systems fromTSEC(2,1) can only solve tractable problems.IfC={Ct}t<r+1 of Π (r∈N) is a halting computation, then we denote by C=r the length of C. For each i(1≤i≤q), the multiset of objects over Γ contained in all cells labelled by i at configuration Ct is denoted by Ct(i). We denote by Ct(0) the multiset of objects over Γ∖E contained in the environment at configuration Ct. Finally, the finite multiset Ct(0)+Ct(1)+⋯+Ct(q) is denoted by Ct∗.Lemma 4.
LetΠ=(Γ,Γ0,Γ1,E,Σ,M1,…,Mq,R,iin,iout) be a recognizer tissue P system of degree q≥1 from TSEC(2,1). Let M=M1+⋯+Mq and let C={C0,…,Cr} be a computation of Π. Then, one has(1)
C0∗=M, and for each t, 0≤t<r, Ct+1∗≤Ct∗;(2)
for eacht, 0≤t≤r, Ct∗≤M;(3)
the number of created cells along the computationC by the application of cell separation rules is bounded by 2M.Proof.
(1) Let us notice that(10)C0∗=C00+C01+⋯+C0q=M1+⋯+Mq=M.Let Π be a recognizer tissue P system from TSEC(2,1) and let R be the set of rules associated with Π, which contains the following types of evolutional communication rules:(a)
[ab]i[]j→[]i[c]j, (i=0∧{a,b}⊈E) or (i≠0∧{a,b}⊆Γ);(b)
[ab]i[]j→[]i[λ]j, (i=0∧{a,b}⊈E) or (i≠0∧{a,b}⊆Γ);(c)
[a]i[b]j→[c]i[λ]j, {a,b}⊆Γ;(d)
[a]i[b]j→[λ]i[c]j, {a,b}⊆Γ;(e)
[a]i[b]j→[λ]i[λ]j, {a,b}⊆Γ;(f)
[a]i[]j→[]i[b]j, (i=0∧a∈Γ∖E) or (i≠0∧a∈Γ);(g)
[a]i[]j→[]i[λ]j, (i=0∧a∈Γ∖E) or (i≠0∧a∈Γ).
For eacht, 0≤t<r, in the transition from configuration Ct to configuration Ct+1, by using any rules of types from (a) to (g), at least one object from Ct is consumed and at most one object is produced in Ct+1. Hence, in any transition step the number of objects in the system is not increased.
(2) By induction ont, let us start analyzing the basic case t=0. The result is trivial because of C0∗=M. By induction hypothesis, let us suppose the result holds for t, 0≤t<r. Then, (11)Ct+1∗≤1Ct∗≤h.i.M.Hence, the result is also true for t+1.
(3) According to the fact that the application of a cell separation rule consumes an object and produces two new cells, result (3) can be obtained from (2) easily.Next, a deterministic algorithmA working in polynomial time is presented, which receives as input a P system Π from TSEC(2,1) and an input multiset m of Π, in such manner that algorithm A reproduces the behaviour of a computation of Π+m. If the system Π is confluent, then the algorithm A will provide the same answer of Π. We give Pseudocode 1 of the algorithm A to describe the simulation process.Pseudocode 1
Input: A P system  Π  from  TSEC(2,1)  and an input multiset  m Initialization phase: C0  is the initial configuration of  Π+m t ← 0 while  Ct  is a non-halting configuration  do Selection phase: Input  Ct,Output  (Ct′,A) Execution phase: Input  (Ct′,A), Output  Ct+1 t ← t + 1 end while Output: Yes  if  Π+m  has an accepting computation,  No  otherwiseThe algorithmA receives a recognizer tissue P system(12)Π=Γ,Γ0,Γ1,E,Σ,M1,…,Mq,R,iin,ioutfrom TSEC(2,1) and an input multiset m. Let M=M1+⋯+Mq. Let any computation of Π perform at most p (p is a natural number) transition steps. Hence, from Lemma 4, the number of cells in the system along any computation is bounded by 2M+q.A transition of a recognizer tissue P systemΠ+m is performed in two phases: selection phase and execution phase (see Algorithms 1 and 2). For the detailed information of a transition of such P system, one can refer to [32].Algorithm 1:Selection phase.
Input:  A configuration  Ct  of  Π+m  at instant  t C t ′ ← C t  ;  A ← ∅  ;  B ← ∅ for  r=[u]i[v]j→[v′]i[u′]j∈RC, according to the order chosen  do for  each pair of cells  (i,σi),(j,σj)  of  Ct′  according tothe lexicographical order  do n r ←  maximum number of times that  r  is applicable to  (i,σi), ( j , σ j ) if  nr>0  then C t ′ ← C t ′ - n r ⋅ L H S ( r , ( i , σ i ) , ( j , σ j ) ) A ← A ∪ { ( r , n r , ( i , σ i ) , ( j , σ j ) ) } B ← B ∪ { ( i , σ i ) , ( j , σ j ) } end if end for end for for  r=[u]i[v]0→[v′]i[u′]0∈RC  according to the order chosen  do for  each cell  (i,σi)  of  Ct′  according to the lexicographical order  do n r ←  maximum number of times that  r  is applicable to  (i,σi) if  nr>0  then C t ′ ← C t ′ - n r ⋅ L H S ( r , ( i , σ i ) , 0 ) A ← A ∪ { ( r , n r , ( i , σ i ) , 0 ) } B ← B ∪ { ( i , σ i ) } end if end for end for for  r=[a]i→[Γ0]i[Γ1]i∈RS  according to the order chosen  do for  each  (a,i,σi)∈Ct′  according to the lexicographical order, and  such that  (i,σi)∉B  do C t ′ ← C t ′ ∖ { ( a , i , σ i ) } A ← A ∪ { ( r , 1 , ( i , σ i ) ) } end for end forAlgorithm 2:Execution phase.
Input:  The output(Ct′,A)of the selection phase for  each(r,nr,(i,σi),(j,σj))∈Ado C t ′ ← C t ′ + n r ⋅ R H S ( r , ( i , σ i ) , ( j , σ j ) ) end for for  each  ( r , n r , ( i , σ i ) , 0 ) ∈ A  do C t ′ ← C t ′ + n r ⋅ R H S ( r , ( i , σ i ) , 0 ) end for for  each  ( r , 1 , ( i , σ i ) ) ∈ A  do C t ′ ← C t ′ + { ( λ , i , σ i ) / σ i 0 } C t ′ ← C t ′ + { ( λ , i , σ i 1 ) } for  each  ( x , i , σ i ) ∈ C t ′  according to the lexicographical order  do if  x ∈ Γ 0  then C t ′ ← C t ′ + { ( x , i , σ i ) / σ i 0 } else C t ′ ← C t ′ + { ( x , i , σ i ) / σ i 1 } end if end for end for C t + 1 ← C t ′It is easy to check that Algorithm1 is deterministic and the running time of this algorithm is polynomial in the size of Π because the number of cycles of the first main loopfor is of order O(R·M2·q2); the number of cycles of the second main loopfor is of order O(R·M·q); and the number of cycles of the third main loopfor is of order O(R·M·q·Γ).Algorithm2 is deterministic and the running time of this algorithm is polynomial in the size of Π because the number of cycles of the first main loopfor is of order O(R·M2·q2); the number of cycles of the second main loopfor is of order O(R·M·q); and the number of cycles of the third main loopfor is of order O(R·M·q·Γ).Theorem 5.
One hasP=PMCTSEC(2,1).Proof.
BecausePMCTSEC(2,1) is closed under polynomial time reduction and nonempty, hence P⊆PMCTSEC(2,1). In what follows, we show that CTSEC(2,1)⊆P. Let X∈PMCTSEC(2,1) and let Π={Πn∣n∈N} be a family of recognizer tissue P systems fromTSEC(2,1) solving X according to Definition 3. Let (cod,s) be a polynomial encoding associated with that solution. If u∈IX is an instance of the problem X, then u will be processed by the system Π(s(u))+cod(u). We consider the deterministic algorithm A′ as shown in Algorithm 3.
The algorithmA′ receives an instance u of the decision problem X=(IX,θX), working in a polynomial time. The following three assertions are equivalent:(i)
θX(u)=1; that is, the answer of problem X to instance u is affirmative.(ii)
Every computation ofΠ(s(u))+cod(u) is an accepting computation.(iii)
The output of the algorithmA′ with input u is Yes.
Hence,X∈P.Algorithm 3
Input:  an instance  u  of the problem  X Construct the system  Π(s(u))+cod(u) Run algorithm  A  with input  Π(s(u))+cod(u) Output:  Yes if  Π(s(u))+cod(u)  has an accepting computation No otherwiseCorollary 6.
For eachn∈N, n≥1, one has PMCTSEC(n,1)=P.Proof.
Indeed, it suffices to notice that, at any transition step, the application of each rule consumes at least one object fromΓ∖E and produces at most one object from Γ. Thus, along any computation of the system, the total number in it is not increased.Theorem 7.
For eachn∈N, n≥1, one has PMCTSEC(1,n)=P.Proof.
In [31], it was shown that the class of decision problems solvable in polynomial time by means of families of tissue P systems with cell division and symport rules with length 1 is equal to classP. Bearing in mind that systems from TSEC(1,n) are noncooperative ones, the dependency graph technique used in the cited paper can be used to obtain the result, in a similar way.


### 3.2. An Efficient Solution to the SAT Problem by P Systems inTSEC(3,2)

TheSAT problem is a well-knownNP-complete problem; here we give an efficient solution to the SAT problem by a family of tissue P systems with evolutional communication rules of length at most (3,2).Theorem 8.
One hasSAT  ∈PMCTSEC(3,2).Proof.
We provide a polynomial time uniform solution to theSAT problem [41] by a family of recognizer tissue P systems Π={Π(t)∣t∈N} from TSEC(3,2). Each system Π(t) (t=〈n,m〉=((n+m)(n+m+1)/2)+n) can process all Boolean formula φ in conjunctive normal form with n variables and m clauses.
For eachn,m∈N, we consider the recognizer tissue P system (13)Πn,m=Γ,Γ0,Γ1,E,Σ,M1,M2,M3,R,iin,iout,where(14)Γ=Σ∪E∪Ai,Ai′,A¯i,A¯i′,A^i,A^i′,Bi,Bi′,B¯i,B¯i′,B^i,B^i′,C¯i,Ti,T¯i,Ti′,Fi,F¯i,Fi′,ai,ai′,bi,bi′,ci,ti,fi,hi,yi,si,vi,wi,zi∣1≤i≤n∪D¯i,j,qi,j,ri,j,ui,j∣1≤i,j≤n∪D¯i,n+1∣1≤i≤n+1∪gi,j,k,g¯i,j,k∣1≤i,k≤n,1≤j≤m∪Ei,j,E¯i,j,ei,j,e¯i,j,lj,i∣1≤i≤n,1≤j≤m∪lj,l¯j,lj,0,Ej∣1≤j≤m∪An+1,A¯n+1,An+1′,Bn+1,B¯n+1,Bn+1′,C¯n+1,Em+1,S,p,yes,no,Γ1=Ti′,Fi′∣1≤i≤n∪Ai′,Bi′∣2≤i≤n+1,Γ0=Γ∖Γ1,Σ=xi,j,x¯i,j∣1≤i≤n,1≤j≤m,E=A~i,B~i,a¯i,a~i,b¯i,b~i,c¯i,c~i,d~i,f¯i,s~i,t¯i,v¯i,v~i,n+1,w~i,y¯i,y~i,z~i∣1≤i≤n∪r¯i,j,r~i,j,u~i,j,v~i,j∣1≤i,j≤n∪gi,j,k′,g¯i,j,k′∣1≤i≤n,1≤j≤m,0≤k≤n∪l¯j,k∣1≤j≤m,0≤k≤n∪αi∣0≤i≤4n+3m+4∪E0,M1=A1,B1,M2=A¯1,B¯1,C¯1,D¯1,1,M3=l1,0,…,lm,0,α0,p,iin=3istheinputcell,iout=0istheoutputregion,and the set R of rules consists of the following rules:(15)r1,i≡Ai1A¯i2⟶A¯i1A^i2,1≤i≤n,r2,i≡Ai′1A¯i2⟶A¯i′1A^i′2,1≤i≤n,r3,i≡Bi1B¯i2⟶B¯i1B^i2,1≤i≤n,r4,i≡Bi′1B¯i2⟶B¯i′1B^i′2,1≤i≤n,r5,i≡C¯i2v¯i0⟶vi20,1≤i≤n,r6,i,j≡D¯i,j2v~i,j0⟶qi,j20,1≤i,j≤n,r7,i≡Ti1ti2⟶ti12,1≤i≤n,r8,i≡Ti′1ti2⟶ti12,1≤i≤n,r9,i≡Fi1fi2⟶fi12,1≤i≤n,r10,i≡Fi′1fi2⟶fi12,1≤i≤n,r11,i≡A¯i1A~i0⟶aiai′10,1≤i≤n,r12,i≡A¯i′1A~i0⟶aiai′10,2≤i≤n,r13,i≡B¯i1B~i0⟶bibi′10,1≤i≤n,r14,i≡B¯i′1B~i0⟶bibi′10,2≤i≤n,r15,i≡A^i2A~i0⟶Ai20,1≤i≤n,r16,i≡A^i′2A~i0⟶Ai′20,2≤i≤n,r17,i≡B^i2B~i0⟶Bi20,1≤i≤n,r18,i≡B^i′2B~i0⟶Bi′20,2≤i≤n,r19,i≡vi2y¯i0⟶yi220,1≤i≤n,r20≡q1,12r¯1,10⟶r1,120,r21,i,j≡qi,j2r¯i,j0⟶ri,j220,1≤i≤n,2≤j≤n,r22,i≡ti1t¯i0⟶TiTi′10,1≤i≤n,r23,i≡fi1f¯i0⟶FiFi′10,1≤i≤n,r24,i≡Ai2c¯i0⟶ci20,1≤i≤n,r25,i≡Ai′2c~i0⟶ci20,2≤i≤n,r26,i≡Bi2c¯i0⟶ci20,1≤i≤n,r27,i≡Bi′2c~i0⟶ci20,2≤i≤n,r28,i≡ai1a¯i0⟶TiAi+110,1≤i≤n,r29,i≡ai′1a~i0⟶Fi′Ai+1′10,1≤i≤n,r30,i≡bi1b¯i0⟶Bi+1S10,1≤i≤n,r31,i≡bi′1b~i0⟶Bi+1′10,1≤i≤n,r32,i≡yi2y~i0⟶ziwi20,1≤i≤n,r33,i,j≡ri,j2r~i,j0⟶siui,j20,1≤i,j≤n,r34,i≡wi2w~i0⟶A¯i+120,1≤i≤n,r35,i≡ci2d~i0⟶B¯i+120,1≤i≤n,r36,i≡zi2z~i0⟶C¯i+120,1≤i≤n,r37,i≡si2s~i0⟶tifi20,1≤i≤n,r38,j≡u1,j2u~1,j0⟶D¯1,j+1D¯2,j+120,1≤j≤n,r39,i,j≡ui,j2u~i,j0⟶D¯i+1,j+120,2≤i,j≤n,r40≡S1⟶Γ01Γ11,r41,i≡D¯i,n+12v~i,n+10⟶hi220,1≤i≤n,r42≡An+11A¯n+12⟶E112,r43≡An+1′1B¯n+12⟶E112,r44,i≡TiTi′1hi2⟶T¯i12,1≤i≤n,r45,i≡FiFi′1hi2⟶F¯i12,1≤i≤n,r46,i,j≡xi,j3gi,j,0′0⟶gi,j,1230,1≤i≤n,1≤j≤m,r47,i,j≡x¯i,j3g¯i,j,0′0⟶g¯i,j,1230,1≤i≤n,1≤j≤m,r48,i,j,k≡gi,j,k3gi,j,k′0⟶gi,j,k+1230,1≤i≤n,1≤j≤m,1≤k≤n-1,r49,i,j,k≡g¯i,j,k3g¯i,j,k′0⟶g¯i,j,k+1230,1≤i≤n,1≤j≤m,1≤k≤n-1,r50,i,j≡gi,j,n3gi,j,n′0⟶ei,j30,1≤i≤n,1≤j≤m,r51,i,j≡g¯i,j,n3g¯i,j,n′0⟶e¯i,j30,1≤i≤n,1≤j≤m,r52,j,k≡lj,k3l¯j,k0⟶lj,k+1230,1≤j≤m,0≤k≤n-1,r53,j≡lj,n3l¯j,n0⟶lj30,1≤j≤m,r54,i,j≡T¯iEj1ei,j3⟶Ei,j13,1≤i≤n,1≤j≤m,r55,i,j≡F¯iEj1e¯i,j3⟶E¯i,j13,1≤i≤n,1≤j≤m,r56,i,j≡Ei,j1lj3⟶li,j1Ei,j3,1≤i≤n,1≤j≤m,r57,i,j≡E¯i,j1lj3⟶l¯i,j1E¯i,j3,1≤i≤n,1≤j≤m,r58,i,j≡li,j1Ei,j3⟶T¯iEj+113,1≤i≤n,1≤j≤m,r59,i,j≡l¯i,j1E¯i,j3⟶F¯iEj+113,1≤i≤n,1≤j≤m,r60,i≡αi3α¯i0⟶αi+130,0≤i≤4n+3m+3,r61≡Em+11p3⟶1yes3,r62≡yes30⟶3yes0,r63≡α4n+3m+4p30⟶3no0.
We consider a propositional formulaφ=C1∧⋯∧Cm, which contains m (m≥1) clauses, Ci=yi,1∨⋯∨yi,pi, for pi≥1, and yi,j∈{xk,¬xk∣1≤k≤n}, for 1≤i≤m, 1≤j≤pi.
Let(cod,s) be a polynomial encoding of instances from SAT in Π, where s(φ)=〈n,m〉 and cod(φ)={xi,j∣xi∈Cj}∪{x¯i,j∣¬xi∈Cj}. So the propositional formula φ will be processed by the system Π(s(φ))+cod(φ).
An instance of theSAT problem is solved by the system Π(s(φ))+cod(φ), which can be separated into three phases: generation phase, checking phase, and output phase.
Generation Phase. In this phase, by using separation rules in cell with label 1, all truth assignments for the variables associated with the Boolean formula φ(x1,…,xn) will be generated. When this phase completes, there are 2n copies of cell with label 1 such that each of them encodes a different truth assignment of variables {x1,…,xn}.
The generation phase takes4n+3 steps, which has two parallel processes. On the one hand, n loops are executed, and each loop takes four steps. When the loops are completed, three additional steps are executed. On the other hand, there is a counter object α in cell 3 that evolves from α0 to α4n+3m+3, and objects (cod(φ))e2n, (lj)2n (1≤j≤m) are produced in cell 3 after n+1 steps at this phase.
In the initial configuration, we have objectsA1, B1 in cell 1, objects A¯1, B¯1, C¯1, D¯1,1 in cell 2, and objects l1,0,…,lm,0, p, α0, cod(φ) in cell 3.
In what follows, we first analyze the computation process that takes place in cells 1 and 2; then we explain the computation process that takes place in cell 3.
At the first step of theith (3≤i≤n) loop involving cells 1 and 2, by using rules r1,i–r4,i, objects Ai, Ai′, Bi, Bi′ in cell 1 are sent to cell 2 and evolved to A^i, A^i′, B^i, B^i′, respectively; simultaneously, objects A¯i, A¯i, B¯i, B¯i in cell 2 are sent to cell 1 and evolved to A¯i, A¯i′, B¯i, B¯i′, respectively. By applying rule r5,i, object C¯i in cell 2 is consumed, and object v¯i in the environment is sent into cell 2 and evolved to vi. By using rule r6,i,j, object v~i,j in the environment is sent into cell 2 and evolved to qi,j, and object D¯i,j in cell 2 is consumed. By using rules r7,i–r10,i, objects ti, ti, fi, fi in cell 2 are sent to the corresponding cell 1, respectively; simultaneously, objects Ti, Ti′, Fi, Fi′ in cell 1 are consumed.
Note that at the first step of the 1st loop involving cells 1 and 2, only rulesr1,1, r3,1, r5,1, r6,1 are applied; at the first step of the 2nd loop involving cells 1 and 2, only rules r1,2, r2,2, r3,2, r4,2, r5,2, r6,2, r7,2, r10,2 are applied.
At the second step of theith (2≤i≤n) loop involving cells 1 and 2, by using rules r11,i–r14,i, objects A¯i, A¯i′, B¯i, B¯i′ in cell 1 are exchanged with objects A~i, A~i, B~i, B~i in the environment, and objects aiai′, aiai′, bibi′, bibi′ are produced in cell 1, respectively. By applying rules r15,i–r18,i, objects Ai, Ai′, Bi, Bi′ are produced in corresponding cell 2, respectively. Object vi in cell 2 is exchanged with object y¯i in the environment by using rule r19,i, and two copies of object yi are produced in cell 2. By applying rule r21,i,j, two copies of object ri,j are produced in cell 2. By applying rules r22,i, r23,i, objects t¯i, f¯i in the environment are sent into corresponding cell 1 and evolved to TiTi′, FiFi′, respectively.
Note that at the second step of the 1st loop involving cells 1 and 2, only rulesr11,1, r13,1, r15,1, r17,1, r19,1, r20 are applied.
At the third step of theith (2≤i≤n) loop involving cells 1 and 2, by using rules r24,i–r27,i, objects Ai, Ai′, Bi, Bi′ in cell 2 are exchanged with objects c¯i, c~i, c¯i, c~i in the environment, respectively; objects Ai, Ai′, Bi, Bi′ are sent to the environment and consumed, and objects c¯i, c~i, c¯i, c~i are sent into cell 2 and evolved to ci. By applying rules r28,i–r31,i, objects TiAi+1, Fi′Ai+1′, Bi+1S, Bi+1′ are produced in corresponding cell 1, respectively. By using rule r32,i, object yi in cell 2 is sent to the environment and consumed; simultaneously, object y~i in the environment is sent into cell 2 and evolved to ziwi. By using rule r33,i,j, object ri,j in cell 2 is sent to the environment and consumed; simultaneously, object r~i,j in the environment is sent into cell 2 and evolved to siui,j.
Note that at the third step of the 1st loop involving cells 1 and 2, only rulesr24,1, r26,1, r28,1, r29,1, r30,1, r31,1, r32,1, r33,1,1 are applied.
At the fourth step of theith (2≤i≤n) loop involving cells 1 and 2, by using rule r40, object S is consumed, and the objects from Γ0 already existing in cell 1 are placed in the first cell, while those from Γ1 are placed in the second cell. By using rules r34,i–r39,i,j, objects wi, ci, zi, si, u1,j, ui,j in cell 2 are sent to the environment and consumed; simultaneously, objects w~i, d~i, z~i, s~i, u~1,j, u~i,j in the environment are sent into cell 2 and evolved to A¯i+1, B¯i+1, C¯i+1, tifi, D¯1,j+1D¯2,j+1, D¯i+1,j+1, respectively.
Note that at the fourth step of the 1st loop involving cells 1 and 2, only rulesr34,1, r35,1, r36,1, r37,1, r38,1, r40 are applied.
At step4n+1, rules r7,i–r10,i, r41,i–r43 are enabled. By applying rules r7,i–r10,i, objects Ti, Ti′, Fi, Fi′ in each cell 1 are changed to objects ti, ti, fi, fi, respectively. By using rule r41,i, object D¯i,n+1 in cell 2 is sent to the environment; simultaneously, object v~i,n+1 in the environment is sent into cell 2 and evolved to two copies of object hi. By applying rules r42, r43, each cell with label 1 will produce an object E1.
At step4n+2, by using rules r22,i, r23,i, objects ti, fi in each cell 1 are changed to objects TiTi′, FiFi′, respectively.
At step4n+3, rules r44,i, r45,i are enabled and applied, and objects TiTi′, FiFi′ in each cell 1 are changed to T¯i, F¯i, respectively.
At the firstn+1 steps of the generation phase, by using rules r46,i,j–r53,j, 2n copies of objects (cod(φ))e, lj(1≤j≤m) are produced in cell 3.
Checking Phase. This phase takes 3m steps and consists of a loop with m iterations, where each iteration takes three steps.
At the first step of thejth loop (1≤j≤m), objects T¯i, Ej (resp., F¯i, Ej) in cell 1 are exchanged with object ei,j (resp., e¯i,j) in cell 3 by using rule r54,i,j (resp., r55,i,j), in case cell 1 encodes a truth assignment making clauses C1,…,Cj true. Note that if a cell with label 1 contains a truth assignment that does not make the clause Cj true, the computation will stop in that cell when rule r54,i,j or rule r55,i,j is applied. When using rule r54,i,j (resp., r55,i,j), object ei,j (resp., e¯i,j) is sent into cell 1 and evolved to Ei,j (resp., E¯i,j); simultaneously, objects T¯i, Ej (resp., F¯i, Ej) in cell 1 are sent to cell 3 and consumed. In addition, counter object α in cell 3 is evolved.
At the second step of thejth loop (1≤j≤m), if a cell with label 1 contains object Ei,j (resp., E¯i,j), then rule r56,i,j (resp., r57,i,j) is enabled and applied, and object Ei,j (resp., E¯i,j) in cell 1 is sent to cell 3; simultaneously, object lj in cell 3 is sent to the corresponding cell 1 and evolved to li,j (resp., l¯i,j). Moreover, counter object α in cell 3 is evolved.
At the third step of thejth loop (1≤j≤m), rule r58,i,j (resp., r59,i,j) is enabled in cell 1 in case object li,j (resp., l¯i,j) appears in that cell. By using rule r58,i,j (resp., r59,i,j), object li,j (resp., l¯i,j) in cell 1 is sent to cell 3 and consumed; simultaneously, object Ei,j (resp., E¯i,j) in cell 3 is sent into corresponding cell 1 and evolved to T¯i, Ej+1 (resp., F¯i, Ej+1). In addition, counter object α increases its subscript.
Output Phase. In this phase, the system sends the right answer into the environment according to the result of the previous phase.
If the input formulaφ is satisfiable, then there exists at least one cell with label 1 that contains object Em+1 after 4n+3m+3 steps. In this case, at step 4n+3m+4, by using rule r60,i, object α4n+3m+4 will present in cell 3; simultaneously, rule r61 is enabled and applied; object p in cell 3 is sent into the corresponding cell 1 and consumed; object Em+1 in cell 1 is sent into cell 3 and evolved to yes, which will be sent to the environment at the next step by using rule r62, and the system halts, and the answer of the system isaffirmative.
If the input formulaφ is not satisfiable, then there is no cell with label 1 that contains object Em+1 after 4n+3m+3 steps. In this case, at step 4n+3m+4, only rule r60,i is enabled and applied, and object α4n+3m+4 will appear in cell 3. At step 4n+3m+5, if object p appears in cell 3, then rule r63 is applied, objects α4n+3m+4, p are sent to the environment and evolved to no, the system halts, and the answer of the system isnegative.
From the computation process, we can check that rules of a systemΠ(〈n,m〉) of the family are defined recursively from values n and m, and the necessary resources to build each such system are as follows:(i)
size of the alphabet:4n2m+8n2+10nm+55n+8m+19∈O(n2m);(ii)
initial number of cells:3∈O(1);(iii)
initial number of objects:m+8∈O(m);(iv)
number of rules:2n2m+4n2+9nm+39n+4m+5∈O(n2m);(v)
maximum length of a rule (the total number of objects involved in a rule):4∈O(1).
Hence, there exists a deterministic Turing machine that builds the systemΠ(〈m,n〉) in a polynomial time with respect to m and n. So the family Π={Π(〈m,n〉)∣m,n∈N} is polynomially uniform by Turing machines.
The tissue P systemΠ(〈n,m〉) with input multiset cod(φ) always halts and sends object yes or no to the environment at the last step, that is, at step 4n+3m+5. Hence the family Π={Π(〈m,n〉)∣m,n∈N} is polynomially bounded.
According to Definition3, the family Π of recognizer tissue P systems from TSEC(3,2) solve SAT problem in linear time. Hence, the theorem holds.Corollary 9.
One hasNP∪co-NP⊆PMCTSEC(3,2).Proof.
The theorem holds because theSAT problem isNP-complete, SAT  ∈PMCTSEC(3,2), and the class PMCTSEC(3,2) is closed under polynomial time reduction and under complement.Corollary 10.
For each natural numbern≥3, one has NP∪co-NP⊆PMCTSEC(n,2).Proof.
It suffices to notice that for each natural numbern≥3 the following holds: PMCTSEC(3,2)⊆PMCTSEC(n,2).Figure1 illustrates the results obtained in this paper as well as some open problems. The point (p,q) represents the complexity class PMCTSEC(p,q). The green circles correspond to classP, the red circles correspond to a class containing NP∪co-NP, and the black circles correspond to open problems.Figure 1
Summary of the results and open problems.


## 3.1. The Limitation on the Efficiency ofTSEC(2,1)

In this subsection, we use tissue P systems with cell separation and evolutional communication rules of length at most(2,1) to provide a new characterization of the classical complexity class P.The proof uses a similar technique as in [32]. Firstly, some representations of TESAS P systems Π=(Γ,Γ0,Γ1,E,Σ,M1,…,Mq,R,iin,iout) from TSEC(2,1) are given. By RC (resp., RS) we denote the set of communication rules (resp., separation rules) of Π. We will fix a total order in RC and a total order in RS. Because several cells with the same label are generated by using separation rules, in order to identify the different cells with the same label, the following recursive definition is used to modify the labels of the new generated cells:(i)
We denote the label of a cell as a pair(i,σ), where 1≤i≤q and σ∈{0,1} is a binary string.(ii)
If a separation rule is applied to a cell with label(i,σ), then the new created two cells will be labelled by (i,σ0) and (i,σ1), respectively. We mention that, for the system during any computation, we consider a lexicographical order over the set of labels of cells.Note that if communication rules occur in two cells, then the labels of these two cells do not change.A configuration at an instantt of a tissue P system from TSEC(2,1) is described by the multisets of objects over Γ contained in each cell and the multiset of objects over Γ∖E in the environment. Hence, a configuration of Π can be described as follows: (3)a,i,σ∣a∈Γ∪λ,1≤i≤q,σ∈0,1∗∪a,0∣a∈Γ∖E.Letr=[ab]i[]j→[]icj, 1≤i,j≤q, be an evolutional symport rule of Π and n∈N. We denote by n·LHS(r,(i,σi),(j,σj)) the multiset of objects (a,i,σi)n(b,i,σi)n and the corresponding n·RHS(r,(i,σi),(j,σj)) the multiset of objects (c,j,σj)n. In a similar way, n·LHS(r,(i,σi),(j,σj)) and n·RHS(r,(i,σi),(j,σj)) are defined when r is of the form [a]i[]j→[]i[c]j.Letr=[ab]i[]j→[]i[λ]j, 1≤i,j≤q, be an evolutional symport rule of Π and n∈N. We denote by n·LHS(r,(i,σi),(j,σj)) the multiset of objects (a,i,σi)n(b,i,σi)n, and the corresponding n·RHS(r,(i,σi),(j,σj)) is ∅. In a similar way, n·LHS(r,(i,σi),(j,σj)) and n·RHS(r,(i,σi),(j,σj)) are defined when r is of the form [a]i[]j→[]i[λ]j.Letr=[ab]0[]j→[]0[c]j, 1≤j≤q, be an evolutional symport rule of Π and n∈N. We denote by n·LHS(r,(j,σj),0) the multiset of objects (4)a,0nb,0n,ifa,b∈Γ∖E;a,0n,ifa∈Γ∖E,b∈E;b,0n,ifb∈Γ∖E,a∈E;∅,otherwise;and we denote by the corresponding n·RHS(r,(j,σj),0) the multiset of objects (c,j,σj)n. In a similar way, n·LHS(r,(j,σj),0) and n·RHS(r,(j,σj),0) are defined when r is of the form [a]0[]j→[]0[λ]j.Letr=[ab]0[]j→[]0[λ]j, 1≤j≤q, be an evolutional symport rule of Π and n∈N. We denote by n·LHS(r,(j,σj),0) the multiset of objects (5)a,0nb,0n,ifa,b∈Γ∖E;a,0n,ifa∈Γ∖E,b∈E;b,0n,ifb∈Γ∖E,a∈E;∅,otherwise.The corresponding n·RHS(r,(j,σj),0) is ∅. In a similar way, n·LHS(r,(j,σj),0) and n·RHS(r,(j,σj),0) are defined when r is of the form [a]0[]j→[]0[λ]j.Letr=[a]i[b]j→[c]i[λ]j, 1≤i,j≤q, be an evolutional antiport rule of Π and n∈N. We denote by n·LHS(r,(i,σi),(j,σj)) the multiset of objects (a,i,σi)n(b,j,σj)n and the corresponding n·RHS(r,(i,σi),(j,σj)) the multiset of objects (c,i,σi)n. In a similar way, n·LHS(r,(i,σi),(j,σj)) and n·RHS(r,(i,σi),(j,σj)) are defined when r is of the form [a]i[b]j→[λ]i[c]j.Letr=[a]i[b]j→[λ]i[λ]j, 1≤i,j≤q, be an evolutional antiport rule of Π and n∈N. We denote by n·LHS(r,(i,σi),(j,σj)) the multiset of objects (a,i,σi)n(b,j,σj)n, and the corresponding n·RHS(r,(i,σi),(j,σj)) is ∅.Letr=[a]0[b]j→[c]0[λ]j, 1≤j≤q, be an evolutional antiport rule of Π and n∈N. We denote by n·LHS(r,(j,σj),0) the multiset of objects (6)a,0nb,jn,ifa∈Γ∖E;b,jn,otherwise;and we denote by the corresponding n·RHS(r,(j,σj),0) the multiset of objects (7)c,0n,ifc∈Γ∖E;∅,otherwise.Letr=[a]0[b]j→[λ]0[c]j, 1≤j≤q, be an evolutional antiport rule of Π and n∈N. We denote by n·LHS(r,(j,σj),0) the multiset of objects (8)a,0nb,jn,ifa∈Γ∖E;b,jn,otherwise;and we denote by the corresponding n·RHS(r,(j,σj),0) the multiset of objects (c,j,σj)n.Letr=[a]0[b]j→[λ]0[λ]j, 1≤j≤q, be an evolutional antiport rule of Π and n∈N. We denote by n·LHS(r,(j,σj),0) the multiset of objects (9)a,0nb,jn,ifa∈Γ∖E;b,jn,otherwise.The corresponding n·RHS(r,(j,σj),0) is ∅.IfCt is a configuration of Π, then the multiset obtained by replacing in Ct every occurrence of (x,i,σ) by (x,i,σ′) is denoted by Ct+{(x,i,σ)/σ′}. Moreover, we denote by Ct+m (resp., Ct∖m) a multiset m of labelled objects added to (resp., removed from) the configuration Ct.Next, we show that TESAS P systems fromTSEC(2,1) can only solve tractable problems.IfC={Ct}t<r+1 of Π (r∈N) is a halting computation, then we denote by C=r the length of C. For each i(1≤i≤q), the multiset of objects over Γ contained in all cells labelled by i at configuration Ct is denoted by Ct(i). We denote by Ct(0) the multiset of objects over Γ∖E contained in the environment at configuration Ct. Finally, the finite multiset Ct(0)+Ct(1)+⋯+Ct(q) is denoted by Ct∗.Lemma 4.
LetΠ=(Γ,Γ0,Γ1,E,Σ,M1,…,Mq,R,iin,iout) be a recognizer tissue P system of degree q≥1 from TSEC(2,1). Let M=M1+⋯+Mq and let C={C0,…,Cr} be a computation of Π. Then, one has(1)
C0∗=M, and for each t, 0≤t<r, Ct+1∗≤Ct∗;(2)
for eacht, 0≤t≤r, Ct∗≤M;(3)
the number of created cells along the computationC by the application of cell separation rules is bounded by 2M.Proof.
(1) Let us notice that(10)C0∗=C00+C01+⋯+C0q=M1+⋯+Mq=M.Let Π be a recognizer tissue P system from TSEC(2,1) and let R be the set of rules associated with Π, which contains the following types of evolutional communication rules:(a)
[ab]i[]j→[]i[c]j, (i=0∧{a,b}⊈E) or (i≠0∧{a,b}⊆Γ);(b)
[ab]i[]j→[]i[λ]j, (i=0∧{a,b}⊈E) or (i≠0∧{a,b}⊆Γ);(c)
[a]i[b]j→[c]i[λ]j, {a,b}⊆Γ;(d)
[a]i[b]j→[λ]i[c]j, {a,b}⊆Γ;(e)
[a]i[b]j→[λ]i[λ]j, {a,b}⊆Γ;(f)
[a]i[]j→[]i[b]j, (i=0∧a∈Γ∖E) or (i≠0∧a∈Γ);(g)
[a]i[]j→[]i[λ]j, (i=0∧a∈Γ∖E) or (i≠0∧a∈Γ).
For eacht, 0≤t<r, in the transition from configuration Ct to configuration Ct+1, by using any rules of types from (a) to (g), at least one object from Ct is consumed and at most one object is produced in Ct+1. Hence, in any transition step the number of objects in the system is not increased.
(2) By induction ont, let us start analyzing the basic case t=0. The result is trivial because of C0∗=M. By induction hypothesis, let us suppose the result holds for t, 0≤t<r. Then, (11)Ct+1∗≤1Ct∗≤h.i.M.Hence, the result is also true for t+1.
(3) According to the fact that the application of a cell separation rule consumes an object and produces two new cells, result (3) can be obtained from (2) easily.Next, a deterministic algorithmA working in polynomial time is presented, which receives as input a P system Π from TSEC(2,1) and an input multiset m of Π, in such manner that algorithm A reproduces the behaviour of a computation of Π+m. If the system Π is confluent, then the algorithm A will provide the same answer of Π. We give Pseudocode 1 of the algorithm A to describe the simulation process.Pseudocode 1
Input: A P system  Π  from  TSEC(2,1)  and an input multiset  m Initialization phase: C0  is the initial configuration of  Π+m t ← 0 while  Ct  is a non-halting configuration  do Selection phase: Input  Ct,Output  (Ct′,A) Execution phase: Input  (Ct′,A), Output  Ct+1 t ← t + 1 end while Output: Yes  if  Π+m  has an accepting computation,  No  otherwiseThe algorithmA receives a recognizer tissue P system(12)Π=Γ,Γ0,Γ1,E,Σ,M1,…,Mq,R,iin,ioutfrom TSEC(2,1) and an input multiset m. Let M=M1+⋯+Mq. Let any computation of Π perform at most p (p is a natural number) transition steps. Hence, from Lemma 4, the number of cells in the system along any computation is bounded by 2M+q.A transition of a recognizer tissue P systemΠ+m is performed in two phases: selection phase and execution phase (see Algorithms 1 and 2). For the detailed information of a transition of such P system, one can refer to [32].Algorithm 1:Selection phase.
Input:  A configuration  Ct  of  Π+m  at instant  t C t ′ ← C t  ;  A ← ∅  ;  B ← ∅ for  r=[u]i[v]j→[v′]i[u′]j∈RC, according to the order chosen  do for  each pair of cells  (i,σi),(j,σj)  of  Ct′  according tothe lexicographical order  do n r ←  maximum number of times that  r  is applicable to  (i,σi), ( j , σ j ) if  nr>0  then C t ′ ← C t ′ - n r ⋅ L H S ( r , ( i , σ i ) , ( j , σ j ) ) A ← A ∪ { ( r , n r , ( i , σ i ) , ( j , σ j ) ) } B ← B ∪ { ( i , σ i ) , ( j , σ j ) } end if end for end for for  r=[u]i[v]0→[v′]i[u′]0∈RC  according to the order chosen  do for  each cell  (i,σi)  of  Ct′  according to the lexicographical order  do n r ←  maximum number of times that  r  is applicable to  (i,σi) if  nr>0  then C t ′ ← C t ′ - n r ⋅ L H S ( r , ( i , σ i ) , 0 ) A ← A ∪ { ( r , n r , ( i , σ i ) , 0 ) } B ← B ∪ { ( i , σ i ) } end if end for end for for  r=[a]i→[Γ0]i[Γ1]i∈RS  according to the order chosen  do for  each  (a,i,σi)∈Ct′  according to the lexicographical order, and  such that  (i,σi)∉B  do C t ′ ← C t ′ ∖ { ( a , i , σ i ) } A ← A ∪ { ( r , 1 , ( i , σ i ) ) } end for end forAlgorithm 2:Execution phase.
Input:  The output(Ct′,A)of the selection phase for  each(r,nr,(i,σi),(j,σj))∈Ado C t ′ ← C t ′ + n r ⋅ R H S ( r , ( i , σ i ) , ( j , σ j ) ) end for for  each  ( r , n r , ( i , σ i ) , 0 ) ∈ A  do C t ′ ← C t ′ + n r ⋅ R H S ( r , ( i , σ i ) , 0 ) end for for  each  ( r , 1 , ( i , σ i ) ) ∈ A  do C t ′ ← C t ′ + { ( λ , i , σ i ) / σ i 0 } C t ′ ← C t ′ + { ( λ , i , σ i 1 ) } for  each  ( x , i , σ i ) ∈ C t ′  according to the lexicographical order  do if  x ∈ Γ 0  then C t ′ ← C t ′ + { ( x , i , σ i ) / σ i 0 } else C t ′ ← C t ′ + { ( x , i , σ i ) / σ i 1 } end if end for end for C t + 1 ← C t ′It is easy to check that Algorithm1 is deterministic and the running time of this algorithm is polynomial in the size of Π because the number of cycles of the first main loopfor is of order O(R·M2·q2); the number of cycles of the second main loopfor is of order O(R·M·q); and the number of cycles of the third main loopfor is of order O(R·M·q·Γ).Algorithm2 is deterministic and the running time of this algorithm is polynomial in the size of Π because the number of cycles of the first main loopfor is of order O(R·M2·q2); the number of cycles of the second main loopfor is of order O(R·M·q); and the number of cycles of the third main loopfor is of order O(R·M·q·Γ).Theorem 5.
One hasP=PMCTSEC(2,1).Proof.
BecausePMCTSEC(2,1) is closed under polynomial time reduction and nonempty, hence P⊆PMCTSEC(2,1). In what follows, we show that CTSEC(2,1)⊆P. Let X∈PMCTSEC(2,1) and let Π={Πn∣n∈N} be a family of recognizer tissue P systems fromTSEC(2,1) solving X according to Definition 3. Let (cod,s) be a polynomial encoding associated with that solution. If u∈IX is an instance of the problem X, then u will be processed by the system Π(s(u))+cod(u). We consider the deterministic algorithm A′ as shown in Algorithm 3.
The algorithmA′ receives an instance u of the decision problem X=(IX,θX), working in a polynomial time. The following three assertions are equivalent:(i)
θX(u)=1; that is, the answer of problem X to instance u is affirmative.(ii)
Every computation ofΠ(s(u))+cod(u) is an accepting computation.(iii)
The output of the algorithmA′ with input u is Yes.
Hence,X∈P.Algorithm 3
Input:  an instance  u  of the problem  X Construct the system  Π(s(u))+cod(u) Run algorithm  A  with input  Π(s(u))+cod(u) Output:  Yes if  Π(s(u))+cod(u)  has an accepting computation No otherwiseCorollary 6.
For eachn∈N, n≥1, one has PMCTSEC(n,1)=P.Proof.
Indeed, it suffices to notice that, at any transition step, the application of each rule consumes at least one object fromΓ∖E and produces at most one object from Γ. Thus, along any computation of the system, the total number in it is not increased.Theorem 7.
For eachn∈N, n≥1, one has PMCTSEC(1,n)=P.Proof.
In [31], it was shown that the class of decision problems solvable in polynomial time by means of families of tissue P systems with cell division and symport rules with length 1 is equal to classP. Bearing in mind that systems from TSEC(1,n) are noncooperative ones, the dependency graph technique used in the cited paper can be used to obtain the result, in a similar way.


## 3.2. An Efficient Solution to the SAT Problem by P Systems inTSEC(3,2)

TheSAT problem is a well-knownNP-complete problem; here we give an efficient solution to the SAT problem by a family of tissue P systems with evolutional communication rules of length at most (3,2).Theorem 8.
One hasSAT  ∈PMCTSEC(3,2).Proof.
We provide a polynomial time uniform solution to theSAT problem [41] by a family of recognizer tissue P systems Π={Π(t)∣t∈N} from TSEC(3,2). Each system Π(t) (t=〈n,m〉=((n+m)(n+m+1)/2)+n) can process all Boolean formula φ in conjunctive normal form with n variables and m clauses.
For eachn,m∈N, we consider the recognizer tissue P system (13)Πn,m=Γ,Γ0,Γ1,E,Σ,M1,M2,M3,R,iin,iout,where(14)Γ=Σ∪E∪Ai,Ai′,A¯i,A¯i′,A^i,A^i′,Bi,Bi′,B¯i,B¯i′,B^i,B^i′,C¯i,Ti,T¯i,Ti′,Fi,F¯i,Fi′,ai,ai′,bi,bi′,ci,ti,fi,hi,yi,si,vi,wi,zi∣1≤i≤n∪D¯i,j,qi,j,ri,j,ui,j∣1≤i,j≤n∪D¯i,n+1∣1≤i≤n+1∪gi,j,k,g¯i,j,k∣1≤i,k≤n,1≤j≤m∪Ei,j,E¯i,j,ei,j,e¯i,j,lj,i∣1≤i≤n,1≤j≤m∪lj,l¯j,lj,0,Ej∣1≤j≤m∪An+1,A¯n+1,An+1′,Bn+1,B¯n+1,Bn+1′,C¯n+1,Em+1,S,p,yes,no,Γ1=Ti′,Fi′∣1≤i≤n∪Ai′,Bi′∣2≤i≤n+1,Γ0=Γ∖Γ1,Σ=xi,j,x¯i,j∣1≤i≤n,1≤j≤m,E=A~i,B~i,a¯i,a~i,b¯i,b~i,c¯i,c~i,d~i,f¯i,s~i,t¯i,v¯i,v~i,n+1,w~i,y¯i,y~i,z~i∣1≤i≤n∪r¯i,j,r~i,j,u~i,j,v~i,j∣1≤i,j≤n∪gi,j,k′,g¯i,j,k′∣1≤i≤n,1≤j≤m,0≤k≤n∪l¯j,k∣1≤j≤m,0≤k≤n∪αi∣0≤i≤4n+3m+4∪E0,M1=A1,B1,M2=A¯1,B¯1,C¯1,D¯1,1,M3=l1,0,…,lm,0,α0,p,iin=3istheinputcell,iout=0istheoutputregion,and the set R of rules consists of the following rules:(15)r1,i≡Ai1A¯i2⟶A¯i1A^i2,1≤i≤n,r2,i≡Ai′1A¯i2⟶A¯i′1A^i′2,1≤i≤n,r3,i≡Bi1B¯i2⟶B¯i1B^i2,1≤i≤n,r4,i≡Bi′1B¯i2⟶B¯i′1B^i′2,1≤i≤n,r5,i≡C¯i2v¯i0⟶vi20,1≤i≤n,r6,i,j≡D¯i,j2v~i,j0⟶qi,j20,1≤i,j≤n,r7,i≡Ti1ti2⟶ti12,1≤i≤n,r8,i≡Ti′1ti2⟶ti12,1≤i≤n,r9,i≡Fi1fi2⟶fi12,1≤i≤n,r10,i≡Fi′1fi2⟶fi12,1≤i≤n,r11,i≡A¯i1A~i0⟶aiai′10,1≤i≤n,r12,i≡A¯i′1A~i0⟶aiai′10,2≤i≤n,r13,i≡B¯i1B~i0⟶bibi′10,1≤i≤n,r14,i≡B¯i′1B~i0⟶bibi′10,2≤i≤n,r15,i≡A^i2A~i0⟶Ai20,1≤i≤n,r16,i≡A^i′2A~i0⟶Ai′20,2≤i≤n,r17,i≡B^i2B~i0⟶Bi20,1≤i≤n,r18,i≡B^i′2B~i0⟶Bi′20,2≤i≤n,r19,i≡vi2y¯i0⟶yi220,1≤i≤n,r20≡q1,12r¯1,10⟶r1,120,r21,i,j≡qi,j2r¯i,j0⟶ri,j220,1≤i≤n,2≤j≤n,r22,i≡ti1t¯i0⟶TiTi′10,1≤i≤n,r23,i≡fi1f¯i0⟶FiFi′10,1≤i≤n,r24,i≡Ai2c¯i0⟶ci20,1≤i≤n,r25,i≡Ai′2c~i0⟶ci20,2≤i≤n,r26,i≡Bi2c¯i0⟶ci20,1≤i≤n,r27,i≡Bi′2c~i0⟶ci20,2≤i≤n,r28,i≡ai1a¯i0⟶TiAi+110,1≤i≤n,r29,i≡ai′1a~i0⟶Fi′Ai+1′10,1≤i≤n,r30,i≡bi1b¯i0⟶Bi+1S10,1≤i≤n,r31,i≡bi′1b~i0⟶Bi+1′10,1≤i≤n,r32,i≡yi2y~i0⟶ziwi20,1≤i≤n,r33,i,j≡ri,j2r~i,j0⟶siui,j20,1≤i,j≤n,r34,i≡wi2w~i0⟶A¯i+120,1≤i≤n,r35,i≡ci2d~i0⟶B¯i+120,1≤i≤n,r36,i≡zi2z~i0⟶C¯i+120,1≤i≤n,r37,i≡si2s~i0⟶tifi20,1≤i≤n,r38,j≡u1,j2u~1,j0⟶D¯1,j+1D¯2,j+120,1≤j≤n,r39,i,j≡ui,j2u~i,j0⟶D¯i+1,j+120,2≤i,j≤n,r40≡S1⟶Γ01Γ11,r41,i≡D¯i,n+12v~i,n+10⟶hi220,1≤i≤n,r42≡An+11A¯n+12⟶E112,r43≡An+1′1B¯n+12⟶E112,r44,i≡TiTi′1hi2⟶T¯i12,1≤i≤n,r45,i≡FiFi′1hi2⟶F¯i12,1≤i≤n,r46,i,j≡xi,j3gi,j,0′0⟶gi,j,1230,1≤i≤n,1≤j≤m,r47,i,j≡x¯i,j3g¯i,j,0′0⟶g¯i,j,1230,1≤i≤n,1≤j≤m,r48,i,j,k≡gi,j,k3gi,j,k′0⟶gi,j,k+1230,1≤i≤n,1≤j≤m,1≤k≤n-1,r49,i,j,k≡g¯i,j,k3g¯i,j,k′0⟶g¯i,j,k+1230,1≤i≤n,1≤j≤m,1≤k≤n-1,r50,i,j≡gi,j,n3gi,j,n′0⟶ei,j30,1≤i≤n,1≤j≤m,r51,i,j≡g¯i,j,n3g¯i,j,n′0⟶e¯i,j30,1≤i≤n,1≤j≤m,r52,j,k≡lj,k3l¯j,k0⟶lj,k+1230,1≤j≤m,0≤k≤n-1,r53,j≡lj,n3l¯j,n0⟶lj30,1≤j≤m,r54,i,j≡T¯iEj1ei,j3⟶Ei,j13,1≤i≤n,1≤j≤m,r55,i,j≡F¯iEj1e¯i,j3⟶E¯i,j13,1≤i≤n,1≤j≤m,r56,i,j≡Ei,j1lj3⟶li,j1Ei,j3,1≤i≤n,1≤j≤m,r57,i,j≡E¯i,j1lj3⟶l¯i,j1E¯i,j3,1≤i≤n,1≤j≤m,r58,i,j≡li,j1Ei,j3⟶T¯iEj+113,1≤i≤n,1≤j≤m,r59,i,j≡l¯i,j1E¯i,j3⟶F¯iEj+113,1≤i≤n,1≤j≤m,r60,i≡αi3α¯i0⟶αi+130,0≤i≤4n+3m+3,r61≡Em+11p3⟶1yes3,r62≡yes30⟶3yes0,r63≡α4n+3m+4p30⟶3no0.
We consider a propositional formulaφ=C1∧⋯∧Cm, which contains m (m≥1) clauses, Ci=yi,1∨⋯∨yi,pi, for pi≥1, and yi,j∈{xk,¬xk∣1≤k≤n}, for 1≤i≤m, 1≤j≤pi.
Let(cod,s) be a polynomial encoding of instances from SAT in Π, where s(φ)=〈n,m〉 and cod(φ)={xi,j∣xi∈Cj}∪{x¯i,j∣¬xi∈Cj}. So the propositional formula φ will be processed by the system Π(s(φ))+cod(φ).
An instance of theSAT problem is solved by the system Π(s(φ))+cod(φ), which can be separated into three phases: generation phase, checking phase, and output phase.
Generation Phase. In this phase, by using separation rules in cell with label 1, all truth assignments for the variables associated with the Boolean formula φ(x1,…,xn) will be generated. When this phase completes, there are 2n copies of cell with label 1 such that each of them encodes a different truth assignment of variables {x1,…,xn}.
The generation phase takes4n+3 steps, which has two parallel processes. On the one hand, n loops are executed, and each loop takes four steps. When the loops are completed, three additional steps are executed. On the other hand, there is a counter object α in cell 3 that evolves from α0 to α4n+3m+3, and objects (cod(φ))e2n, (lj)2n (1≤j≤m) are produced in cell 3 after n+1 steps at this phase.
In the initial configuration, we have objectsA1, B1 in cell 1, objects A¯1, B¯1, C¯1, D¯1,1 in cell 2, and objects l1,0,…,lm,0, p, α0, cod(φ) in cell 3.
In what follows, we first analyze the computation process that takes place in cells 1 and 2; then we explain the computation process that takes place in cell 3.
At the first step of theith (3≤i≤n) loop involving cells 1 and 2, by using rules r1,i–r4,i, objects Ai, Ai′, Bi, Bi′ in cell 1 are sent to cell 2 and evolved to A^i, A^i′, B^i, B^i′, respectively; simultaneously, objects A¯i, A¯i, B¯i, B¯i in cell 2 are sent to cell 1 and evolved to A¯i, A¯i′, B¯i, B¯i′, respectively. By applying rule r5,i, object C¯i in cell 2 is consumed, and object v¯i in the environment is sent into cell 2 and evolved to vi. By using rule r6,i,j, object v~i,j in the environment is sent into cell 2 and evolved to qi,j, and object D¯i,j in cell 2 is consumed. By using rules r7,i–r10,i, objects ti, ti, fi, fi in cell 2 are sent to the corresponding cell 1, respectively; simultaneously, objects Ti, Ti′, Fi, Fi′ in cell 1 are consumed.
Note that at the first step of the 1st loop involving cells 1 and 2, only rulesr1,1, r3,1, r5,1, r6,1 are applied; at the first step of the 2nd loop involving cells 1 and 2, only rules r1,2, r2,2, r3,2, r4,2, r5,2, r6,2, r7,2, r10,2 are applied.
At the second step of theith (2≤i≤n) loop involving cells 1 and 2, by using rules r11,i–r14,i, objects A¯i, A¯i′, B¯i, B¯i′ in cell 1 are exchanged with objects A~i, A~i, B~i, B~i in the environment, and objects aiai′, aiai′, bibi′, bibi′ are produced in cell 1, respectively. By applying rules r15,i–r18,i, objects Ai, Ai′, Bi, Bi′ are produced in corresponding cell 2, respectively. Object vi in cell 2 is exchanged with object y¯i in the environment by using rule r19,i, and two copies of object yi are produced in cell 2. By applying rule r21,i,j, two copies of object ri,j are produced in cell 2. By applying rules r22,i, r23,i, objects t¯i, f¯i in the environment are sent into corresponding cell 1 and evolved to TiTi′, FiFi′, respectively.
Note that at the second step of the 1st loop involving cells 1 and 2, only rulesr11,1, r13,1, r15,1, r17,1, r19,1, r20 are applied.
At the third step of theith (2≤i≤n) loop involving cells 1 and 2, by using rules r24,i–r27,i, objects Ai, Ai′, Bi, Bi′ in cell 2 are exchanged with objects c¯i, c~i, c¯i, c~i in the environment, respectively; objects Ai, Ai′, Bi, Bi′ are sent to the environment and consumed, and objects c¯i, c~i, c¯i, c~i are sent into cell 2 and evolved to ci. By applying rules r28,i–r31,i, objects TiAi+1, Fi′Ai+1′, Bi+1S, Bi+1′ are produced in corresponding cell 1, respectively. By using rule r32,i, object yi in cell 2 is sent to the environment and consumed; simultaneously, object y~i in the environment is sent into cell 2 and evolved to ziwi. By using rule r33,i,j, object ri,j in cell 2 is sent to the environment and consumed; simultaneously, object r~i,j in the environment is sent into cell 2 and evolved to siui,j.
Note that at the third step of the 1st loop involving cells 1 and 2, only rulesr24,1, r26,1, r28,1, r29,1, r30,1, r31,1, r32,1, r33,1,1 are applied.
At the fourth step of theith (2≤i≤n) loop involving cells 1 and 2, by using rule r40, object S is consumed, and the objects from Γ0 already existing in cell 1 are placed in the first cell, while those from Γ1 are placed in the second cell. By using rules r34,i–r39,i,j, objects wi, ci, zi, si, u1,j, ui,j in cell 2 are sent to the environment and consumed; simultaneously, objects w~i, d~i, z~i, s~i, u~1,j, u~i,j in the environment are sent into cell 2 and evolved to A¯i+1, B¯i+1, C¯i+1, tifi, D¯1,j+1D¯2,j+1, D¯i+1,j+1, respectively.
Note that at the fourth step of the 1st loop involving cells 1 and 2, only rulesr34,1, r35,1, r36,1, r37,1, r38,1, r40 are applied.
At step4n+1, rules r7,i–r10,i, r41,i–r43 are enabled. By applying rules r7,i–r10,i, objects Ti, Ti′, Fi, Fi′ in each cell 1 are changed to objects ti, ti, fi, fi, respectively. By using rule r41,i, object D¯i,n+1 in cell 2 is sent to the environment; simultaneously, object v~i,n+1 in the environment is sent into cell 2 and evolved to two copies of object hi. By applying rules r42, r43, each cell with label 1 will produce an object E1.
At step4n+2, by using rules r22,i, r23,i, objects ti, fi in each cell 1 are changed to objects TiTi′, FiFi′, respectively.
At step4n+3, rules r44,i, r45,i are enabled and applied, and objects TiTi′, FiFi′ in each cell 1 are changed to T¯i, F¯i, respectively.
At the firstn+1 steps of the generation phase, by using rules r46,i,j–r53,j, 2n copies of objects (cod(φ))e, lj(1≤j≤m) are produced in cell 3.
Checking Phase. This phase takes 3m steps and consists of a loop with m iterations, where each iteration takes three steps.
At the first step of thejth loop (1≤j≤m), objects T¯i, Ej (resp., F¯i, Ej) in cell 1 are exchanged with object ei,j (resp., e¯i,j) in cell 3 by using rule r54,i,j (resp., r55,i,j), in case cell 1 encodes a truth assignment making clauses C1,…,Cj true. Note that if a cell with label 1 contains a truth assignment that does not make the clause Cj true, the computation will stop in that cell when rule r54,i,j or rule r55,i,j is applied. When using rule r54,i,j (resp., r55,i,j), object ei,j (resp., e¯i,j) is sent into cell 1 and evolved to Ei,j (resp., E¯i,j); simultaneously, objects T¯i, Ej (resp., F¯i, Ej) in cell 1 are sent to cell 3 and consumed. In addition, counter object α in cell 3 is evolved.
At the second step of thejth loop (1≤j≤m), if a cell with label 1 contains object Ei,j (resp., E¯i,j), then rule r56,i,j (resp., r57,i,j) is enabled and applied, and object Ei,j (resp., E¯i,j) in cell 1 is sent to cell 3; simultaneously, object lj in cell 3 is sent to the corresponding cell 1 and evolved to li,j (resp., l¯i,j). Moreover, counter object α in cell 3 is evolved.
At the third step of thejth loop (1≤j≤m), rule r58,i,j (resp., r59,i,j) is enabled in cell 1 in case object li,j (resp., l¯i,j) appears in that cell. By using rule r58,i,j (resp., r59,i,j), object li,j (resp., l¯i,j) in cell 1 is sent to cell 3 and consumed; simultaneously, object Ei,j (resp., E¯i,j) in cell 3 is sent into corresponding cell 1 and evolved to T¯i, Ej+1 (resp., F¯i, Ej+1). In addition, counter object α increases its subscript.
Output Phase. In this phase, the system sends the right answer into the environment according to the result of the previous phase.
If the input formulaφ is satisfiable, then there exists at least one cell with label 1 that contains object Em+1 after 4n+3m+3 steps. In this case, at step 4n+3m+4, by using rule r60,i, object α4n+3m+4 will present in cell 3; simultaneously, rule r61 is enabled and applied; object p in cell 3 is sent into the corresponding cell 1 and consumed; object Em+1 in cell 1 is sent into cell 3 and evolved to yes, which will be sent to the environment at the next step by using rule r62, and the system halts, and the answer of the system isaffirmative.
If the input formulaφ is not satisfiable, then there is no cell with label 1 that contains object Em+1 after 4n+3m+3 steps. In this case, at step 4n+3m+4, only rule r60,i is enabled and applied, and object α4n+3m+4 will appear in cell 3. At step 4n+3m+5, if object p appears in cell 3, then rule r63 is applied, objects α4n+3m+4, p are sent to the environment and evolved to no, the system halts, and the answer of the system isnegative.
From the computation process, we can check that rules of a systemΠ(〈n,m〉) of the family are defined recursively from values n and m, and the necessary resources to build each such system are as follows:(i)
size of the alphabet:4n2m+8n2+10nm+55n+8m+19∈O(n2m);(ii)
initial number of cells:3∈O(1);(iii)
initial number of objects:m+8∈O(m);(iv)
number of rules:2n2m+4n2+9nm+39n+4m+5∈O(n2m);(v)
maximum length of a rule (the total number of objects involved in a rule):4∈O(1).
Hence, there exists a deterministic Turing machine that builds the systemΠ(〈m,n〉) in a polynomial time with respect to m and n. So the family Π={Π(〈m,n〉)∣m,n∈N} is polynomially uniform by Turing machines.
The tissue P systemΠ(〈n,m〉) with input multiset cod(φ) always halts and sends object yes or no to the environment at the last step, that is, at step 4n+3m+5. Hence the family Π={Π(〈m,n〉)∣m,n∈N} is polynomially bounded.
According to Definition3, the family Π of recognizer tissue P systems from TSEC(3,2) solve SAT problem in linear time. Hence, the theorem holds.Corollary 9.
One hasNP∪co-NP⊆PMCTSEC(3,2).Proof.
The theorem holds because theSAT problem isNP-complete, SAT  ∈PMCTSEC(3,2), and the class PMCTSEC(3,2) is closed under polynomial time reduction and under complement.Corollary 10.
For each natural numbern≥3, one has NP∪co-NP⊆PMCTSEC(n,2).Proof.
It suffices to notice that for each natural numbern≥3 the following holds: PMCTSEC(3,2)⊆PMCTSEC(n,2).Figure1 illustrates the results obtained in this paper as well as some open problems. The point (p,q) represents the complexity class PMCTSEC(p,q). The green circles correspond to classP, the red circles correspond to a class containing NP∪co-NP, and the black circles correspond to open problems.Figure 1
Summary of the results and open problems.


## 4. A Software Tool to Aid in Formal Validation

The solution to theSAT problem by TESAS P systems is very complicated (see Theorem 8), not obviously a trivial solution, easy to follow and check. In order to evaluate the correctness of the solution to the SAT problem by TESAS P systems, a visual application was provided (see Algorithm 4 for extensive details). With this software, P systems designers could analyse carefully the design proposed; in addition, end users were able to introduce their propositional formulas visually, then run the simulations, and finally get the results.Algorithm 4:P-Lingua translation for SAT solution.
@model < tsec >  def  main()  call init_membrane_structure(); call init_first_alphabet(m,n); call init_second_alphabet(m,n); call init_environment(m,n); call init_multisets(m); call init_rules(m,n); call define_input();   d ef   init_membrane_structure()  @mu = [  [  ] ’1  [  ] ’2  [  ] ’3  ] ’0;   /* @ms1 is  % * $ ∖ Gamma _0  =  ∖ Gamma ∖ setminus ∖ Gamma _ 1 $ *),   including  % * $ ∖ Sigma ∖ cup ∖ mathcal  E  $ *) */ /* Some special symbols as a bar, tilde, hat or prime are replaced in P-Lingua plain text file with suffixes b (bar), t (tilde), h (hat) or p (prime), respectively. Thus,  % * $ ∖hat  A  ' $ *) is written as Ahp ("A hat prime").*/ d ef  init_first_alphabet(m,n)  @ms1 += A  i  ,Ab  i  ,Abp  i  ,Ah  i  ,Ahp  i  ,B  i  ,Bb  i  ,Bbp  i  , Bh  i  ,Bhp  i  ,Cb  i  ,T  i  ,Tb  i  ,F  i  ,Fb  i  ,a  i  , ap  i  ,b  i  ,bp  i  ,c  i  ,t  i  ,f  i  ,h  i  ,y  i  ,s  i  , v  i  ,w  i  ,z  i   : 1<=i<=n; @ms1 += Db  i,j  ,q  i,j  ,r  i,j  ,u  i,j   : 1<=j<=n,1<=i<=n; @ms1 += Db  i,n+1   : 1<=i<=n+1; @ms1 += g  i,j,k  ,gb  i,j,k   : 1<=k<=n,1<=j<=m,1<=i<=n; @ms1 += E  i,j  ,Eb  i,j  ,e  i,j  ,eb  i,j  ,l  j,i   : 1<=j<=m,1<=i<=n; @ms1 += l  j  ,lb  j  ,l  j,0  ,E  j   : 1<= j <= m; @ms1 += A  n+1  ,Ab  n+1  ,B  n+1  ,Bb  n+1  ,Cb  n+1  ,E  m+1  , S,p,yes,no;  /* Input alphabet  % * $ ∖ Sigma $ *) */ @ms1 += x  i,j  ,nx  i,j   : 1<=j<=m,1<=i<=n;  /* Environment alphabet  % * $ ∖ mathcal  E  $ *) */ @ms1 += At  i  ,Bt  i  ,ab  i  ,at  i  ,bb  i  ,bt  i  ,cb  i  ,ct  i  ,dt  i  , tb  i  ,fb  i  ,st  i  ,vb  i  ,vt  i ,n+1  ,wt  i  ,yb  i  ,yt  i  , zt  i   : 1<=i<=n; @ms1 += rb  i,j  ,rt  i,j  ,ut  i,j  ,vt  i,j   : 1<=j<=n,1<=i<=n; @ms1 += gp  i,j,k  ,gbp  i,j,k   : 0<=k<=n,1<=j<=m,1<=i<=n; @ms1 += lb  j,k   : 0<=k<=n,1<=j<=m; @ms1 += al  i  ,alb  i   : 0<=i<=4*n+3*m+4; @ms1 += E  0  ;   d ef  init_second_alphabet(m,n)  @ms2 += Tp  i  ,Fp  i   : 1<=i<=n; @ms2 += Ap  i  ,Bp  i   : 2<=i<=n+1;   d ef  init_environment(m,n)  @ms(0) += At  i  ,Bt  i  ,ab  i  ,at  i  ,bb  i  ,bt  i  ,cb  i  ,ct  i  , dt  i  ,tb  i  ,fb  i  ,st  i  ,vb  i  ,vt  i ,n+1  ,wt  i  , yb  i  ,yt  i  ,zt  i   : 1<=i<=n; @ms(0) += rb  i,j  ,rt  i,j  ,ut  i,j  ,vt  i,j   : 1<=j<=n,1<=i<=n; @ms(0) += gp  i,j,k  ,gbp  i,j,k   : 0<=k<=n,1<=j<=m,1<=i<=n; @ms(0) += lb  j,k   : 0<=k<=n,1<=j<=m; @ms(0) += al  i  ,alb  i   : 0<=i<=4*n+3*m+4; @ms(0) += E  0  ;   d ef  init_multisets(m)  @ms(1) = A  1  ,B  1  ; @ms(2) = Ab  1  ,Bb  1  ,Cb  1  ,Db  1,1  ; @ms(3) = p,al  0  ; @ms(3) += l  i,0   : 1<=i<=m;   d ef  init_rules(m,n)   /* r_  1,i  */  [ A  i  ] ’1 [ Ab  i  ] ’2 –> [ Ab  i  ] ’1 [ Ah  i  ] ’2; /*  r_  2,i   */  [Ap  i  ]’1 [Ab  i  ]’2 –> [ Abp  i  ] ’1 [ Ahp  i  ] ’2; /*  r_  3,i   */  [ B  i  ] ’1 [ Bb  i  ] ’2 –> [ Bb  i  ] ’1 [ Bh  i  ]’2; /*  r_  4,i   */  [ Bp  i  ] ’1 [ Bb  i  ] ’2 –> [ Bbp  i  ] ’1 [ Bhp  i  ] ’2; /*  r_  5,i   */  [ Cb  i  ] ’2 [ vb  i  ] ’0 –> [ v  i  ] ’2 [ ]’0; /*  r_  6,i,j   */  [ Db  i,j  ] ’2 [ vt  i,j  ] ’0 –> [ q  i,j  ] ’2 [ ]’0:1<=j<=n; /*  r_  7,i   */  [ T  i  ] ’1 [ t  i  ] ’2 –> [ t  i  ] ’1 [ ]’2; /*  r_  8,i   */  [ Tp  i  ] ’1 [ t  i  ] ’2 –> [ t  i  ] ’1 [ ]’2; /*  r_  9,i   */  [ F  i  ] ’1 [ f  i  ] ’2 –> [ f  i  ] ’1 [ ]’2; /*  r_  10,i   */  [ Fp  i  ] ’1 [ f  i  ] ’2 –> [ f  i  ] ’1 [ ]’2; : 1<=i<=n; /* r_  11,i  */  [ Ab  i  ] ’1 [ At  i  ] ’0 –> [ a  i  ,ap  i  ] ’1 [ ]’0: 1<=i<=n; /* r_  12,i   */  [ Abp  i  ] ’1 [ At  i  ] ’0 –> [ a  i  ,ap  i  ] ’1 [ ]’0:2<=i<=n; /*  r_  13,i   */  [ Bb  i  ] ’1 [ Bt  i  ] ’0 –> [ b  i  ,bp  i  ] ’1 [ ]’0: 1<=i<=n; /*  r_  14,i   */  [ Bbp  i  ] ’1 [ Bt  i  ] ’0 –> [ b  i  ,bp  i  ] ’1 [ ]’0:2<=i<=n;  /*  r_  15,i   */  [ Ah  i  ] ’2 [ At  i  ] ’0 –> [ A  i  ] ’2 [ ]’0: 1<=i<=n; /*  r_  16,i   */  [ Ahp  i  ] ’2 [ At  i  ] ’0 –> [ Ap  i  ] ’2 [ ]’0: 2<=i<=n; /*  r_  17,i   */  [ Bh  i  ] ’2 [ Bt  i  ] ’0 –> [ B  i  ] ’2 [ ]’0: 1<=i<=n; /*  r_  18,i   */  [ Bhp  i  ] ’2 [ Bt  i  ] ’0 –> [ Bp  i  ] ’2 [ ]’0: 2<=i<=n; /*  r_  19,i   */  [ v  i  ] ’2 [ yb  i  ] ’0 –>  [ y  i  *2 ] ’2 [ ]’0: 1<=i<=n; /*  r_  20   */  [ q  1,1  ] ’2 [ rb  1,1  ] ’0 –> [ r  1,1  ] ’2 [ ]’0; /*  r_  21,i,j   */  [ q  i,j  ] ’2 [ rb  i,j  ] ’0 –> [ r  i,j  *2 ] ’2 [ ]’0 : 2<=j<=n,  1<=i<=n;   /*  r_  22,i   */ [ t  i  ] ’1 [ tb  i  ] ’0 –> [ T  i  ,Tp  i  ] ’1 [ ]’0; /*  r_  23,i   */ [ f  i  ] ’1 [ fb  i  ] ’0 –> [ F  i  ,Fp  i  ] ’1 [ ]’0; : 1<=i<=n;  /* r_  24,i  */  [ A  i  ] ’2 [ cb  i  ] ’0 –> [ c  i  ] ’2 [ ]’0: 1<=i<=n; /* r_  25,i  */  [ Ap  i  ] ’2 [ ct  i  ] ’0 –> [ c  i  ] ’2 [ ]’0: 2<=i<=n; /* r_  26,i  */  [B  i  ]’2 [cb  i  ]’0 –> [c  i  ]’2 [ ]’0: 1<=i<=n; /* r_  27,i  */  [Bp  i  ]’2 [ct  i  ]’0 –> [c  i  ]’2 [ ]’0: 2<=i<=n;  /* r_  28,i  */  [a  i  ]’1 [ab  i  ]’0 –> [T  i  ,A  i+1  ]’1 [ ]’0: 1<=i<=n; /* r_  29,i  */  [ap  i  ]’1 [at  i  ]’0 –> [Fp  i  ,Ap  i+1  ]’1 [ ]’0 : 1<=i<=n;   /* r_  30,i  */  [b  i  ]’1 [bb  i  ]’0 –> [B  i+1  ,S]’1 [ ]’0; /* r_  31,i  */  [bp  i  ]’1 [bt  i  ]’0 –> [Bp  i+1  ]’1 [ ]’0; /* r_  32,i  */  [y  i  ]’2 [yt  i  ]’0 –> [z  i  ,w  i  ]’2 [ ]’0; /* r_  33,i,j  */  [r  i,j  ]’2 [rt  i,j  ]’0 –> [s  i  ,u  i,j  ]’2 [ ]’0 : 1<=j<=n; /* r_  34,i  */  [w  i  ]’2 [wt  i  ]’0 –> [Ab  i+1  ]’2 [ ]’0; /* r_  35,i  */  [c  i  ]’2 [dt  i  ]’0 –> [Bb  i+1  ]’2 [ ]’0; /* r_  36,i  */  [z  i  ]’2 [zt  i  ]’0 –> [Cb  i+1  ]’2 [ ]’0; /* r_  37,i  */  [s  i  ]’2 [st  i  ]’0 –> [t  i  ,f  i  ]’2 [ ]’0; : 1<=i<=n; /* r_  38,j  */ [u  1,j  ]’2 [ut  1,j  ]’0 –> [Db  1,j+1  ,Db  2,j+1  ]’2 [ ]’0 : 1<=j<=n; /* r_  39,i,j  */ [u  i,j  ]’2 [ut  i,j  ]’0 –> [Db  i+1,j+1  ]’2 [ ]’0 : 2<=j<=n, 2<=i<=n;  /* r_  40  */ [S]’1 –> [ ]’1[ ]’1;  /* r_  41 ,i  */ [Db  i,n+1  ]’2 [vt  i,n+1  ]’0 –> [h  i  *2]’2 [ ]’0 : 1<=i<=n;  /* r_  42  */ [A  n+1  ]’1 [Ab  n+1  ]’2 –> [E  1  ]’1 [ ]’2; /* r_  43  */ [Ap  n+1  ]’1 [Bb  n+1  ]’2 –> [E  1  ]’1 [ ]’2;   /* r_  44,i  */  [T  i  ,Tp  i  ]’1 [h  i  ]’2 –> [Tb  i  ]’1 [ ]’2; /* r_  45,i  */  [F  i  ,Fp  i  ]’1 [h  i  ]’2 –> [Fb  i  ]’1 [ ]’2; : 1<=i<=n;   /* r_  46,i,j  */ [x  i,j  ]’3 [gp  i,j,0  ]’0 –> [g  i,j,1  *2]’3 [ ]’0; /* r_  47,i,j  */ [xb  i,j  ]’3 [gbp  i,j,0  ]’0 –> [gb  i,j,1  *2]’3 [ ]’0;  /*r_  48,i,j,k  */ [g  i,j,k  ]’3 [gp  i,j,k  ]’0 –> [g  i,j,k+1  *2]’3 [ ]’0; /*r_  49,i,j,k  */ [gb  i,j,k  ]’3 [gbp  i,j,k  ]’0–>[gb  i,j,k+1  *2]’3 [ ]’0; : 1<=k<=n-1; /* r_  50,i,j  */ [g  i,j,n  ]’3 [gp  i,j,n  ]’0 –> [e  i,j  ]’3 [ ]’0; /* r_  51,i,j  */ [gb  i,j,n  ]’3 [gbp  i,j,n  ]’0 –> [eb  i,j  ]’3 [ ]’0; : 1<=j<=m, 1<=i<=n; /* r_  52,j,k  */ [l  j,k  ]’3 [lb  j,k  ]’0 –> [l  j,k+1  *2]’3 [ ]’0 : 0<=k<=n-1 , 1<=j<=m; /* r_  53,j  */ [l  j,n  ] ’ 3 [lb  j,n  ]’0 –> [l  j  ]’3 [ ]’0:1<=j<=m;   /* r_  54,i,j  */ [Tb  i  ,E  j  ]’1 [ e  i,j  ]’3 –> [ E  i,j  ]’1 [ ]’3; /* r_  55,i,j  */ [Fb  i  ,E  j  ]’1 [eb  i,j  ]’3 –> [Eb  i,j  ]’1 [ ]’3; /* r_  56,i,j  */ [E  i,j  ]’1 [l  j  ]’3 –> [l  i,j  ]’1 [E  i,j  ]’3; /* r_  57,i,j  */ [Eb  i,j  ]’1 [l  j  ]’3 –> [lb  i,j  ]’1  [Eb  i,j  ]’3; /* r_  58,i,j  */ [l  i,j  ]’1 [E  i,j  ]’3 –> [Tb  i  ,E  j+1  ]’1 [ ]’3; /* r_  59,i,j  */ [lb  i,j  ]’1 [Eb  i,j  ]’3 –> [Fb  i  ,E  j+1  ]’1 [ ]’3; : 1<=j<=m, 1<=i<=n;  /*r_  60,i  */ [al  i  ]’3 [alb  i  ]’0–>[al  i+1  ]’3 [ ]’0: 0<=i<=4*n+3*m+3;  /* r_  61   */  [E  m+1  ]’1 [p]’3 –> [ ]’1 [yes]’3;  /* r_  62   */  [yes]’3 [ ]’0 –>[ ]’3 [yes]’0; /* r_  63   */  [al  4*n+3*m+4  ,p]’3 [ ]’0 –>[ ]’3 [no]’0;   /* Input cell: 3 */ def  define_input()  @ms(3) += xb  variable  i  ,clause  i  *valn  i  , x  variable  i  ,clause  i  *val  i   : 1<=i<=nvals;As described in Algorithm4 mentioned, the new tool extends the framework provided by P-Lingua and MeCoSim in terms of language accepted, simulation engines, and custom apps provided. We present all the aspects of the simulation in detail in Algorithm 4, but let us highlight the main features included at these different levels.New Elements in P-Lingua Framework. Taking the existing P-Lingua syntax for P systems introduced in [25] as a starting point, some extensions in the syntax of the language had to be included for tissue P systems with evolutional symport/antiport rules. We can mention some of them:(i)
New model type,tsec:@model<tsec>(ii)
Communication rules with two cells in the right hand of the rule, as:[Ebi,j]’1 [lj]’3 –> [lbi,j]’1[Ebi,j]’3  : 1<=j<=m, 1<=i<=n;[al4*n+3*m+4,p]’3 [  ]’0 –> [  ]’3 [no]’0;Custom App Based on MeCoSim. A new visual app has been customised using MeCoSim for the solution of SAT with TESAS P systems, including a series of relevant elements:(i)
Input tables to introduce the propositional formulas. The data introduced in these tables are then converted into parameters for the model that can be used to generate the correspondingcod(φ).(ii)
Use of existing SAT plugin to provide end users with a more natural way of introducing the formulas that are then converted to the format of the previous tables.(iii)
Definition of the output showing in different formats if the formula is satisfiable or not, generated from the objects of the computation.New Simulators for Tissue P Systems with Evolutional Rules. In the proof of Theorem 5, a deterministic algorithm was given to reproduce the behaviour of a computation of Π+m, with m an input multiset coding the input of the system. To mimic the algorithm described, several simulators were developed to compute P systems inTSEC. These simulators present subtle differences to select the rules to be applied, all of them compliant with the semantics defined for these systems (more details in Algorithm 4). The main differences among them are the following:(i)
Nondeterministic simulator: this simulator distinguishes two states (first communication rules are selected and later separation rules if no communication rules can be selected over a cell); this simulator visits cell by cell, according to its order of appearance in P-Lingua file; for each cell, the set of rules is shuffled and then applied as many times as possible, to guarantee maximality.(ii)
Deterministic by cell: the selection phase keeps the same two states of the previous simulator, but the cells are visited according to the lexicographical order of their labels. The set of rules inside each cell is not shuffled, but visited according to P-Lingua file order.(iii)
Deterministic by rule: this simulator is more similar to the deterministic algorithm described in the proof of Theorem 5. Thus, its selection phase, instead of going cell by cell (as the previous simulators), starts visiting at the most external level each rule. As described in Section 3, the rules are visited in the following order: direct communication between cells, then communication with environment, and finally separation, if possible; for each type of rules of the same type, it selects the rules following the order in the P-Lingua file.(iv)
Deterministic by rule, lexicographically: it performs the computations as described in the proof of Theorem 5. In addition to the most external visit of the different set of rules, in the same order of the previous simulator, inside a specific type of rules, the cells are visited according to the lexicographical order of their labels, thus meeting the structure defined in the referred section.Computer-Aided Design and Validation of Tissue P Systems with Evolutional Symport/Antiport Rules. The tools described played a significant role in the design, simulation, and validation of the solution for the SAT problem described in Theorem 8. Handling these complex solutions is hard and error-prone, and here the availability of the software tools helped significantly in the checking of the model and its properties, as detailed in the Appendix. Additionally, the development of the tools implied revisiting the general algorithms proposed for the model, thus paying attention to subtle details, given the need of reproducing every detail specified in the formal definition of the model, so these development tasks emerged as enriching complementary works to enhance the robustness of the computing models and their corresponding theoretical definitions.


## 5. Conclusions and Further Works

The computational complexity of tissue P systems with cell separation was first investigated in [29], where using communication rules with the length of at most 1, only tractable problems can be efficiently solved; and using communication rules with length at most 8, the SAT problem can be solved. In [42], it is shown that only tractable problems can be efficiently solved by tissue P systems with cell separation using communication rules with length at most 2; and the SAT problem can be solved by this kind of P systems using communication rules with length at most 3 [26]. In [33], tissue P systems with evolutional symport/antiport rules and cell division (TESAD P systems, for short) were proposed, where objects are moved from one region to another region and may be evolved during this process. It is shown that a limit on the efficiency of TESAD P systems is provided with evolutional communication rules of length at most 2; and when using evolutional communication rules of length at most 4, the SAT problem can be solved by TESAD P systems.In this work, membrane fission as a mechanism to generate an exponential workspace (expressed in terms of number of membranes and number of objects) has been considered instead of membrane division, in the framework of tissue P systems with evolutional symport/antiport rules. The computational efficiency of this kind of tissue P systems has been investigated. In this context, the main contributions of the paper are the following: (a) only problems in classP can be efficiently solved by means of families of tissue P systems with cell separation and evolutional communication rules of length at most (n,1) (or rules of length at most (1,n)), for each natural number n≥1; (b) computationally hard problems can be solved in polynomial time by recognizer TESAS P systems when using evolutional communication rules of length at most (n,2), for each natural number n≥3; and (c) a new MeCoSim based simulator has been designed to check the correctness of the solution to the SAT problem.As future works, we propose the following:(1)
In Section3, a polynomial time solution to the SAT problem by means of a family of tissue P systems fromTSEC(3,2) has been provided. It remains open whetherNP-complete problems can be efficiently solved by tissue P systems fromTSEC(2,2). What about the computational efficiency ofTSEC(2,n), for each natural number n≥2? Moreover, the solution to the SAT problem in Theorem 8 has both evolutional symport rules and evolutional antiport rules. It is of interest to investigate the computational power of tissue P systems with cell separation that use only either evolutional symport or evolutional antiport rules.(2)
In the framework of tissue P systems, the environment is a singular region since the objects initially placed in it have an arbitrary large number of copies. Tissue P systems with cell separation and without environment (the alphabet of the environment is empty) were considered in [43]. It would be interesting to analyze the computational efficiency of recognizer TESAS P systems when the alphabet of the environment is an empty set.(3)
Besides much investigated maximal parallelism, several ways of using rules were also considered in membrane computing, such as flat maximal parallelism [44, 45]. It remains open what the computation power of recognizer TESAS P systems working in a flat maximally parallel manner is.(4)
In [33], recognizer TESA P systems with cell division were introduced and the length of an evolutional communication rule was defined as the total number of objects involved in it. The computational efficiency ofTDEC(4), the class of all recognizer TESA P systems with cell division using evolutional communication rules with length at most 4, was provided. We propose to analyze the efficiency of recognizer TESA P systems with cell division with respect to the length of evolutional communication rules given in this paper: length(r)=(length(LHS(r)),length(RHS(r))). In fact, the solution to SAT problem provided in the cited paper corresponds to a family fromTDEC(3,2). What about the computational efficiency ofTDEC(2,n), for each natural number n≥2?



---

*Source: 3745210-2018-04-23.xml*