# Tuning Frontiers of Efficiency in Tissue P Systems with Evolutional Communication Rules

Authors: David Orellana-Martín; Luis Valencia-Cabrera; Bosheng Song; Linqiang Pan; Mario J. Pérez-Jiménez
Journal: Complexity
 (2021)

---

## Abstract

Over the last few years, a new methodology to address theP versus NP problem has been developed, based on searching for borderlines between the nonefficiency of computing models (only problems in class P can be solved in polynomial time) and the presumed efficiency (ability to solve NP-complete problems in polynomial time). These borderlines can be seen as frontiers of efficiency, which are crucial in this methodology. “Translating,” in some sense, an efficient solution in a presumably efficient model to an efficient solution in a nonefficient model would give an affirmative answer to problem P versus NP. In the framework of Membrane Computing, the key of this approach is to detect the syntactic or semantic ingredients that are needed to pass from a nonefficient class of membrane systems to a presumably efficient one. This paper deals with tissue P systems with communication rules of type symport/antiport allowing the evolution of the objects triggering the rules. In previous works, frontiers of efficiency were found in these kinds of membrane systems both with division rules and with separation rules. However, since they were not optimal, it is interesting to refine these frontiers. In this work, optimal frontiers of the efficiency are obtained in terms of the total number of objects involved in the communication rules used for that kind of membrane systems. These optimizations could be easier to translate, if possible, to efficient solutions in a nonefficient model.


---

## Body

## 1. Introduction

In biology, some basic requirements are proposed in order to define when something can be considered alive: replication, energy production, proteins synthesis, and metabolic processes. The minimal unit that meets these requirements is the cell. Usually, we find multiple cells forming larger structures, interchanging information between them in order to collaborate, improving in this way their lifespan. Membrane computing is a branch of natural computing inspired by the structure, organization, and functioning of living cells. In the seminal paper [1], computing devices are introduced having an internal structure of cell-like membranes (a rooted tree), delimiting compartments in which multisets of objects are placed. The objects evolve and pass through membranes in a synchronous parallel manner according to given evolution rules, also associated with the membranes. In [2], a new type of computing devices inspired by intercellular communication and cooperation between neurons was considered. They consist of a network of unit processors, cells, dealing with symbols and communicating these symbols along channels specified in advance, based on the biological phenomenon of trans-membrane transport of couples of chemicals. The synchronized movement of such chemical substances present in a cell was modelled in [3]: groups of objects can pass together through a region either in the same (described by symport rules) or in the opposite direction (described by antiport rules). In these models, no change (evolution) occurs in the objects involved during their movement, that is, they remain unchanged after the application of symport/antiport rules. We refer the reader to [4, 5] for a further introduction to the field of membrane computing. Apart from applications in synthetic biology, ecology, engineering, and physics, among others (see [6–8] for a wide view of the state-of-the-art), membrane computing has been broadly used as a computational framework to study more theoretical areas such as computability theory and computational complexity theory.The tractability of abstract problems is defined through polynomial-time solvability by deterministic Turing machines [9]. P is the class of tractable problems. A computing model is called efficient if it is capable of providing polynomial-time solutions to intractable problems. It is widely believed that P ≠ NP, thus, NP-complete problems (the hard problems in NP) are called presumably intractable problems. A computing model is called presumably efficient if it is able to provide polynomial-time solutions to NP-complete problems.Let us consider two modelsM1 and M1 in a computing paradigm (for instance, in membrane computing) such that M2 is obtained from M1 by adding some syntactic or semantic ingredients. If M1 is a nonefficient model and M2 is a presumably efficient one, then the ingredients needed to obtain M2 from M1 provide a frontier between the tractability of abstract problems and the presumed intractability. In some sense, passing from M1 to M2 amounts to passing from the nonefficiency to the presumed efficiency. Each such borderline provides a tool to tackle the P versus NP problem.Decision problems are associated with languages in such a manner that solving a decision problem is defined by recognizing the language associated with it. Hence, recognizer membrane systems were defined in [10] (called decision P systems) and complexity classes associated with these systems were introduced in [11]. Over the last few years, the previous methodology for addressing the P versus NP problem has been applied in the framework of membrane computing. Specifically, in the framework of cell-like P systems with active membranes, a frontier between the nonefficiency and the presumed efficiency was obtained by forbidding division rules [12] or permitting them [13]. In the framework of tissue-like P systems with symport/antiport rules, (optimal) frontiers between the nonefficiency and the presumed efficiency, in terms of both the length of the rules and the kinds of rules able to construct an exponential workspace in terms of cells, have been obtained [14–17].In [18], a new kind of tissue P systems based on the communication of cells within a living tissue is studied, where objects can evolve when the rules are applied. Specifically, tissue P systems with division rules using evolutional symport/antiport rules have been considered. In that paper, the length of a communication rule is defined as the total number of objects involved in it. For each natural number n≥1, TDℰCn denotes the class of recognizer tissue P systems with division rules using evolutional communication rules of length at most n. The nonefficiency of the computing model TDℰC2 has been established by using the dependency graph technique, and a polynomial-time uniform solution to the SAT problem by a family of membrane systems from TDℰC4 has been given in [18]. Therefore, passing from evolutional communication rules of length at most 2 to evolutional communication rules of length at most 4 amounts to passing from the nonefficiency to the presumed efficiency. The following question then arises: What is the efficiency of the complexity class PMCTDℰC3?In [19], tissue P systems with evolutional symport/antiport rules are studied, where separation rules instead of division rules are used as a mechanism to create an exponential workspace in polynomial time. In that paper, for each pair of natural numbers k1≥1,k2≥1, TDℰCk1,k2 denotes the class of recognizer tissue P systems with separation rules using evolutional communication rules such that the total number of objects involved in the left-hand side (LHS) is at most k1 and the total number of objects involved in the right-hand side (RHS) is at most k2. The nonefficiency of TDℰC1,n and TDℰCn,1, for each n≥1, has been established using the algorithmic technique. On the other hand, the presumed efficiency of TDℰC3,2 has been shown.The reader is supposed to have knowledge about languages, multisets, and other questions usually used in this kind of works. In any case, for a gentle introduction to them, we refer the reader to [20].In this work, we deal with tissue P systems with evolutional symport/antiport rules where division rules or separation rules are used as mechanisms to create an exponential workspace in polynomial time. Following [19], for each pair of natural numbers k1≥1,k2≥1, the class TDℰCk1,k2 is defined similarly to TDℰCk1,k2, replacing separation rules by division rules. Following [18], for each natural number n≥1, TDℰCn is defined similarly to TDℰCn, replacing division by separation rules. For each pair of natural numbers k1≥1,k2≥1, we have TDℰCk1,k2⊆TDℰCk1+k2 and TDℰCk1,k2⊆TDℰCk1+k2.This paper focuses on the nonefficiency ofTDℰC1,n, for each n≥1, and the presumed efficiency of TDℰC2,1 and TDℰC2,2. Specifically, we prove the following results: (1) For each natural number n≥1, we have P=PMCTDℰC1,n; (2) the computing model TDℰC2,1 is presumably efficient, that is, NP∪co-NP⊆PMCTDℰC2,1; (3) the computing model TDℰC2,2 is presumably efficient, that is, NP∪co-NP⊆PMCTDℰC2,2. Bearing in mind that TDℰC2,1⊆TDℰC3⊆TDℰC4 and TDℰC2,2⊆TDℰC3,2, the presumed efficiency of TDℰC3, TDℰC4, and TDℰC3,2 follows, closing the question raised about TDℰC3, among others. In this manner, the results obtained in [18, 19] are complemented and improved.This paper is organized as follows: Tissue P systems with division or separation rules and evolutional symport/antiport rules are defined inSection 2. The nonefficiency of TDℰC1,n, for each n≥1, is established in Section 3, and two polynomial-time uniform solutions to the SAT problem by families of systems from TDℰC2,1 and TSℰC2,2 are provided in Sections 4 and 5, respectively. Finally, some conclusions and interesting open research lines are presented.


## 2. Tissue P Systems with Evolutional Communication Rules

Let us briefly recall the definition of recognizer tissue P systems with evolutional symport/antiport rules using division or separation rules as a mechanism to construct an exponential workspace in polynomial time.Definition 1.
A recognizer tissue P system with division/separation rules and evolutional communication rules of degreeq≥1 (where q is the number of cells present in the system) is a tuple(1)Π=Γ,Γ0,Γ1,E,Σ,ℳ1,…,ℳq,ℛ,iin,iout,where(i)
Γ, E,Σ are finite alphabets such that E⊆Γ, Σ⊆Γ∖ℰ, and the alphabet Γ has two distinguished objects yes and no(ii)
Γ0,Γ1 is a partition of Γ; that is, Γ0,Γ1≠∅,Γ0∩Γ1=∅,Γ0∪Γ1=Γ(iii)
ℳ1,…,ℳq are multisets over Γ∖Σ(iv)
ℛ is a finite set of rules of the following forms:(1)
Evolutional communication rules:(a)uij⟶iu′j, where i,j∈0,…,q, i≠j, u∈M+Γ, u′∈MΓ, and if i=0, then alphu∩Γ∖ℰ≠∅evolutional symport rules(b)uivj⟶v′iu′j, where i,j∈0,…,q,i≠j,u,v∈M+Γ,u′,v′∈MΓevolutional antiport rules(2)
Division rules:ai⟶bici, where i∈1,…,q,i≠iout,a,b,c∈Γ(3)
Separation rules:ai⟶Γ0iΓ1i, where i∈1,…,q,i≠iout,a∈Γ(v)
iin∈1,…,q and iout=0 (that is, the label of the environment)(vi)
IfC is a computation of Π then C is a halting computation and either object yes or object no (but not both) must have been released into the output region, and only at the last step of the computation
The semantic concepts (configuration, transition step, and computation) in this kind of recognizer membrane systems can be found in [18, 19]. Only division rules or separation rules (but not both) are considered, and in the case of recognizer tissue P systems with division rules, the partition Γ0,Γ1 can be removed from the expression.
In [18], the length of an evolutional communication rule r is defined as the total number of objects involved in the rule. For each natural number n≥1, TDℰCn (resp., TSℰCn) denotes the class of recognizer tissue P systems with division rules (resp., separation rules) using evolutional communication rules of length at most n.
Following [19], for each pair of natural numbers k1≥1,k2≥1, TDℰCk1,k2 (resp., TSℰCk1,k2) denotes the class of recognizer tissue P systems with division rules (resp., separation rules) using evolutional communication rules such that the total number of objects involved in the left-hand side (LHS) (that is, the objects before the arrow in evolutional communication rules) is at most k1 and the total number of objects involved in the right-hand side (RHS) (that is, the objects after the arrow in evolutional communication rules) is at most k2. Obviously, for each pair of natural numbers k1≥1,k2≥1, we have TDℰCk1,k2⊆TDℰCk1+k2 and TSℰCk1,k2⊆TSℰCk1+k2. It is important to remark that, in this type of study, we do not take into account the number of objects implicitly involved neither in division nor in separation rules.


## 3. The Nonefficiency ofTDℰC1,n

The nonefficiency ofTSℰC1,n, for each natural number n≥1, has been shown by using the dependency graph technique in [19]. Let us recall that this technique consists in the following: if Πt|t∈ℕ is a family of systems from TSℰC1,n solving a decision problem X in polynomial time and uniform way, then a directed graph GΠsu+codu (with a source node) is associated with each instance u∈IX, in such a manner that every computation C of Πsu+codu is an accepting computation if and only if there exists a path in GΠsu+codu from the source node to yes,env. When working with membrane systems TSℰC1,n, each separation rule of the form ai⟶Γ0iΓ1i provides a single node a,i to the corresponding dependency graph, but no new arc is added since no new objects are created by the application of such a rule. In the case of membrane systems from TDℰC1,n, we can adapt the proof given in [19], taking into account the fact that a division rule ai⟶aibi provides three new nodes, a,i, b,i, and c,i to the corresponding dependency graph, and two new arcs: a,i,b,i and a,i,c,i. Of course, this process keeps having a polynomially bounded number of nodes and arcs, so the search for a path in the dependency graph from the source node to yes,env is still polynomial-time bounded. Therefore, for each natural number n≥1, the nonefficiency of TDℰC1,n follows.Theorem 1.
For each natural numbern≥1, we have P=PMCTDℰC1,n.


## 4. A Solution toSAT in TDℰC2,1

We provide here a solution toSAT by means of a family of recognizer tissue P systems Π=Πt|t∈ℕ from TDℰC2,1. Given a Boolean formula φ in CNF and simplified with n variables and p clauses, the system Πsφ+codφ processes it, being sφ=n,p and codφ=xi,j,0|xi∈Cj∪x¯i,j,0|¬xi∈Cj∪xi,j,0∗|xi∉Cj,¬xi∉Cj and returns the answer to its satisfiability.For eachn,p∈ℕ, we consider the recognizer P system(2)Πn,p=Γ,E,Σ,ℳ1,…,ℳnp+3,ℛ,iin,iout,where we have the following:(i)
Working alphabetΓ:(3)yes,no,y1,y2,n1,n2,n3,#∪ai,j,Ti,j,Fi,j|1≤i≤n,1≤j≤p∪xi,j,k,x¯i,j,k,xi,j,k∗|1≤i≤n,1≤j≤p,0≤k≤np+1∪αj∣1≤j≤p+1∪δk∣0≤k≤np+4∪δk′∣0≤k≤np+2(ii)
Input alphabetΣ=xi,j,0,x¯i,j,0,xi,j,0∗|1≤i≤n,1≤j≤p.(iii)
Environment alphabetE=γ.(iv)
ℳk=∅,1≤k≤np;ℳnp+1=δ0;ℳnp+2=ai,j|1≤i≤n,1≤j≤p∪αj|1≤j≤p+1;ℳnp+3=δ0′(v)
The rule setℛ consists of the following rules:(1)
Rules to generatep copies of the 2n true possible truth assignments. For this, 2np partial truth assignments will be generated.(4)ai,jnp+2⟶Ti,jnp+2Fi,jnp+2Ti,jFi,j′np+20⟶np+2#0for1≤i≤n,1≤j,j′≤p.(2)
Rules to generate2np copies of codφ.(5)xi,j,0np+1i+n⋅j−1⟶np+1xi,j,1i+n⋅j−1x¯i,j,0np+1i+n⋅j−1⟶np+1x¯i,j,1i+n⋅j−1xi,j,0∗np+1i+n⋅j−1⟶np+1xi,j,1∗i+n⋅j−1for1≤i≤n,1≤j≤p,xi,j,ki+n⋅j−1⟶xi,j,k+1i+n⋅j−1xi,j,k+1i+n⋅j−1x¯i,j,ki+n⋅j−1⟶x¯i,j,k+1i+n⋅j−1x¯i,j,k+1i+n⋅j−1xi,j,k∗i+n⋅j−1⟶xi,j,k+1∗i+n⋅j−1xi,j,k+1∗i+n⋅j−1for1≤i≤n,1≤j≤p,1≤k≤np,δ0′np+3γ0⟶δ1′np+30,δk′np+3⟶δk+1′np+3δk+1′np+3for1≤k≤np,δnp+1′np+3γ0⟶δnp+2′np+30.(3)
Rules to check which clauses are satisfied by the truth assignments.(6)Ti,jnp+2xi,j,np+1i+n⋅j−1⟶cjnp+2i+n⋅j−1Ti,jnp+2x¯i,j,np+1i+n⋅j−1⟶#np+2i+n⋅j−1Ti,jnp+2xi,j,np+1∗i+n⋅j−1⟶#np+2i+n⋅j−1Fi,jnp+2xi,j,np+1i+n⋅j−1⟶#np+2i+n⋅j−1Fi,jnp+2x¯i,j,np+1i+n⋅j−1⟶cjnp+2i+n⋅j−1Fi,jnp+2xi,j,np+1∗i+n⋅j−1⟶#np+2i+n⋅j−1for1≤i≤n,1≤j≤p.(4)
Rules to check if all the clauses are satisfied by a truth assignment.(7)αp+1np+2δnp+2′np+3⟶αp+1′np+2np+3,cjαjnp+2np+3⟶np+2#np+3for1≤j≤p.(5)
General counter.(8)δknp+1γ0⟶δk+1np+100≤k≤np+3.(6)
Rules to return a negative answer.(9)αjαp+1′np+20⟶np+2n10for1≤j≤p,n10np+2⟶0n2np+2,n2np+2δnp+4np+1⟶n3np+2np+1,n3np+20⟶np+2no0.(7)
Rules to return a positive answer.(10)αp+1′np+2δnp+4np+1⟶y1np+2np+1,y1np+2γ0⟶y2np+20,y2np+20⟶np+2yes0.(vi)
The input cell is the cell labelled bynp+1 (iin=np+1) and the output zone is the environment (iout=env).Letφ be a Boolean formula in simplified CNF. The P system Πsφ+codφ will follow a brute-force algorithm in the framework of tissue P systems with evolutional symport/antiport rules with length, at most, 2,1 and division rules, and it consists of the following stages:(1)
Generation stage: using rules from (1),p copies of the 2n possible truth assignments associated with variables x1,…,xn will be generated in cells labelled by np+2. For this, 2np−2n “partial” truth assignments will be generated too; that is, some cells will contain different assignments for a single variable, but these objects will be “cancelled” by the application of the rule Ti,jFi,j′np+20⟶np+2#0. In parallel, 2np copies of each object xi,j,np+1,x¯i,j,np+1,xi,j,np+1∗ that appears in codφ will be generated by applying rules from (2). In order to synchronize the process, the third subscript, k, will “evolve” until reaching np+1. This stage takes exactly np+1 computation steps.(2)
First checking stage: in this stage, by means of the application of rules from (3), thep copies of each one of the 2n possible truth assignments associated with variables x1,…,xn cooperate with objects xi,j,np+1, x¯i,j,np+1, xi,j,np+1∗ by using rules from (3) in order to know which clauses are satisfied by each truth assignment. It is worth pointing out that through this checking stage, the 2np−2n partial truth assignments cannot satisfy φ if it is unsatisfiable. This stage takes 1 computation step.(3)
Second checking stage: by using rules from (4), objectαj is removed from a cell labelled as np+2 if and only if the truth assignment associated with this cell makes the clause Cj true. Therefore, a cell labelled as np+2 will encode a truth assignment that makes φ true if and only if it does not contain any object αj at the end of this stage, taking exactly 1 computation step.(4)
Output stage: finally, rules from (5)–(7) will send either an objectyes or an object no to the environment, depending on whether the formula is satisfactory or not. This stage takes exactly 4 computation steps, regardless of the answer being affirmative or negative.


### 4.1. Formal Verification

In this section, an exhaustive verification of the system is given.


#### 4.1.1. Generation Stage

The purpose of this stage is twofold: on the one hand,2np objects of each li,j,np+1,l∈x,x¯,x∗,1≤i≤n,1≤j≤p will be generated in cells i+n⋅j−1. On the other hand, 2n valid truth assignments will be generated in cells labelled by np+2. For that, 2np of such cells will be generated, each of them containing a truth assignment. Of course, there will be repeated truth assignments, but in this framework, due to the restrictions of the length of the rules, it seems necessary to create all the possible assignments (including the ones where two different truth values are assigned to a single variable), and then “remove” the incompatibilities.Proposition 1.
LetC=C0,C1,…,Cq be a computation of the system Πsφ with input multiset codφ.(i)
For eachk (0≤k≤np) at configuration Ck, we have the following:(1)
C0i+n⋅j−1=∅ and there are 2k−1 cells labelled by i+n⋅j−1 in the configuration Ck such that each of them contains an object li,j,k, being l=x if xi is a literal of the clause Cj, x¯ if ¬xi is a literal of the clause Cj , and x∗ if neither xi nor ¬xi are literals of the clause Cj, for k≥1(2)
C0np+1=δk∪codφ and Cknp+1=δk for k>0(3)
There are2k cells labelled by np+2 in the configuration Ck such that each of them contains the set α1,…,αp+1, np−k objects from the set a1,1,…,a1,p,…,an,1,…,an,p and less than k or k objects from the set R1,1,…,R1,p,…,Rn,1,…,Rn,p,R∈T,F(4)
C0np+3=δ0′ and there are 2k−1 cells labelled by np+3 in the configuration Ck such that each of them contains an object δk′, for k≥1(ii)
In the configurationCnp+1, we have that there are 2np cells labelled by i+n⋅j−1 for each 1≤i≤n,1≤j≤p such that each of them contains an object li,j,np+1 being l=x if xi is a literal of the clause Cj, x¯ if ¬xi is a literal of the clause Cj , and x∗ if neither xi nor ¬xi are literals of the clause Cj, Cnp+1np+1=δnp+1; there are 2np cells labelled by np+2 such that each of them contains the set α1,…,αp+1, less than np or np objects from the set R1,1,…,R1,p,…,Rn,1,…,Rn,p,R∈T,F and there are 2np cells labelled by np+3 such that each of them contains an object δnp+1′Proof.
(i) is going to be proved by induction onk(i)
The base casek=0 is trivial because at the initial configuration, we have the following:(1)
C0i+n⋅j−1=∅(2)
C0np+1=δ0∪codφ(3)
There is one cell labelled bynp+2 such that contains the set α1,…,αp+1 and the set a1,1,…,a1,p,…,an,1,…,an,p(4)
There is one cell labelled bynp+3 such that it contains an object δ0′Then, configurationC0 yields configuration C1 by applying the rules:(11)ai,jnp+2⟶Ti,jnp+2Fi,jnp+2xi,j,0np+1i+n⋅j−1⟶np+1xi,j,1i+n⋅j−1x¯i,j,0np+1i+n⋅j−1⟶np+1xi,j,1i+n⋅j−1xi,j,0∗np+1i+n⋅j−1⟶np+1xi,j,1∗i+n⋅j−1for1≤i≤n,1≤j≤p.δ0′np+3γ0⟶δ1′np+30δ0np+1γ0⟶δ1np+10Thus, we have the following:(1)
C1i+n⋅j−1=li,j,1, being l=x if xi is a literal of the clause Cj, x¯ if ¬xi is a literal of the clause Cj and x∗ if neither xi nor ¬xi are literals of the clause Cj(2)
C1np+1=δ1(3)
There are two cells labelled bynp+2 such that contains the set α1,…,αp+1, np−1 objects of the set a1,1,…,a1,p,…,an,1,…,an,p and one object Ti,j and one object Fi,j, respectively, for a i,1≤i≤n and a j,1≤j≤p(4)
There is one cell labelled bynp+3 such that it contains an object δ1′(ii)
Assuming that, by induction, the result is true fork (0≤k≤np); that is, that we have the following:(1)
C0i+n⋅j−1=∅ and there are 2k−1 cells labelled by i+n⋅j−1 in the configuration Ck such that each of them contains an object li,j,k, being l=x if xi is a literal of the clause Cj, x¯ if ¬xi is a literal of the clause Cj and x∗ if neither xi nor ¬xi are literals of the clause Cj, for k≥1(2)
C0np+1=δk∪codφ and Cknp+1=δk for k>0(3)
There are2k cells labelled by np+2 in the configuration Ck such that each of them contains the set α1,…,αp+1, np−k objects from the set a1,1,…,a1,p,…,an,1,…,an,p and less than k or k objects from the set R1,1,…,R1,p,…,Rn,1,…,Rn,p,R∈T,F(4)
C0np+3=δ0′ and there are 2k−1 cells labelled by np+3 in the configuration Ck such that each of them contains an object δk′ for k≥1Then, configurationCk yields configuration Ck+1 by applying the rules:(12)ai,jnp+2⟶Ti,jnp+2Fi,jnp+2Ti,jFi,j′np+20⟶np+2#0for1≤i≤n,1≤j,j′≤p,xi,j,ki+n⋅j−1⟶xi,j,k+1i+n⋅j−1xi,j,k+1i+n⋅j−1x¯i,j,ki+n⋅j−1⟶x¯i,j,k+1i+n⋅j−1x¯i,j,k+1i+n⋅j−1xi,j,k∗i+n⋅j−1⟶xi,j,k+1∗i+n⋅j−1xi,j,k+1∗i+n⋅j−1for1≤i≤n,1≤j≤p,δk′np+3⟶δk+1′np+3δk+1′np+3,δknp+1γ0⟶δk+18inp+10.Thus, we have the following:(1)
There are2k cells labelled by i+n⋅j−1 in the configuration Ck such that each of them contains an object li,j,k+1, being l=x if xi is a literal of the clause Cj, x¯ if ¬xi is a literal of the clause Cj and x∗ if neither xi nor ¬xi are literals of the clause Cj(2)
Ck+1np+1=δk+1(3)
There are2k+1 cells labelled by np+2 in the configuration Ck+1 such that each of them contains the set α1,…,αp+1, np−k+1 objects from the set a1,1,…,a1,p,…,an,1,…,an,p and less than k+1 or k+1 objects from the set R1,1,…,R1,p,…,Rn,1,…,Rn,p,R∈T,F(4)
There are2k cells labelled by np+3 in the configuration Ck+1 such that each of them contains an object δk+1′(iii)
In order to prove (ii) it is enough to take into account the fact that, from (i), we have the following:(1)
There are2np−1 cells labelled by i+n⋅j−1 in the configuration Cnp such that each of them contains an object li,j,np, being l=x if xi is a literal of the clause Cj, x¯ if ¬xi is a literal of the clause Cj and x∗ if neither xi nor ¬xi are literals of the clause Cj(2)
Cnpnp+1=δnp(3)
There are2np cells labelled by np+2 in the configuration Cnp such that each of them contains the set α1,…,αp+1 and less than np or np objects from the set R1,1,…,R1,p,…,Rn,1,…,Rn,p,R∈T,F, representing a truth assignment(4)
There are2np−1 cells labelled by np+3 in the configuration Cnp such that each of them contains an object δnp′Then, configurationCnp yields configuration Cnp+1 by applying the rules:(13)Ti,jFi,j′np+20⟶np+2#0for1≤i≤n,1≤j,j′≤p,xi,j,npi+n⋅j−1⟶xi,j,np+1i+n⋅j−1xi,j,np+1i+n⋅j−1x¯i,j,npi+n⋅j−1⟶x¯i,j,np+1i+n⋅j−1x¯i,j,np+1i+n⋅j−1xi,j,np∗i+n⋅j−1⟶xi,j,np+1∗i+n⋅j−1xi,j,np+1∗i+n⋅j−1for1≤i≤n,1≤j≤p,δnp′np+3⟶δnp+1′np+3δnp+1′np+3,δnpnp+1γ0⟶δnp+1np+10.Then, we have the following:(1)
There are2np cells labelled by i+n⋅j−1 in the configuration Cnp+1 such that each of them contains an object li,j,np+1, being l=x if xi is a literal of the clause Cj, x¯ if ¬xi is a literal of the clause Cj and x∗ if neither xi nor ¬xi are literals of the clause Cj(2)
Cnp+1np+1=δnp+1(3)
There are2np cells labelled by np+2 in the configuration Cnp+1 such that each of them contains the set α1,…,αp+1 and less than np or np objects from the set R1,1,…,R1,p,…,Rn,1,…,Rn,p,R∈T,F, representing a truth assignment(4)
There are2np cells labelled by np+3 in the configuration Cnp+1 such that each of them contains an object δnp+1′


#### 4.1.2. First Checking Stage

From the previous stage, we have thatCnp+1np+1=δnp+1, there are 2np cells labelled by np+3 which contains an object δnp+1′, 2np cells labelled by np+2 that contains objects α1,…,αp,αp+1 and a set of objects R1,1,R1,2,…,R1,p,R2,1,…,R2,p,…,Rn,1…,Rn,pR∈T,F, representing the truth assignment associated with that cell. Not all objects of such a set have to be present in a single cell since they could have been consumed by the application of a rule Ti,jFi,j′np+20⟶np+2#0. Moreover, there exist 2np cells labelled by i+n⋅j−1,1≤i≤n,1≤j≤p each of them containing an object li,j,np+1. Then, by the application of the rules from 2.1, objects cj will be created in the cells labelled by np+2 such that the truth assignment associated with such cell satisfies clause Cj due to any literal of it. Besides, rules δnp+1np+1γ0⟶δnp+2np+10,δnp+1′np+3γ0⟶δnp+2′np+30 are applied.Therefore, we haveCnp+2np+1=δnp+2, there are 2np cells labelled by np+3 which contains an object δnp+2′, 2np cells labelled by np+2 that contains objects α1,…,αp,αp+1 and a multiset of objects from c1,…,cp, representing the clauses satisfied by the truth assignment associated with that cell. The remaining objects li,j,np+1 in cells labelled by i+n⋅j−1 are not going to be taken into account from now since they cannot “react” with something from this point of the computation.


#### 4.1.3. Second Checking Stage

The stepnp+3 is devoted to checking whether all the clauses Cj,1≤j≤p of the Boolean formula φ have been satisfied by the truth assignment associated with each cell labelled by np+2. We have that Cnp+2np+1=δnp+2, and there will be 2np cells labelled by np+3 which contains an object δnp+2′ and 2np cells labelled by np+2 such that contains objects α1,…,αp,αp+1 and objects cj,1≤j≤p corresponding to the clauses satisfied by the truth assignment associated with that cell. Then, by applying the rules αp+1np+2δnp+2′np+3⟶αp+1′np+2np+3,cjαjnp+2np+3⟶np+2#np+3,δnp+2np+1γ0⟶δnp+3np+10, we obtain the following: Cnp+3np+1=δnp+3 and there will be 2np cells labelled by np+2 that will contain an object αj if and only if clause Cj has not been satisfied by the truth assignment associated with such cell.


#### 4.1.4. Output Stage

The output phase starts at thenp+4-th step and takes exactly four steps, regardless of whether the input formula φ is satisfied or not by some truth assignment.(i)
Affirmative answer: if the input formulaφ of SAT problem is satisfiable then at least one of the truth assignments from a cell with label np+2 has satisfied all clauses. Therefore, there will be at least one cell labelled by np+2 such that it will not have any object αj, since all of them have been “consumed” in some sense by an object cj. Therefore, in the step np+4, object δnp+3 will evolve into δnp+4 by the application of the rule δnp+3np+1γ0⟶δnp+4np+10, besides the application of rules αjαp+1′np+20⟶np+2n10 in other cells. In the next step, since αp+1′ remains in a cell labelled by np+2, it can evolve with object δnp+4 by the rule αp+1′np+2δnp+4np+1⟶y1np+2np+1. Since there is only one object δnp+4, then we can be sure that the object y1 (that will produce the object yes later) is unique. Besides, objects n1 will be sent as n2 to cells labelled by np+2 in a nondeterministic way. In the np+5-th step, it will evolve into the object y2. Let us keep in mind that objects n2 cannot react with object δnp+4 since it has been consumed in the previous step. At the last step of the computation, the only rule applicable will be y2np+20⟶np+2yes0. Then, an object yes will be sent to the environment, and the computation halts.(ii)
Negative answer: if the input formulaφ of SAT problem is not satisfiactory, then none of the truth assignments encoded by a cell labelled as np+2 makes the formula φ true. Thus, in each cell, there will be at least one object of the type αj,1≤j≤p. It means that the clause Cj is not satisfied by the truth assignment corresponding to that cell. Therefore, at step np+3 rules αjαp+1′np+20⟶np+2n10 will be applied in all the cells. Therefore, at configuration Cnp+3 there will not be any object αp+1′ in the system, so object δnp+4 remains in the cell labelled by np+1. In the next step, objects n1 go to cells labelled by np+2, selected in a nondeterministic way. Since object δnp+4 is in the cell labelled as np+1 it can make object n2 evolve into object n3, and then in the last step, it is sent to the environment as an object no. Since there is no applicable rule, the system halts.Theorem 2.
SAT∈PMCTDℰC2,1Proof.
The family of P systems previously constructed verifies the following:(i)
Every system of the familyΠ is a recognizer P system from TDEC2,1.(ii)
The familyΠ is polynomially uniform by Turing machines because, for each n,p∈ℕ, the rules of Πn,p of the family are recursively defined from n,p∈ℕ, and the amount of resources needed to build an element of the family is of a polynomial order in n and p, as shown below:(1)Size of the alphabet:3n2p2+11np+p+17∈Θn2p2(2)
Initial number of cells:np+3∈Θnp(3)
Initial number of objects in cells:np+p+3∈Θnp(4)
Number of rules:3n2p2+np2+12np+2p+13∈Θn2p2(5)
Maximal number of objects involved in any rule:3∈Θ1(iii)
The paircod,s of polynomial-time computable functions defined fulfills the following: for each input formula φ of SAT problem, sφ is a natural number, codφ is an input multiset for the system Πsφ, and for each n∈ℕ, s−1n is a finite set.(iv)
The familyΠ is polynomially bounded: indeed, for each input formula φ of SAT problem, the deterministic P system Πsφ+codφ takes exactly np+7 steps, being n the number of variables in φ and p its number of clauses.(v)
The familyΠ is sound with regard to X,cod,s: for each formula φ, if the computation of Πsφ+codφ is an accepting computation, then φ is satisfiable.(vi)
The familyΠ is complete with regard to X,cod,s: for each input formula φ such that it is satisfiable, the computation of Πsφ+codφ is an accepting computation.Corollary 1.
NP∪co−NP⊆PMCTDℰC2,1Proof.
It is simple to prove this since it is known thatSAT is a NP-complete problem, SAT∈PMCTDℰC2,1 and the complexity class PMCTDℰC2,1 is closed under polynomial-time reduction and under complementary. □Corollary 2.
NP∪co−NP⊆PMCTDℰC3


## 4.1. Formal Verification

In this section, an exhaustive verification of the system is given.


### 4.1.1. Generation Stage

The purpose of this stage is twofold: on the one hand,2np objects of each li,j,np+1,l∈x,x¯,x∗,1≤i≤n,1≤j≤p will be generated in cells i+n⋅j−1. On the other hand, 2n valid truth assignments will be generated in cells labelled by np+2. For that, 2np of such cells will be generated, each of them containing a truth assignment. Of course, there will be repeated truth assignments, but in this framework, due to the restrictions of the length of the rules, it seems necessary to create all the possible assignments (including the ones where two different truth values are assigned to a single variable), and then “remove” the incompatibilities.Proposition 1.
LetC=C0,C1,…,Cq be a computation of the system Πsφ with input multiset codφ.(i)
For eachk (0≤k≤np) at configuration Ck, we have the following:(1)
C0i+n⋅j−1=∅ and there are 2k−1 cells labelled by i+n⋅j−1 in the configuration Ck such that each of them contains an object li,j,k, being l=x if xi is a literal of the clause Cj, x¯ if ¬xi is a literal of the clause Cj , and x∗ if neither xi nor ¬xi are literals of the clause Cj, for k≥1(2)
C0np+1=δk∪codφ and Cknp+1=δk for k>0(3)
There are2k cells labelled by np+2 in the configuration Ck such that each of them contains the set α1,…,αp+1, np−k objects from the set a1,1,…,a1,p,…,an,1,…,an,p and less than k or k objects from the set R1,1,…,R1,p,…,Rn,1,…,Rn,p,R∈T,F(4)
C0np+3=δ0′ and there are 2k−1 cells labelled by np+3 in the configuration Ck such that each of them contains an object δk′, for k≥1(ii)
In the configurationCnp+1, we have that there are 2np cells labelled by i+n⋅j−1 for each 1≤i≤n,1≤j≤p such that each of them contains an object li,j,np+1 being l=x if xi is a literal of the clause Cj, x¯ if ¬xi is a literal of the clause Cj , and x∗ if neither xi nor ¬xi are literals of the clause Cj, Cnp+1np+1=δnp+1; there are 2np cells labelled by np+2 such that each of them contains the set α1,…,αp+1, less than np or np objects from the set R1,1,…,R1,p,…,Rn,1,…,Rn,p,R∈T,F and there are 2np cells labelled by np+3 such that each of them contains an object δnp+1′Proof.
(i) is going to be proved by induction onk(i)
The base casek=0 is trivial because at the initial configuration, we have the following:(1)
C0i+n⋅j−1=∅(2)
C0np+1=δ0∪codφ(3)
There is one cell labelled bynp+2 such that contains the set α1,…,αp+1 and the set a1,1,…,a1,p,…,an,1,…,an,p(4)
There is one cell labelled bynp+3 such that it contains an object δ0′Then, configurationC0 yields configuration C1 by applying the rules:(11)ai,jnp+2⟶Ti,jnp+2Fi,jnp+2xi,j,0np+1i+n⋅j−1⟶np+1xi,j,1i+n⋅j−1x¯i,j,0np+1i+n⋅j−1⟶np+1xi,j,1i+n⋅j−1xi,j,0∗np+1i+n⋅j−1⟶np+1xi,j,1∗i+n⋅j−1for1≤i≤n,1≤j≤p.δ0′np+3γ0⟶δ1′np+30δ0np+1γ0⟶δ1np+10Thus, we have the following:(1)
C1i+n⋅j−1=li,j,1, being l=x if xi is a literal of the clause Cj, x¯ if ¬xi is a literal of the clause Cj and x∗ if neither xi nor ¬xi are literals of the clause Cj(2)
C1np+1=δ1(3)
There are two cells labelled bynp+2 such that contains the set α1,…,αp+1, np−1 objects of the set a1,1,…,a1,p,…,an,1,…,an,p and one object Ti,j and one object Fi,j, respectively, for a i,1≤i≤n and a j,1≤j≤p(4)
There is one cell labelled bynp+3 such that it contains an object δ1′(ii)
Assuming that, by induction, the result is true fork (0≤k≤np); that is, that we have the following:(1)
C0i+n⋅j−1=∅ and there are 2k−1 cells labelled by i+n⋅j−1 in the configuration Ck such that each of them contains an object li,j,k, being l=x if xi is a literal of the clause Cj, x¯ if ¬xi is a literal of the clause Cj and x∗ if neither xi nor ¬xi are literals of the clause Cj, for k≥1(2)
C0np+1=δk∪codφ and Cknp+1=δk for k>0(3)
There are2k cells labelled by np+2 in the configuration Ck such that each of them contains the set α1,…,αp+1, np−k objects from the set a1,1,…,a1,p,…,an,1,…,an,p and less than k or k objects from the set R1,1,…,R1,p,…,Rn,1,…,Rn,p,R∈T,F(4)
C0np+3=δ0′ and there are 2k−1 cells labelled by np+3 in the configuration Ck such that each of them contains an object δk′ for k≥1Then, configurationCk yields configuration Ck+1 by applying the rules:(12)ai,jnp+2⟶Ti,jnp+2Fi,jnp+2Ti,jFi,j′np+20⟶np+2#0for1≤i≤n,1≤j,j′≤p,xi,j,ki+n⋅j−1⟶xi,j,k+1i+n⋅j−1xi,j,k+1i+n⋅j−1x¯i,j,ki+n⋅j−1⟶x¯i,j,k+1i+n⋅j−1x¯i,j,k+1i+n⋅j−1xi,j,k∗i+n⋅j−1⟶xi,j,k+1∗i+n⋅j−1xi,j,k+1∗i+n⋅j−1for1≤i≤n,1≤j≤p,δk′np+3⟶δk+1′np+3δk+1′np+3,δknp+1γ0⟶δk+18inp+10.Thus, we have the following:(1)
There are2k cells labelled by i+n⋅j−1 in the configuration Ck such that each of them contains an object li,j,k+1, being l=x if xi is a literal of the clause Cj, x¯ if ¬xi is a literal of the clause Cj and x∗ if neither xi nor ¬xi are literals of the clause Cj(2)
Ck+1np+1=δk+1(3)
There are2k+1 cells labelled by np+2 in the configuration Ck+1 such that each of them contains the set α1,…,αp+1, np−k+1 objects from the set a1,1,…,a1,p,…,an,1,…,an,p and less than k+1 or k+1 objects from the set R1,1,…,R1,p,…,Rn,1,…,Rn,p,R∈T,F(4)
There are2k cells labelled by np+3 in the configuration Ck+1 such that each of them contains an object δk+1′(iii)
In order to prove (ii) it is enough to take into account the fact that, from (i), we have the following:(1)
There are2np−1 cells labelled by i+n⋅j−1 in the configuration Cnp such that each of them contains an object li,j,np, being l=x if xi is a literal of the clause Cj, x¯ if ¬xi is a literal of the clause Cj and x∗ if neither xi nor ¬xi are literals of the clause Cj(2)
Cnpnp+1=δnp(3)
There are2np cells labelled by np+2 in the configuration Cnp such that each of them contains the set α1,…,αp+1 and less than np or np objects from the set R1,1,…,R1,p,…,Rn,1,…,Rn,p,R∈T,F, representing a truth assignment(4)
There are2np−1 cells labelled by np+3 in the configuration Cnp such that each of them contains an object δnp′Then, configurationCnp yields configuration Cnp+1 by applying the rules:(13)Ti,jFi,j′np+20⟶np+2#0for1≤i≤n,1≤j,j′≤p,xi,j,npi+n⋅j−1⟶xi,j,np+1i+n⋅j−1xi,j,np+1i+n⋅j−1x¯i,j,npi+n⋅j−1⟶x¯i,j,np+1i+n⋅j−1x¯i,j,np+1i+n⋅j−1xi,j,np∗i+n⋅j−1⟶xi,j,np+1∗i+n⋅j−1xi,j,np+1∗i+n⋅j−1for1≤i≤n,1≤j≤p,δnp′np+3⟶δnp+1′np+3δnp+1′np+3,δnpnp+1γ0⟶δnp+1np+10.Then, we have the following:(1)
There are2np cells labelled by i+n⋅j−1 in the configuration Cnp+1 such that each of them contains an object li,j,np+1, being l=x if xi is a literal of the clause Cj, x¯ if ¬xi is a literal of the clause Cj and x∗ if neither xi nor ¬xi are literals of the clause Cj(2)
Cnp+1np+1=δnp+1(3)
There are2np cells labelled by np+2 in the configuration Cnp+1 such that each of them contains the set α1,…,αp+1 and less than np or np objects from the set R1,1,…,R1,p,…,Rn,1,…,Rn,p,R∈T,F, representing a truth assignment(4)
There are2np cells labelled by np+3 in the configuration Cnp+1 such that each of them contains an object δnp+1′


### 4.1.2. First Checking Stage

From the previous stage, we have thatCnp+1np+1=δnp+1, there are 2np cells labelled by np+3 which contains an object δnp+1′, 2np cells labelled by np+2 that contains objects α1,…,αp,αp+1 and a set of objects R1,1,R1,2,…,R1,p,R2,1,…,R2,p,…,Rn,1…,Rn,pR∈T,F, representing the truth assignment associated with that cell. Not all objects of such a set have to be present in a single cell since they could have been consumed by the application of a rule Ti,jFi,j′np+20⟶np+2#0. Moreover, there exist 2np cells labelled by i+n⋅j−1,1≤i≤n,1≤j≤p each of them containing an object li,j,np+1. Then, by the application of the rules from 2.1, objects cj will be created in the cells labelled by np+2 such that the truth assignment associated with such cell satisfies clause Cj due to any literal of it. Besides, rules δnp+1np+1γ0⟶δnp+2np+10,δnp+1′np+3γ0⟶δnp+2′np+30 are applied.Therefore, we haveCnp+2np+1=δnp+2, there are 2np cells labelled by np+3 which contains an object δnp+2′, 2np cells labelled by np+2 that contains objects α1,…,αp,αp+1 and a multiset of objects from c1,…,cp, representing the clauses satisfied by the truth assignment associated with that cell. The remaining objects li,j,np+1 in cells labelled by i+n⋅j−1 are not going to be taken into account from now since they cannot “react” with something from this point of the computation.


### 4.1.3. Second Checking Stage

The stepnp+3 is devoted to checking whether all the clauses Cj,1≤j≤p of the Boolean formula φ have been satisfied by the truth assignment associated with each cell labelled by np+2. We have that Cnp+2np+1=δnp+2, and there will be 2np cells labelled by np+3 which contains an object δnp+2′ and 2np cells labelled by np+2 such that contains objects α1,…,αp,αp+1 and objects cj,1≤j≤p corresponding to the clauses satisfied by the truth assignment associated with that cell. Then, by applying the rules αp+1np+2δnp+2′np+3⟶αp+1′np+2np+3,cjαjnp+2np+3⟶np+2#np+3,δnp+2np+1γ0⟶δnp+3np+10, we obtain the following: Cnp+3np+1=δnp+3 and there will be 2np cells labelled by np+2 that will contain an object αj if and only if clause Cj has not been satisfied by the truth assignment associated with such cell.


### 4.1.4. Output Stage

The output phase starts at thenp+4-th step and takes exactly four steps, regardless of whether the input formula φ is satisfied or not by some truth assignment.(i)
Affirmative answer: if the input formulaφ of SAT problem is satisfiable then at least one of the truth assignments from a cell with label np+2 has satisfied all clauses. Therefore, there will be at least one cell labelled by np+2 such that it will not have any object αj, since all of them have been “consumed” in some sense by an object cj. Therefore, in the step np+4, object δnp+3 will evolve into δnp+4 by the application of the rule δnp+3np+1γ0⟶δnp+4np+10, besides the application of rules αjαp+1′np+20⟶np+2n10 in other cells. In the next step, since αp+1′ remains in a cell labelled by np+2, it can evolve with object δnp+4 by the rule αp+1′np+2δnp+4np+1⟶y1np+2np+1. Since there is only one object δnp+4, then we can be sure that the object y1 (that will produce the object yes later) is unique. Besides, objects n1 will be sent as n2 to cells labelled by np+2 in a nondeterministic way. In the np+5-th step, it will evolve into the object y2. Let us keep in mind that objects n2 cannot react with object δnp+4 since it has been consumed in the previous step. At the last step of the computation, the only rule applicable will be y2np+20⟶np+2yes0. Then, an object yes will be sent to the environment, and the computation halts.(ii)
Negative answer: if the input formulaφ of SAT problem is not satisfiactory, then none of the truth assignments encoded by a cell labelled as np+2 makes the formula φ true. Thus, in each cell, there will be at least one object of the type αj,1≤j≤p. It means that the clause Cj is not satisfied by the truth assignment corresponding to that cell. Therefore, at step np+3 rules αjαp+1′np+20⟶np+2n10 will be applied in all the cells. Therefore, at configuration Cnp+3 there will not be any object αp+1′ in the system, so object δnp+4 remains in the cell labelled by np+1. In the next step, objects n1 go to cells labelled by np+2, selected in a nondeterministic way. Since object δnp+4 is in the cell labelled as np+1 it can make object n2 evolve into object n3, and then in the last step, it is sent to the environment as an object no. Since there is no applicable rule, the system halts.Theorem 2.
SAT∈PMCTDℰC2,1Proof.
The family of P systems previously constructed verifies the following:(i)
Every system of the familyΠ is a recognizer P system from TDEC2,1.(ii)
The familyΠ is polynomially uniform by Turing machines because, for each n,p∈ℕ, the rules of Πn,p of the family are recursively defined from n,p∈ℕ, and the amount of resources needed to build an element of the family is of a polynomial order in n and p, as shown below:(1)Size of the alphabet:3n2p2+11np+p+17∈Θn2p2(2)
Initial number of cells:np+3∈Θnp(3)
Initial number of objects in cells:np+p+3∈Θnp(4)
Number of rules:3n2p2+np2+12np+2p+13∈Θn2p2(5)
Maximal number of objects involved in any rule:3∈Θ1(iii)
The paircod,s of polynomial-time computable functions defined fulfills the following: for each input formula φ of SAT problem, sφ is a natural number, codφ is an input multiset for the system Πsφ, and for each n∈ℕ, s−1n is a finite set.(iv)
The familyΠ is polynomially bounded: indeed, for each input formula φ of SAT problem, the deterministic P system Πsφ+codφ takes exactly np+7 steps, being n the number of variables in φ and p its number of clauses.(v)
The familyΠ is sound with regard to X,cod,s: for each formula φ, if the computation of Πsφ+codφ is an accepting computation, then φ is satisfiable.(vi)
The familyΠ is complete with regard to X,cod,s: for each input formula φ such that it is satisfiable, the computation of Πsφ+codφ is an accepting computation.Corollary 1.
NP∪co−NP⊆PMCTDℰC2,1Proof.
It is simple to prove this since it is known thatSAT is a NP-complete problem, SAT∈PMCTDℰC2,1 and the complexity class PMCTDℰC2,1 is closed under polynomial-time reduction and under complementary. □Corollary 2.
NP∪co−NP⊆PMCTDℰC3


## 4.1.1. Generation Stage

The purpose of this stage is twofold: on the one hand,2np objects of each li,j,np+1,l∈x,x¯,x∗,1≤i≤n,1≤j≤p will be generated in cells i+n⋅j−1. On the other hand, 2n valid truth assignments will be generated in cells labelled by np+2. For that, 2np of such cells will be generated, each of them containing a truth assignment. Of course, there will be repeated truth assignments, but in this framework, due to the restrictions of the length of the rules, it seems necessary to create all the possible assignments (including the ones where two different truth values are assigned to a single variable), and then “remove” the incompatibilities.Proposition 1.
LetC=C0,C1,…,Cq be a computation of the system Πsφ with input multiset codφ.(i)
For eachk (0≤k≤np) at configuration Ck, we have the following:(1)
C0i+n⋅j−1=∅ and there are 2k−1 cells labelled by i+n⋅j−1 in the configuration Ck such that each of them contains an object li,j,k, being l=x if xi is a literal of the clause Cj, x¯ if ¬xi is a literal of the clause Cj , and x∗ if neither xi nor ¬xi are literals of the clause Cj, for k≥1(2)
C0np+1=δk∪codφ and Cknp+1=δk for k>0(3)
There are2k cells labelled by np+2 in the configuration Ck such that each of them contains the set α1,…,αp+1, np−k objects from the set a1,1,…,a1,p,…,an,1,…,an,p and less than k or k objects from the set R1,1,…,R1,p,…,Rn,1,…,Rn,p,R∈T,F(4)
C0np+3=δ0′ and there are 2k−1 cells labelled by np+3 in the configuration Ck such that each of them contains an object δk′, for k≥1(ii)
In the configurationCnp+1, we have that there are 2np cells labelled by i+n⋅j−1 for each 1≤i≤n,1≤j≤p such that each of them contains an object li,j,np+1 being l=x if xi is a literal of the clause Cj, x¯ if ¬xi is a literal of the clause Cj , and x∗ if neither xi nor ¬xi are literals of the clause Cj, Cnp+1np+1=δnp+1; there are 2np cells labelled by np+2 such that each of them contains the set α1,…,αp+1, less than np or np objects from the set R1,1,…,R1,p,…,Rn,1,…,Rn,p,R∈T,F and there are 2np cells labelled by np+3 such that each of them contains an object δnp+1′Proof.
(i) is going to be proved by induction onk(i)
The base casek=0 is trivial because at the initial configuration, we have the following:(1)
C0i+n⋅j−1=∅(2)
C0np+1=δ0∪codφ(3)
There is one cell labelled bynp+2 such that contains the set α1,…,αp+1 and the set a1,1,…,a1,p,…,an,1,…,an,p(4)
There is one cell labelled bynp+3 such that it contains an object δ0′Then, configurationC0 yields configuration C1 by applying the rules:(11)ai,jnp+2⟶Ti,jnp+2Fi,jnp+2xi,j,0np+1i+n⋅j−1⟶np+1xi,j,1i+n⋅j−1x¯i,j,0np+1i+n⋅j−1⟶np+1xi,j,1i+n⋅j−1xi,j,0∗np+1i+n⋅j−1⟶np+1xi,j,1∗i+n⋅j−1for1≤i≤n,1≤j≤p.δ0′np+3γ0⟶δ1′np+30δ0np+1γ0⟶δ1np+10Thus, we have the following:(1)
C1i+n⋅j−1=li,j,1, being l=x if xi is a literal of the clause Cj, x¯ if ¬xi is a literal of the clause Cj and x∗ if neither xi nor ¬xi are literals of the clause Cj(2)
C1np+1=δ1(3)
There are two cells labelled bynp+2 such that contains the set α1,…,αp+1, np−1 objects of the set a1,1,…,a1,p,…,an,1,…,an,p and one object Ti,j and one object Fi,j, respectively, for a i,1≤i≤n and a j,1≤j≤p(4)
There is one cell labelled bynp+3 such that it contains an object δ1′(ii)
Assuming that, by induction, the result is true fork (0≤k≤np); that is, that we have the following:(1)
C0i+n⋅j−1=∅ and there are 2k−1 cells labelled by i+n⋅j−1 in the configuration Ck such that each of them contains an object li,j,k, being l=x if xi is a literal of the clause Cj, x¯ if ¬xi is a literal of the clause Cj and x∗ if neither xi nor ¬xi are literals of the clause Cj, for k≥1(2)
C0np+1=δk∪codφ and Cknp+1=δk for k>0(3)
There are2k cells labelled by np+2 in the configuration Ck such that each of them contains the set α1,…,αp+1, np−k objects from the set a1,1,…,a1,p,…,an,1,…,an,p and less than k or k objects from the set R1,1,…,R1,p,…,Rn,1,…,Rn,p,R∈T,F(4)
C0np+3=δ0′ and there are 2k−1 cells labelled by np+3 in the configuration Ck such that each of them contains an object δk′ for k≥1Then, configurationCk yields configuration Ck+1 by applying the rules:(12)ai,jnp+2⟶Ti,jnp+2Fi,jnp+2Ti,jFi,j′np+20⟶np+2#0for1≤i≤n,1≤j,j′≤p,xi,j,ki+n⋅j−1⟶xi,j,k+1i+n⋅j−1xi,j,k+1i+n⋅j−1x¯i,j,ki+n⋅j−1⟶x¯i,j,k+1i+n⋅j−1x¯i,j,k+1i+n⋅j−1xi,j,k∗i+n⋅j−1⟶xi,j,k+1∗i+n⋅j−1xi,j,k+1∗i+n⋅j−1for1≤i≤n,1≤j≤p,δk′np+3⟶δk+1′np+3δk+1′np+3,δknp+1γ0⟶δk+18inp+10.Thus, we have the following:(1)
There are2k cells labelled by i+n⋅j−1 in the configuration Ck such that each of them contains an object li,j,k+1, being l=x if xi is a literal of the clause Cj, x¯ if ¬xi is a literal of the clause Cj and x∗ if neither xi nor ¬xi are literals of the clause Cj(2)
Ck+1np+1=δk+1(3)
There are2k+1 cells labelled by np+2 in the configuration Ck+1 such that each of them contains the set α1,…,αp+1, np−k+1 objects from the set a1,1,…,a1,p,…,an,1,…,an,p and less than k+1 or k+1 objects from the set R1,1,…,R1,p,…,Rn,1,…,Rn,p,R∈T,F(4)
There are2k cells labelled by np+3 in the configuration Ck+1 such that each of them contains an object δk+1′(iii)
In order to prove (ii) it is enough to take into account the fact that, from (i), we have the following:(1)
There are2np−1 cells labelled by i+n⋅j−1 in the configuration Cnp such that each of them contains an object li,j,np, being l=x if xi is a literal of the clause Cj, x¯ if ¬xi is a literal of the clause Cj and x∗ if neither xi nor ¬xi are literals of the clause Cj(2)
Cnpnp+1=δnp(3)
There are2np cells labelled by np+2 in the configuration Cnp such that each of them contains the set α1,…,αp+1 and less than np or np objects from the set R1,1,…,R1,p,…,Rn,1,…,Rn,p,R∈T,F, representing a truth assignment(4)
There are2np−1 cells labelled by np+3 in the configuration Cnp such that each of them contains an object δnp′Then, configurationCnp yields configuration Cnp+1 by applying the rules:(13)Ti,jFi,j′np+20⟶np+2#0for1≤i≤n,1≤j,j′≤p,xi,j,npi+n⋅j−1⟶xi,j,np+1i+n⋅j−1xi,j,np+1i+n⋅j−1x¯i,j,npi+n⋅j−1⟶x¯i,j,np+1i+n⋅j−1x¯i,j,np+1i+n⋅j−1xi,j,np∗i+n⋅j−1⟶xi,j,np+1∗i+n⋅j−1xi,j,np+1∗i+n⋅j−1for1≤i≤n,1≤j≤p,δnp′np+3⟶δnp+1′np+3δnp+1′np+3,δnpnp+1γ0⟶δnp+1np+10.Then, we have the following:(1)
There are2np cells labelled by i+n⋅j−1 in the configuration Cnp+1 such that each of them contains an object li,j,np+1, being l=x if xi is a literal of the clause Cj, x¯ if ¬xi is a literal of the clause Cj and x∗ if neither xi nor ¬xi are literals of the clause Cj(2)
Cnp+1np+1=δnp+1(3)
There are2np cells labelled by np+2 in the configuration Cnp+1 such that each of them contains the set α1,…,αp+1 and less than np or np objects from the set R1,1,…,R1,p,…,Rn,1,…,Rn,p,R∈T,F, representing a truth assignment(4)
There are2np cells labelled by np+3 in the configuration Cnp+1 such that each of them contains an object δnp+1′


## 4.1.2. First Checking Stage

From the previous stage, we have thatCnp+1np+1=δnp+1, there are 2np cells labelled by np+3 which contains an object δnp+1′, 2np cells labelled by np+2 that contains objects α1,…,αp,αp+1 and a set of objects R1,1,R1,2,…,R1,p,R2,1,…,R2,p,…,Rn,1…,Rn,pR∈T,F, representing the truth assignment associated with that cell. Not all objects of such a set have to be present in a single cell since they could have been consumed by the application of a rule Ti,jFi,j′np+20⟶np+2#0. Moreover, there exist 2np cells labelled by i+n⋅j−1,1≤i≤n,1≤j≤p each of them containing an object li,j,np+1. Then, by the application of the rules from 2.1, objects cj will be created in the cells labelled by np+2 such that the truth assignment associated with such cell satisfies clause Cj due to any literal of it. Besides, rules δnp+1np+1γ0⟶δnp+2np+10,δnp+1′np+3γ0⟶δnp+2′np+30 are applied.Therefore, we haveCnp+2np+1=δnp+2, there are 2np cells labelled by np+3 which contains an object δnp+2′, 2np cells labelled by np+2 that contains objects α1,…,αp,αp+1 and a multiset of objects from c1,…,cp, representing the clauses satisfied by the truth assignment associated with that cell. The remaining objects li,j,np+1 in cells labelled by i+n⋅j−1 are not going to be taken into account from now since they cannot “react” with something from this point of the computation.


## 4.1.3. Second Checking Stage

The stepnp+3 is devoted to checking whether all the clauses Cj,1≤j≤p of the Boolean formula φ have been satisfied by the truth assignment associated with each cell labelled by np+2. We have that Cnp+2np+1=δnp+2, and there will be 2np cells labelled by np+3 which contains an object δnp+2′ and 2np cells labelled by np+2 such that contains objects α1,…,αp,αp+1 and objects cj,1≤j≤p corresponding to the clauses satisfied by the truth assignment associated with that cell. Then, by applying the rules αp+1np+2δnp+2′np+3⟶αp+1′np+2np+3,cjαjnp+2np+3⟶np+2#np+3,δnp+2np+1γ0⟶δnp+3np+10, we obtain the following: Cnp+3np+1=δnp+3 and there will be 2np cells labelled by np+2 that will contain an object αj if and only if clause Cj has not been satisfied by the truth assignment associated with such cell.


## 4.1.4. Output Stage

The output phase starts at thenp+4-th step and takes exactly four steps, regardless of whether the input formula φ is satisfied or not by some truth assignment.(i)
Affirmative answer: if the input formulaφ of SAT problem is satisfiable then at least one of the truth assignments from a cell with label np+2 has satisfied all clauses. Therefore, there will be at least one cell labelled by np+2 such that it will not have any object αj, since all of them have been “consumed” in some sense by an object cj. Therefore, in the step np+4, object δnp+3 will evolve into δnp+4 by the application of the rule δnp+3np+1γ0⟶δnp+4np+10, besides the application of rules αjαp+1′np+20⟶np+2n10 in other cells. In the next step, since αp+1′ remains in a cell labelled by np+2, it can evolve with object δnp+4 by the rule αp+1′np+2δnp+4np+1⟶y1np+2np+1. Since there is only one object δnp+4, then we can be sure that the object y1 (that will produce the object yes later) is unique. Besides, objects n1 will be sent as n2 to cells labelled by np+2 in a nondeterministic way. In the np+5-th step, it will evolve into the object y2. Let us keep in mind that objects n2 cannot react with object δnp+4 since it has been consumed in the previous step. At the last step of the computation, the only rule applicable will be y2np+20⟶np+2yes0. Then, an object yes will be sent to the environment, and the computation halts.(ii)
Negative answer: if the input formulaφ of SAT problem is not satisfiactory, then none of the truth assignments encoded by a cell labelled as np+2 makes the formula φ true. Thus, in each cell, there will be at least one object of the type αj,1≤j≤p. It means that the clause Cj is not satisfied by the truth assignment corresponding to that cell. Therefore, at step np+3 rules αjαp+1′np+20⟶np+2n10 will be applied in all the cells. Therefore, at configuration Cnp+3 there will not be any object αp+1′ in the system, so object δnp+4 remains in the cell labelled by np+1. In the next step, objects n1 go to cells labelled by np+2, selected in a nondeterministic way. Since object δnp+4 is in the cell labelled as np+1 it can make object n2 evolve into object n3, and then in the last step, it is sent to the environment as an object no. Since there is no applicable rule, the system halts.Theorem 2.
SAT∈PMCTDℰC2,1Proof.
The family of P systems previously constructed verifies the following:(i)
Every system of the familyΠ is a recognizer P system from TDEC2,1.(ii)
The familyΠ is polynomially uniform by Turing machines because, for each n,p∈ℕ, the rules of Πn,p of the family are recursively defined from n,p∈ℕ, and the amount of resources needed to build an element of the family is of a polynomial order in n and p, as shown below:(1)Size of the alphabet:3n2p2+11np+p+17∈Θn2p2(2)
Initial number of cells:np+3∈Θnp(3)
Initial number of objects in cells:np+p+3∈Θnp(4)
Number of rules:3n2p2+np2+12np+2p+13∈Θn2p2(5)
Maximal number of objects involved in any rule:3∈Θ1(iii)
The paircod,s of polynomial-time computable functions defined fulfills the following: for each input formula φ of SAT problem, sφ is a natural number, codφ is an input multiset for the system Πsφ, and for each n∈ℕ, s−1n is a finite set.(iv)
The familyΠ is polynomially bounded: indeed, for each input formula φ of SAT problem, the deterministic P system Πsφ+codφ takes exactly np+7 steps, being n the number of variables in φ and p its number of clauses.(v)
The familyΠ is sound with regard to X,cod,s: for each formula φ, if the computation of Πsφ+codφ is an accepting computation, then φ is satisfiable.(vi)
The familyΠ is complete with regard to X,cod,s: for each input formula φ such that it is satisfiable, the computation of Πsφ+codφ is an accepting computation.Corollary 1.
NP∪co−NP⊆PMCTDℰC2,1Proof.
It is simple to prove this since it is known thatSAT is a NP-complete problem, SAT∈PMCTDℰC2,1 and the complexity class PMCTDℰC2,1 is closed under polynomial-time reduction and under complementary. □Corollary 2.
NP∪co−NP⊆PMCTDℰC3


## 5. The Presumed Efficiency ofTSℰC2,2

In this section, the presumed efficiency ofTSℰC2,2 is established by providing a polynomial time uniform solution to the SAT problem by means of a family of membrane systems Π=Πt|t∈ℕ from TSℰC2,2.For each pair of natural numbersn,p∈ℕ, we consider the recognizer tissue P system from TSℰC2,2, Πn,p=Γ,Γ0,Γ1,E,Σ,ℳ1,ℳ2,ℛ,iin,iout, defined as follows:(i) The working alphabet:(14)Γ=yes,no,y1,y2,n1,n2,#∪ai,j|1≤i≤n,0≤j≤i∪ai,j′|2≤i≤n,0≤j≤i−1∪ai,jL,ai,jR|2≤i≤n,0≤j≤i−1∪αj,αj′,αjL,αjR|1≤j≤p+1∪ti,fi,ti′,ti″,fi″,tiL,tiR,fiL,fiR|1≤i≤n∪βl,k,βl,k′,βl,kL,βl,kR0|≤k≤n,1≤l≤n∪xi,j,k,x¯i,j,k,xi,j,k∗|1≤i≤n,1≤j≤p,0≤k≤n+j−1∪xi,j,k′,x¯i,j,k′,xi,j,k∗′,xi,j,k″,x¯i,j,k″,xi,j,k∗″,xi,j,k″′,x¯i,j,k″′,xi,j,k∗″′|1≤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.(ii) The partitionΓ0,Γ1 defined as: Γ1=Γ∖Γ0 and(15)Γ0=ai,jL|2≤i≤n,1≤j≤i−1∪αjL|1≤j≤p+1∪tiL,fiL|1≤i≤n∪βl,kL|0≤k≤n,k+1≤k≤n.(iii)
The input alphabetΣ=xi,j,0,x¯i,j,0,xi,j,0∗|1≤i≤n,1≤j≤p.(iv)
The environment alphabetE=γ.(v)
ℳ1=δ0,δ0′∪βl,0n+p+1|1≤l≤n;ℳ2=ai,0|1≤i≤n∪αj|1≤j≤p+1.(vi)
The setℛ consists of the following rules:(1) Rules for steps4k+1.(16)ai,i−12γ0⟶ai,i−1′ti′20for1≤i≤n,ti2γ0⟶ti′′20fi2γ0⟶fi′′20for1≤i≤n,ai,j2γ0⟶ai,j′20for2≤i≤n,0≤j≤i−2,αj2γ0⟶αj′20for1≤j≤p+1,βl,k1γ0⟶βl,k′10for0≤k≤n,k+1≤j≤n,xi,j,k1γ0⟶xi,j,k′10x¯i,j,k1γ0⟶x¯i,j,k′10xi,j,k∗1γ0⟶xi,j,k∗′10for1≤i≤n,1≤j≤p,0≤k≤n−1.(2)
Rules for steps4k+2.(17)ai,i−1′2γ0⟶ai,i−1′fiR20ti′2γ0⟶tiL20ti″2γ0⟶tiLtiR20fi″2γ0⟶fiLfiR20for1≤i≤n,ai,j′2γ0⟶ai,j+1Lai,j+1R20for2≤i≤n,0≤j≤i−2,αj′2γ0⟶αjLαjR20for1≤j≤p+1,βl,k′1γ0⟶βl,kLβl,kR10for0≤k≤n,k+1≤j≤n,xi,j,k′1γ0⟶xi,j,k″210x¯i,j,k′1γ0⟶x¯i,j,k″210xi,j,k∗′1γ0⟶xi,j,k∗″210for1≤i≤n,1≤j≤p,0≤k≤n−1.(3)
Rules for steps4k+3.(18)ai,i2⟶Γ02Γ12for1≤i≤n,βk,kO10⟶1βk,kO0βl,kO10⟶1βl,kO0forO∈L,R,1≤k≤n,k+1≤l≤n,xi,j,k″1γ0⟶xi,j,k″′10x¯i,j,k″1γ0⟶x¯i,j,k″′10xi,j,k∗″1γ0⟶xi,j,k∗″′10for1≤i≤n,1≤j≤p,1≤k≤n.(4)
Rules for steps4k.(19)ai,jO2βk,kO0⟶ai,j20riO2βk,kO0⟶ri20forO∈L,R,r∈t,f,1≤i≤n,1≤j≤n,1≤k≤n,xi,j,k″′1γ0⟶xi,j,k10x¯i,j,k″′1γ0⟶x¯i,j,k10xi,j,k∗″′1γ0⟶xi,j,k∗10for1≤i≤n,1≤j≤p,0≤k≤n,βl,k01⟶0βl,k1for0≤k≤n,k+1≤l≤n.(5)
Rules to check the satisfied clauses.(20)ti2xi,j,n+j−11⟶cj,jti21ti2x¯i,j,n+j−11⟶ti21ti2xi,j,n+j−1∗1⟶ti21fi2xi,j,n+j−11⟶fi21fi2xi,j,n+j−11⟶cj,jfi21fi2xi,j,n+j−1∗1⟶fi21for1≤i≤n,1≤j≤p,xi,j,n+k1γ0⟶xi,j,n+k+110x¯i,j,n+k1γ0⟶x¯i,j,n+k+110xi,j,n+k∗1γ0⟶xi,j,n+k+1∗10for1≤i≤n,1≤j≤p,0≤k≤j−2.(6) Rules to check if all the clauses are satisfied by a truth assignment.(21)αp+12δ4n+p′1⟶αp+1′21,αjcj,p21⟶2#1for1≤j≤p.(7) General counters.(22)δi1γ0⟶δi+121for0≤i≤4n+p+1,δ4i+1′1γ0⟶δ4i+1′221for0≤i≤n−1,δ4i+k′1γ0⟶δ4i+k+1′21for0≤i≤n−1,k∈0,2,3,δ4n+i′1γ0⟶δ4n+i+1′21for0≤i≤p−1.(8) Rules to return a negative answer.(23)αjαp+1′20⟶1#0for1≤j≤p,n102⟶0n12,n12δ4n+p+21⟶n221,n220⟶2no2.(9) Rules to return a positive answer.(24)αp+1′2δ4n+p+21⟶y121,y12γ0⟶y220,y220⟶2yes2.(ii) The input cell is the cell labelled by 1 (that is,iin=1) and the output zone is the environment (that is, iout=env).


### 5.1. An Overview of the Computations

A brief overview of the computation is explained below. For a more exhaustive verification, we refer the reader to [21].


#### 5.1.1. Generation Stage

The objective of this stage is twofold: on the one hand, all truth assignments for the variables associated with the Boolean formulaφx1,…,xn are generated by applying rules from 2 in cells labelled by 2, in such a manner that in the 4i+2-th step (1≤i≤n−1) of this stage, separation rule associated with an object ai,i is triggered, two new cells distributing ti and fi between them. In the last step of this stage, each cell labelled by 2 will contain a truth assignment of the formula. On the other hand, 2n copies of each object a∈codφ are going to be generated in the cell labelled by 1. These objects are being prepared for the next stage. It is interesting to keep in mind that separation rules are executed each 4 time steps, so objects keep evolving within their corresponding cells in order to maintain the synchronization. It is done by means of a simulation of evolution rules, by using object γ as a “catalyzer” of the reaction:(25)a1γ0⟶a′10.


#### 5.1.2. First Checking Stage

In this stage, objectscj,k are generated in the cells labelled by 2 such that the truth assignment associated with them makes the clause Cj true. In each step, the system processes a single clause so that p steps are needed to process the whole formula. Objects cj,k are generated in any of the following cases:(i)
Literalxi appears in clause Cj, and the value of variable xi in a truth assignment is True. Then, we can say that such truth assignment satisfies this clause.(ii)Literal¬xi appears in clause Cj, and the value of variable xi in a truth assignment is False. Then, we can say that such truth assignment satisfies this clause.In any other case, variablexi has nothing to do with clause Cj. At the final step of this stage, cells labelled by 2 will have objects cj,p where Cj are clauses satisfied by such truth assignment. We obtain an object αp+1′ to use it in the next stage.


#### 5.1.3. Second Checking Stage

Here, rules from 6 are fired at the4n+p+1-th step, and objects αj within a cell labelled by 2 are removed if and only if the truth assignment associated with that cell makes a true clause Cj, that is, if there is at least one object cj in such cell. In this step, objects αj from cells labelled by 2 such that their corresponding element cj,p appears in it disappear. At the same time, an object αp+1′ appears in each cell labelled by 2 for the next stage, where they will interact with the remaining, if any, objects aj.


#### 5.1.4. Output Stage

This stage takes four steps, regardless of the formula being satisfactory or not. If there is at least one truth assignment that makes the input formula true, then at least one cell labelled by 2 will preserve an objectαp+1′, and it will interact with the object δ4n+p+2 to finally return an object yes to the environment. On the contrary, if none of the truth assignments makes the formula φ true, then object δ4n+p+2 will remain and it will interact with the object n1, leading to the sending of an object no into the environment.Theorem 3.
SAT∈PMCTSℰC2,2Proof.
The family of P systems previously constructed verifies the following:(i)
Every system of the familyΠ is a recognizer P system from TSEC2,2.(ii)
The familyΠ is polynomially uniform by Turing machines because, for each n,p∈ℕ, the rules of Πn,p of the family are recursively defined from n,p∈ℕ, and the amount of resources needed to build an element of the family is of a polynomial order in n and p, as follows:(1)
Size of the alphabet:9n2p+6n2+3np2/2−3np+22n+p2/2+13p/2+14∈Θmaxn2p,np2(2)
Initial number of cells:2∈Θ1(3)
Initial number of objects in cells:n2+np+1+p+3∈Θn2(4)
Number of rules:8n3+27n2p/2+4n1+19np/2+23n+p2/2+17p/2+11∈Θn3(5)
Maximal number of objects involved in any rule:4∈Θ1(iii)
The paircod,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∈ℕ, s−1n is a finite set.(iv)
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 n the number of variables of φ and p the number of clauses.(v)
The familyΠ is sound with regard to X,cod,s: for each formula φ, if the computation of Πsφ+codφ is an accepting computation, then φ is satisfiable.(vi)
The familyΠ is complete with regard to X,cod,s: for each input formula φ such that it is satisfiable, the computation of Πsφ+codφ is an accepting computation.Corollary 3.
NP∪co−NP⊆PMCTSℰC2,2Proof.
It is simple to prove this since it is known thatSAT is a NP-complete problem, SAT∈PMCTSℰC2,2 and the complexity class PMCTSℰC2,2 is closed under polynomial-time reduction and under complementary. □
Bearing in mind thatTSℰC2,2⊆TSℰC3,2, the result of the previous corollary improves the one obtained in [19] concerning to the presumed efficiency of the computing model TSℰC3,2.


## 5.1. An Overview of the Computations

A brief overview of the computation is explained below. For a more exhaustive verification, we refer the reader to [21].


### 5.1.1. Generation Stage

The objective of this stage is twofold: on the one hand, all truth assignments for the variables associated with the Boolean formulaφx1,…,xn are generated by applying rules from 2 in cells labelled by 2, in such a manner that in the 4i+2-th step (1≤i≤n−1) of this stage, separation rule associated with an object ai,i is triggered, two new cells distributing ti and fi between them. In the last step of this stage, each cell labelled by 2 will contain a truth assignment of the formula. On the other hand, 2n copies of each object a∈codφ are going to be generated in the cell labelled by 1. These objects are being prepared for the next stage. It is interesting to keep in mind that separation rules are executed each 4 time steps, so objects keep evolving within their corresponding cells in order to maintain the synchronization. It is done by means of a simulation of evolution rules, by using object γ as a “catalyzer” of the reaction:(25)a1γ0⟶a′10.


### 5.1.2. First Checking Stage

In this stage, objectscj,k are generated in the cells labelled by 2 such that the truth assignment associated with them makes the clause Cj true. In each step, the system processes a single clause so that p steps are needed to process the whole formula. Objects cj,k are generated in any of the following cases:(i)
Literalxi appears in clause Cj, and the value of variable xi in a truth assignment is True. Then, we can say that such truth assignment satisfies this clause.(ii)Literal¬xi appears in clause Cj, and the value of variable xi in a truth assignment is False. Then, we can say that such truth assignment satisfies this clause.In any other case, variablexi has nothing to do with clause Cj. At the final step of this stage, cells labelled by 2 will have objects cj,p where Cj are clauses satisfied by such truth assignment. We obtain an object αp+1′ to use it in the next stage.


### 5.1.3. Second Checking Stage

Here, rules from 6 are fired at the4n+p+1-th step, and objects αj within a cell labelled by 2 are removed if and only if the truth assignment associated with that cell makes a true clause Cj, that is, if there is at least one object cj in such cell. In this step, objects αj from cells labelled by 2 such that their corresponding element cj,p appears in it disappear. At the same time, an object αp+1′ appears in each cell labelled by 2 for the next stage, where they will interact with the remaining, if any, objects aj.


### 5.1.4. Output Stage

This stage takes four steps, regardless of the formula being satisfactory or not. If there is at least one truth assignment that makes the input formula true, then at least one cell labelled by 2 will preserve an objectαp+1′, and it will interact with the object δ4n+p+2 to finally return an object yes to the environment. On the contrary, if none of the truth assignments makes the formula φ true, then object δ4n+p+2 will remain and it will interact with the object n1, leading to the sending of an object no into the environment.Theorem 3.
SAT∈PMCTSℰC2,2Proof.
The family of P systems previously constructed verifies the following:(i)
Every system of the familyΠ is a recognizer P system from TSEC2,2.(ii)
The familyΠ is polynomially uniform by Turing machines because, for each n,p∈ℕ, the rules of Πn,p of the family are recursively defined from n,p∈ℕ, and the amount of resources needed to build an element of the family is of a polynomial order in n and p, as follows:(1)
Size of the alphabet:9n2p+6n2+3np2/2−3np+22n+p2/2+13p/2+14∈Θmaxn2p,np2(2)
Initial number of cells:2∈Θ1(3)
Initial number of objects in cells:n2+np+1+p+3∈Θn2(4)
Number of rules:8n3+27n2p/2+4n1+19np/2+23n+p2/2+17p/2+11∈Θn3(5)
Maximal number of objects involved in any rule:4∈Θ1(iii)
The paircod,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∈ℕ, s−1n is a finite set.(iv)
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 n the number of variables of φ and p the number of clauses.(v)
The familyΠ is sound with regard to X,cod,s: for each formula φ, if the computation of Πsφ+codφ is an accepting computation, then φ is satisfiable.(vi)
The familyΠ is complete with regard to X,cod,s: for each input formula φ such that it is satisfiable, the computation of Πsφ+codφ is an accepting computation.Corollary 3.
NP∪co−NP⊆PMCTSℰC2,2Proof.
It is simple to prove this since it is known thatSAT is a NP-complete problem, SAT∈PMCTSℰC2,2 and the complexity class PMCTSℰC2,2 is closed under polynomial-time reduction and under complementary. □
Bearing in mind thatTSℰC2,2⊆TSℰC3,2, the result of the previous corollary improves the one obtained in [19] concerning to the presumed efficiency of the computing model TSℰC3,2.


## 5.1.1. Generation Stage

The objective of this stage is twofold: on the one hand, all truth assignments for the variables associated with the Boolean formulaφx1,…,xn are generated by applying rules from 2 in cells labelled by 2, in such a manner that in the 4i+2-th step (1≤i≤n−1) of this stage, separation rule associated with an object ai,i is triggered, two new cells distributing ti and fi between them. In the last step of this stage, each cell labelled by 2 will contain a truth assignment of the formula. On the other hand, 2n copies of each object a∈codφ are going to be generated in the cell labelled by 1. These objects are being prepared for the next stage. It is interesting to keep in mind that separation rules are executed each 4 time steps, so objects keep evolving within their corresponding cells in order to maintain the synchronization. It is done by means of a simulation of evolution rules, by using object γ as a “catalyzer” of the reaction:(25)a1γ0⟶a′10.


## 5.1.2. First Checking Stage

In this stage, objectscj,k are generated in the cells labelled by 2 such that the truth assignment associated with them makes the clause Cj true. In each step, the system processes a single clause so that p steps are needed to process the whole formula. Objects cj,k are generated in any of the following cases:(i)
Literalxi appears in clause Cj, and the value of variable xi in a truth assignment is True. Then, we can say that such truth assignment satisfies this clause.(ii)Literal¬xi appears in clause Cj, and the value of variable xi in a truth assignment is False. Then, we can say that such truth assignment satisfies this clause.In any other case, variablexi has nothing to do with clause Cj. At the final step of this stage, cells labelled by 2 will have objects cj,p where Cj are clauses satisfied by such truth assignment. We obtain an object αp+1′ to use it in the next stage.


## 5.1.3. Second Checking Stage

Here, rules from 6 are fired at the4n+p+1-th step, and objects αj within a cell labelled by 2 are removed if and only if the truth assignment associated with that cell makes a true clause Cj, that is, if there is at least one object cj in such cell. In this step, objects αj from cells labelled by 2 such that their corresponding element cj,p appears in it disappear. At the same time, an object αp+1′ appears in each cell labelled by 2 for the next stage, where they will interact with the remaining, if any, objects aj.


## 5.1.4. Output Stage

This stage takes four steps, regardless of the formula being satisfactory or not. If there is at least one truth assignment that makes the input formula true, then at least one cell labelled by 2 will preserve an objectαp+1′, and it will interact with the object δ4n+p+2 to finally return an object yes to the environment. On the contrary, if none of the truth assignments makes the formula φ true, then object δ4n+p+2 will remain and it will interact with the object n1, leading to the sending of an object no into the environment.Theorem 3.
SAT∈PMCTSℰC2,2Proof.
The family of P systems previously constructed verifies the following:(i)
Every system of the familyΠ is a recognizer P system from TSEC2,2.(ii)
The familyΠ is polynomially uniform by Turing machines because, for each n,p∈ℕ, the rules of Πn,p of the family are recursively defined from n,p∈ℕ, and the amount of resources needed to build an element of the family is of a polynomial order in n and p, as follows:(1)
Size of the alphabet:9n2p+6n2+3np2/2−3np+22n+p2/2+13p/2+14∈Θmaxn2p,np2(2)
Initial number of cells:2∈Θ1(3)
Initial number of objects in cells:n2+np+1+p+3∈Θn2(4)
Number of rules:8n3+27n2p/2+4n1+19np/2+23n+p2/2+17p/2+11∈Θn3(5)
Maximal number of objects involved in any rule:4∈Θ1(iii)
The paircod,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∈ℕ, s−1n is a finite set.(iv)
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 n the number of variables of φ and p the number of clauses.(v)
The familyΠ is sound with regard to X,cod,s: for each formula φ, if the computation of Πsφ+codφ is an accepting computation, then φ is satisfiable.(vi)
The familyΠ is complete with regard to X,cod,s: for each input formula φ such that it is satisfiable, the computation of Πsφ+codφ is an accepting computation.Corollary 3.
NP∪co−NP⊆PMCTSℰC2,2Proof.
It is simple to prove this since it is known thatSAT is a NP-complete problem, SAT∈PMCTSℰC2,2 and the complexity class PMCTSℰC2,2 is closed under polynomial-time reduction and under complementary. □
Bearing in mind thatTSℰC2,2⊆TSℰC3,2, the result of the previous corollary improves the one obtained in [19] concerning to the presumed efficiency of the computing model TSℰC3,2.


## 6. Conclusions and Future Work

In this paper, following the works initiated in [18, 19], tissue P systems with evolutional symport/antiport rules have been studied from a computational complexity view, where either division rules or separation rules are used as mechanisms to create an exponential workspace in polynomial time. In this context, new results have been achieved:(i)
With regard to tissue P systems with division rules:(1)
The nonefficiency of membrane systems fromTDℰC1,n, for each natural number n≥1, has been established, complementing the result previously obtained in [18] concerning the nonefficiency of membrane systems from TDℰC2.(2)
The presumed efficiency ofTDℰC2,1 has been established, improving the result previously obtained in [18] concerning the presumed efficiency of TDℰC4, since TDℰC2,1⊆TDℰC3⊆TDℰC4.(ii)
With regard to tissue P systems with separation rules:(1)
The presumed efficiency ofTSℰC2,2 has been established, improving the result previously obtained in [19] concerning the presumed efficiency of TSℰC3,2.All complexity results obtained until now in the framework of tissue P systems with evolutional symport/antiport rules are described in Figure1:Figure 1
Known complexity results on tissue P systems with evolutional symport/antiport rules.
(a)(b)The following diagram describes the known frontiers between the nonefficiency and the presumed efficiency in the framework of tissue P systems with evolutional symport/antiport rules [22–25]:(26)TDℰC2⇝TDℰC3,TSℰC2⇝TSℰC4,TDℰC1,n⇝TDℰC2,n,TSℰC1,2⇝TSℰC2,2,TSℰC2,1⇝TSℰC2,2,TSℰC2,1⇝TDℰC2,1.We propose the following open problems for future researches:(i)
What is the upper bound of complexity classesPMCℛ, where ℛ is a presumably efficient class of tissue P systems with division or separation rules and evolutional communication rules?(ii)
Is the class of membrane systems fromTSℰC3 nonefficient or presumably efficient?(iii)What is the role of the environment in the framework of tissue P systems with division or separation rules and evolutional communication rules?(iv)What is the behaviour of recognizer cell-like P systems with division or separation rules and evolutional communication rules from a computational complexity perspective?



---

*Source: 7120840-2021-04-28.xml*