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

Research Article TuningFrontiersofEfficiencyinTissuePSystemswithEvolutional Communication Rules David Orellana-Mart´ ın , 1 Luis Valencia-Cabrera , 1 Bosheng Song , 2 Linqiang Pan , 3 and Mario J. P´ erez-Jim´ enez 1 1 Research Group on Natural Computing, Department of Computer Science and Artificial Intelligence, Universidad de Sevilla, Avda. Reina Mercedes s/n, 41012, Sevilla, Spain 2 College of Information Science and Engineering, Hunan University, Changsha 410082, China 3 Key Laboratory of Image Information Processing and Intelligent Control of Education Ministry of China, Institute of Artificial Intelligence, School of Artificial Intelligence and Automation, Huazhong University of Science and Technology, Wuhan 430074, Hubei, China Correspondence should be addressed to Linqiang Pan; [email protected] Received 2 November 2019; Accepted 31 March 2021; Published 28 April 2021 Academic Editor: Hocine Cherifi Copyright ©2021 David Orellana-Mart´ ın et al. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. Over the last few years, a new methodology to address the Pversus NP problem has been developed, based on searching for borderlines between the nonefficiency of computing models (only problems in class Pcan 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 Pversus 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. 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 Hindawi Complexity Volume 2021, Article ID 7120840, 14 pages https://doi.org/10.1155/2021/7120840 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]. Pis 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 models M1and M1in a computing paradigm (for instance, in membrane computing) such that M2is obtained from M1by adding some syntactic or semantic ingredients. If M1is a nonefficient model and M2is a presumably efficient one, then the ingredients needed to obtain M2from M1provide a frontier between the tractability of abstract problems and the presumed intractability. In some sense, passing from M1to M2amounts to passing from the nonefficiency to the presumed efficiency. Each such borderline provides a tool to tackle the Pversus 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 Pversus 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, TDEC(n)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 TDEC(2)has been established by using the dependency graph technique, and a polynomialtime uniform solution to the SAT problem by a family of membrane systems from TDEC(4)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 PMCTDEC(3)? 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, TDEC(k1, 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 k1and the total number of objects involved in the right-hand side (RHS) is at most k2. The nonefficiency of TDEC(1, n)and TDEC(n, 1), for each n≥1, has been established using the algorithmic technique. On the other hand, the presumed efficiency of TDEC(3,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 TDEC(k1, k2)is defined similarly to TDEC(k1, k2), replacing separation rules by division rules. Following [18], for each natural number n≥1, TDEC(n)is defined similarly to TDEC(n), replacing division by separation rules. For each pair of natural numbers k1≥1, k2≥1, we have TDEC(k1, k2)⊆TDEC(k1+k2)and TDEC(k1, k2)⊆T DEC(k1+k2). This paper focuses on the nonefficiency of TDEC(1, n), for each n≥1, and the presumed efficiency of TDEC(2,1) and TDEC(2,2). Specifically, we prove the following results: (1) For each natural number n≥1, we have P�PMCTDEC(1,n); (2) the computing model TDEC(2,1) is presumably efficient, that is, NP ∪co-NP ⊆PMCTDEC(2,1); (3) the computing model TDEC(2,2)is presumably efficient, that is, NP ∪co-NP ⊆PMCTDEC(2,2). Bearing in mind that TDEC(2,1)⊆TDE C(3)⊆TDEC(4)and TDEC(2,2)⊆TDEC(3,2), the presumed efficiency of TDEC(3),TDEC(4), and TDEC(3,2)follows, closing the question raised about TDEC(3), 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 in Section 2. The nonefficiency of 2Complexity TDEC(1, 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 TDEC(2,1)and TSEC(2,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 degree q≥1 (where qis the number of cells present in the system) is a tuple Π�Γ,Γ0,Γ1,E,Σ,M1,. . . ,Mq,R, iin, iout 􏼐 􏼑,(1) where (i) Γ,E,Σare finite alphabets such that E⊆Γ,Σ⊆Γ∖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) M1,. . . ,Mqare multisets over Γ∖Σ (iv) Ris a finite set of rules of the following forms: (1) Evolutional communication rules: (a) [u]ij ⟶i[u′]j, where i,j∈0,...,q 􏼈 􏼉,i≠j,u∈ M+(Γ),u′∈M(Γ), and if i�0, then alph (u)∩(Γ∖E)≠∅(evolutionalsymportrules) (b) [u]i[v]j⟶[v′]i[u′]j, where i,j∈0,...,q 􏼈 􏼉, i≠j,u,v∈M+(Γ),u′,v′∈M(Γ) (evolutionalantiportrules) (2) Division rules: [a]i⟶[b]i[c]i, where i∈1,..., q 􏼈 􏼉, i ≠iout, a, b, c ∈ Γ (3) Separation rules: [a]i⟶[Γ0]i[Γ1]i, where i∈1,. . . , q 􏼈 􏼉, i ≠iout, a ∈ Γ (v) iin ∈1,..., q 􏼈 􏼉}and iout �0 (that is, the label of the environment) (vi) If Cis a computation of Πthen Cis 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 ris defined as the total number of objects involved in the rule. For each natural number n≥1, TDEC(n)(resp., TSEC(n)) 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, TDEC(k1, k2)(resp., TSEC(k1, 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 k1and 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 TDEC(k1, k2)⊆TDEC(k1+k2)and TSEC(k1, k2) ⊆TSEC(k1+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 of TDEC(1, n) The nonefficiency of TSEC(1, 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∈N { } is a family of systems from TSEC(1, n)solving a decision problem Xin polynomial time and uniform way, then a directed graph GΠ(s(u))+cod(u) (with a source node) is associated with each instance u∈IX, in such a manner that every computation Cof Π(s(u)) + cod(u)is an accepting computation if and only if there exists a path in GΠ(s(u))+cod(u)from the source node to (yes,env). When working with membrane systems TSEC(1, n), each separation rule of the form [a]i⟶[Γ0]i[Γ1]iprovides 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 TDEC(1, n), we can adapt the proof given in [19], taking into account the fact that a division rule [a]i⟶[a]i[b]iprovides 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 TDEC(1, n)follows. Theorem 1. For each natural number n≥1, we have P�PMCTDEC(1,n). 4. A Solution to SAT in TDEC(2,1) We provide here a solution to SAT by means of a family of recognizer tissue P systems Π�Π(t)|t∈N { } from TDEC(2,1). Given a Boolean formula φin CNF and simplified with nvariables and pclauses, the system Π(s(φ)) + cod(φ)processes it, being s(φ) � 〈n, p〉 Complexity 3 and cod(φ) � xi,j,0|xi∈Cj 􏽮 􏽯∪xi,j,0|xi∈Cj 􏽮 􏽯∪x∗ i,j,0|xi∉Cj, 􏽮 xi∉Cj}and returns the answer to its satisfiability. For each n, p ∈N, we consider the recognizer P system Π(〈n, p〉) � Γ,E,Σ,M1,. . . ,Mnp+3,R, iin, iout 􏼐 􏼑,(2) where we have the following: (i) Working alphabet Γ: yes,no, y1, y2, n1, n2, n3,# 􏼈 􏼉∪ai,j, Ti,j, Fi,j|1≤i≤n, 1≤j≤p 􏽮 􏽯∪xi,j,k, xi,j,k, x∗ i,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 􏼈 􏼉 (3) (ii) Input alphabet Σ�xi,j,0, xi,j,0, x∗ i,j,0|1≤i≤n, 􏽮 1≤j≤p}. (iii) Environment alphabet E�c 􏼈 􏼉. (iv) Mk�∅,1≤k≤np;Mnp+1�δ0 􏼈 􏼉; Mnp+2�ai,j|1≤i≤n, 1≤j≤p 􏽮 􏽯∪αj|1≤j≤p+1 􏽮 􏽯; Mnp+3�δ0 ′ 􏼈 􏼉 (v) The rule set Rconsists of the following rules: (1) Rules to generate pcopies of the 2ntrue possible truth assignments. For this, 2np partial truth assignments will be generated. ai,j 􏽨 􏽩np+2⟶Ti,j 􏽨 􏽩np+2Fi,j 􏽨 􏽩np+2 Ti,jFi,j′ 􏽨 􏽩np+2[ ]0⟶[ ]np+2[#]0 ⎫⎪ ⎪ ⎬ ⎪ ⎪ ⎭for 1 ≤i≤n, 1≤j, j′≤p. (4) (2) Rules to generate 2np copies of cod(φ). xi,j,0 􏽨 􏽩np+1[ ]i+n·(j−1)⟶[ ]np+1xi,j,1 􏽨 􏽩i+n·(j−1) xi,j,0 􏽨 􏽩np+1[ ]i+n·(j−1)⟶[ ]np+1xi,j,1 􏽨 􏽩i+n·(j−1) x∗ i,j,0 􏽨 􏽩np+1[ ]i+n·(j−1)⟶[ ]np+1x∗ i,j,1 􏽨 􏽩i+n·(j−1) ⎫ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎬ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎭ for 1≤i≤n, 1≤j≤p, xi,j,k 􏽨 􏽩i+n·(j−1)⟶xi,j,k+1 􏽨 􏽩i+n·(j−1)xi,j,k+1 􏽨 􏽩i+n·(j−1) xi,j,k 􏽨 􏽩i+n·(j−1)⟶xi,j,k+1 􏽨 􏽩i+n·(j−1)xi,j,k+1 􏽨 􏽩i+n·(j−1) x∗ i,j,k 􏽨 􏽩i+n·(j−1)⟶x∗ i,j,k+1 􏽨 􏽩i+n·(j−1)x∗ i,j,k+1 􏽨 􏽩i+n·(j−1) ⎫ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎬ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎭ for 1≤i≤n, 1≤j≤p, 1≤k≤np, δ0 ′ 􏼂 􏼃np+3[c]0⟶δ1 ′ 􏼂 􏼃np+3[ ]0, δk ′ 􏼂 􏼃np+3⟶δk+1 ′ 􏼂 􏼃np+3δk+1 ′ 􏼂 􏼃np+3for 1 ≤k≤np , δnp+1 ′ 􏽨 􏽩np+3[c]0⟶δnp+2 ′ 􏽨 􏽩np+3[ ]0. (5) (3) Rules to check which clauses are satisfied by the truth assignments. 4Complexity Ti,j 􏽨 􏽩np+2xi,j,np+1 􏽨 􏽩i+n·(j−1)⟶cj 􏽨 􏽩np+2[ ]i+n·(j−1) Ti,j 􏽨 􏽩np+2xi,j,np+1 􏽨 􏽩i+n·(j−1)⟶[#]np+2[ ]i+n·(j−1) Ti,j 􏽨 􏽩np+2x∗ i,j,np+1 􏽨 􏽩i+n·(j−1)⟶[#]]np+2[ ]i+n·(j−1) Fi,j 􏽨 􏽩np+2xi,j,np+1 􏽨 􏽩i+n·(j−1)⟶[#]np+2[ ]i+n·(j−1) Fi,j 􏽨 􏽩np+2xi,j,np+1 􏽨 􏽩i+n·(j−1)⟶cj 􏽨 􏽩np+2[ ]i+n·(j−1) Fi,j 􏽨 􏽩np+2x∗ i,j,np+1 􏽨 􏽩i+n·(j−1)⟶[#]np+2[ ]i+n·(j−1) ⎫ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎬ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎭ for 1≤i≤n, 1≤j≤p. (6) (4) Rules to check if all the clauses are satisfied by a truth assignment. αp+1 􏽨 􏽩np+2δnp+2 ′ 􏽨 􏽩np+3⟶αp+1 ′ 􏽨 􏽩np+2[ ]np+3, cjαj 􏽨 􏽩np+2[ ]np+3⟶[ ]np+2[#]np+3for 1 ≤j≤p . (7) (5) General counter. δk 􏼂 􏼃np+1[c]0⟶δk+1 􏼂 􏼃np+1[ ]0 0≤k≤np +3.(8) (6) Rules to return a negative answer. αjαp+1 ′ 􏽨 􏽩np+2[ ]0⟶[ ]np+2n1 􏼂 􏼃0for 1 ≤j≤p, n1 􏼂 􏼃0[ ]np+2⟶[ ]0n2 􏼂 􏼃np+2, n2 􏼂 􏼃np+2δnp+4 􏽨 􏽩np+1⟶n3 􏼂 􏼃np+2[ ]np+1, n3 􏼂 􏼃np+2[ ]0⟶[ ]np+2[no]0. (9) (7) Rules to return a positive answer. αp+1 ′ 􏽨 􏽩np+2δnp+4 􏽨 􏽩np+1⟶y1 􏼂 􏼃np+2[ ]np+1, y1 􏼂 􏼃np+2[c]0⟶y2 􏼂 􏼃np+2[ ]0, y2 􏼂 􏼃np+2[ ]0⟶[ ]np+2[yes]0. (10) (vi) The input cell is the cell labelled by np +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), pcopies of the 2npossible 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, xi,j,np+1, x∗ i,j,np+1that 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), the pcopies of each one of the 2npossible truth assignments associated with variables x1,. . . , xn 􏼈 􏼉cooperate with objects xi,j,np+1, xi,j,np+1,x∗ i,j,np+1by 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 −2npartial truth assignments cannot satisfy φif it is unsatisfiable. This stage takes 1 computation step. (3) Second checking stage: by using rules from (4), object αjis removed from a cell labelled as np +2 if and only if the truth assignment associated with this cell makes the clause Cjtrue. 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 αjat the end of this stage, taking exactly 1 computation step. (4) Output stage: finally, rules from (5)–(7) will send either an object yes 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≤pwill be generated in cells i+n· (j−1). On the other hand, 2nvalid 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 Complexity 5 two different truth values are assigned to a single variable), and then “remove” the incompatibilities. Proposition 1. Let C� (C0,C1,. . . ,Cq)be a computation of the system Π(s(φ)) with input multiset cod(φ). (i) For each k(0≤k≤np) at configuration Ck, we have the following: (1) C0(i+n· (j−1)) � ∅and there are 2k−1cells labelled by i+n· (j−1)in the configuration Ck such that each of them contains an object li,j,k, being l�xif xiis a literal of the clause Cj,xif xiis a literal of the clause Cj, and x∗if neither xinor xi are literals of the clause Cj, for k≥1 (2) C0(np +1) � δk 􏼈 􏼉∪cod(φ)and Ck(np +1) � δk 􏼈 􏼉for k>0 (3) There are 2kcells labelled by np +2in the configuration Cksuch that each of them contains the set α1,. . . ,αp+1 􏽮 􏽯,np −kobjects from the set a1,1,. . . , a1,p,. . . , an,1,. . . , an,p 􏽮 􏽯and less than k or kobjects from the set R1,1,. . . , R1,p, 􏽮 . . . , Rn,1,. . . , Rn,p}, R ∈T, F { } (4) C0(np +3) � δ0 ′ 􏼈 􏼉 and there are 2k−1cells labelled by np +3in the configuration Cksuch that each of them contains an object δk ′, for k≥1 (ii) In the configuration Cnp+1, we have that there are 2np cells labelled by i+n· (j−1)for each 1≤i≤n, 1≤j≤psuch that each of them contains an object li,j,np+1being l�xif xiis a literal of the clause Cj,xif xiis a literal of the clause Cj, and x∗if neither xinor xiare literals of the clause Cj, Cnp+1(np +1) � δnp+1 􏽮 􏽯; there are 2np cells labelled by np +2such 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 +3such that each of them contains an object δnp+1 ′ Proof. (i) is going to be proved by induction on k (i) The base case k�0 is trivial because at the initial configuration, we have the following: (1) C0(i+n· (j−1)) � ∅ (2) C0(np +1) � δ0 􏼈 􏼉∪cod(φ) (3) There is one cell labelled by np +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 by np +3 such that it contains an object δ0 ′ Then, configuration C0yields configuration C1by applying the rules: ai,j 􏽨 􏽩np+2⟶Ti,j 􏽨 􏽩np+2Fi,j 􏽨 􏽩np+2 xi,j,0 􏽨 􏽩np+1[ ]i+n·(j−1)⟶[ ]np+1xi,j,1 􏽨 􏽩i+n·(j−1) xi,j,0 􏽨 􏽩np+1[ ]i+n·(j−1)⟶[ ]np+1xi,j,1 􏽨 􏽩i+n·(j−1) x∗ i,j,0 􏽨 􏽩np+1[ ]i+n·(j−1)⟶[ ]np+1x∗ i,j,1 􏽨 􏽩i+n·(j−1) ⎫ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎬ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎭ for 1≤i≤n, 1≤j≤p. δ0 ′ 􏼂 􏼃np+3[c]0⟶δ1 ′ 􏼂 􏼃np+3[ ]0 δ0 􏼂 􏼃np+1[c]0⟶δ1 􏼂 􏼃np+1[ ]0 (11) Thus, we have the following: (1) C1(i+n· (j−1)) � li,j,1 􏽮 􏽯, being l�xif xiis a literal of the clause Cj,xif xiis a literal of the clause Cjand x∗if neither xinor xiare literals of the clause Cj (2) C1(np +1) � δ1 􏼈 􏼉 (3) There are two cells labelled by np +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≤nand a j, 1≤j≤p (4) There is one cell labelled by np +3 such that it contains an object δ1 ′ (ii) Assuming that, by induction, the result is true for k (0 ≤k≤np); that is, that we have the following: (1) C0(i+n· (j−1)) � ∅and there are 2k−1cells labelled by i+n· (j−1)in the configuration Ck such that each of them contains an object li,j,k, being l�xif xiis a literal of the clause Cj,xif xi is a literal of the clause Cjand x∗if neither xi nor xiare literals of the clause Cj, for k≥1 (2) C0(np +1) � δk 􏼈 􏼉∪cod(φ)and Ck(np +1) � δk 􏼈 􏼉for k>0 (3) There are 2kcells labelled by np +2 in the configuration Cksuch that each of them contains the set α1,. . . ,αp+1 􏽮 􏽯,np −kobjects from the set a1,1,. . . , a1,p,. . . , an,1,. . . , an,p 􏽮 􏽯and less than kor kobjects from the set R1,1,. . . , R1,p,. . . , Rn,1,. . . , Rn,p 􏽮 􏽯, R ∈T, F { } (4) C0(np +3) � δ0 ′ 􏼈 􏼉 and there are 2k−1cells labelled by np +3 in the configuration Cksuch that each of them contains an object δk ′for k≥1 Then, configuration Ckyields configuration Ck+1by applying the rules: 6Complexity ai,j 􏽨 􏽩np+2⟶Ti,j 􏽨 􏽩np+2Fi,j 􏽨 􏽩np+2 Ti,jFi,j′ 􏽨 􏽩np+2[ ]0⟶[ ]np+2[#]0 ⎫ ⎪ ⎪ ⎬ ⎪ ⎪ ⎭for 1≤i≤n, 1≤j, j′≤p, xi,j,k 􏽨 􏽩i+n·(j−1)⟶xi,j,k+1 􏽨 􏽩i+n·(j−1)xi,j,k+1 􏽨 􏽩i+n·(j−1) xi,j,k 􏽨 􏽩i+n·(j−1)⟶xi,j,k+1 􏽨 􏽩i+n·(j−1)xi,j,k+1 􏽨 􏽩i+n·(j−1) x∗ i,j,k 􏽨 􏽩i+n·(j−1)⟶x∗ i,j,k+1 􏽨 􏽩i+n·(j−1)x∗ i,j,k+1 􏽨 􏽩i+n·(j−1) ⎫ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎬ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎭ for 1≤i≤n, 1≤j≤p, δk ′ 􏼂 􏼃np+3⟶δk+1 ′ 􏼂 􏼃np+3δk+1 ′ 􏼂 􏼃np+3, δk 􏼂 􏼃np+1[c]0⟶δk+18i 􏼂 􏼃np+1[ ]0. (12) Thus, we have the following: (1) There are 2kcells labelled by i+n· (j−1)in the configuration Cksuch that each of them contains an object li,j,k+1, being l�xif xiis a literal of the clause Cj,xif xiis a literal of the clause Cj and x∗if neither xinor xiare literals of the clause Cj (2) Ck+1(np +1) � δk+1 􏼈 􏼉 (3) There are 2k+1cells labelled by np +2 in the configuration Ck+1such 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 are 2kcells labelled by np +3 in the configuration Ck+1such 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 are 2np−1cells labelled by i+n· (j−1)in the configuration Cnp such that each of them contains an object li,j,np, being l�xif xiis a literal of the clause Cj,xif xiis a literal of the clause Cjand x∗if neither xinor xiare literals of the clause Cj (2) Cnp(np +1) � δnp 􏽮 􏽯 (3) There are 2np 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 are 2np−1cells labelled by np +3 in the configuration Cnp such that each of them contains an object δnp ′ Then, configuration Cnp yields configuration Cnp+1 by applying the rules: Ti,jFi,j′ 􏽨 􏽩np+2[ ]0⟶[ ]np+2[#]0for 1≤i≤n, 1≤j, j′≤p, xi,j,np 􏽨 􏽩i+n·(j−1)⟶xi,j,np+1 􏽨 􏽩i+n·(j−1)xi,j,np+1 􏽨 􏽩i+n·(j−1) xi,j,np 􏽨 􏽩i+n·(j−1)⟶xi,j,np+1 􏽨 􏽩i+n·(j−1)xi,j,np+1 􏽨 􏽩i+n·(j−1) x∗ i,j,np 􏽨 􏽩i+n·(j−1)⟶x∗ i,j,np+1 􏽨 􏽩i+n·(j−1)x∗ i,j,np+1 􏽨 􏽩i+n·(j−1) ⎫ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎬ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎭ for 1≤i≤n, 1≤j≤p, δnp ′ 􏽨 􏽩np+3⟶δnp+1 ′ 􏽨 􏽩np+3δnp+1 ′ 􏽨 􏽩np+3, δnp 􏽨 􏽩np+1[c]0⟶δnp+1 􏽨 􏽩np+1]0. (13) Then, we have the following: (1) There are 2np cells labelled by i+n· (j−1)in the configuration Cnp+1such that each of them contains an object li,j,np+1, being l�xif xiis a literal of the clause Cj,xif xiis a literal of the clause Cjand x∗if neither xinor xiare literals of the clause Cj (2) Cnp+1(np +1) � δnp+1 􏽮 􏽯 (3) There are 2np cells labelled by np +2 in the configuration Cnp+1such that each of them Complexity 7 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 are 2np cells labelled by np +3 in the configuration Cnp+1such that each of them contains an object δnp+1 ′□ 4.1.2. First Checking Stage. From the previous stage, we have that Cnp+1(np +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+1and a set of objects R1,1, R1,2,. . . , R1,p, R2,1,. . . , R2,p,. . . , Rn,1. . . , Rn,p R∈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≤peach of them containing an object li,j,np+1. Then, by the application of the rules from 2.1, objects cjwill be created in the cells labelled by np +2 such that the truth assignment associated with such cell satisfies clause Cjdue to any literal of it. Besides, rules [δnp+1]np+1 [c]0⟶[δnp+2]np+10 ,[δnp+1 ′]np+3[c]0⟶[δnp+2 ′]np+30 are applied. Therefore, we have Cnp+2(np +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+1and 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+1in 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 step np +3 is devoted to checking whether all the clauses Cj,1≤j≤pof the Boolean formula φhave been satisfied by the truth assignment associated with each cell labelled by np +2. We have that Cnp+2(np +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≤pcorresponding to the clauses satisfied by the truth assignment associated with that cell. Then, by applying the rules [αp+1]np+2[δnp+2 ′]np+3⟶[αp+1 ′]np+2np+3,[cjαj]np+2np+3⟶np+2[#]np+3,[δnp+2]np+1[c]0 ⟶[δnp+3]np+10, we obtain the following: Cnp+3(np +1) � δnp+3 􏽮 􏽯and there will be 2np cells labelled by np +2 that will contain an object αjif and only if clause Cjhas not been satisfied by the truth assignment associated with such cell. 4.1.4. Output Stage. The output phase starts at the (np +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+3will evolve into δnp+4by the application of the rule [δnp+3]np+1[c]0 ⟶[δnp+4]np+10, besides the application of rules [αjαp+1 ′]np+20 ⟶np+2[n1]0in other cells. In the next step, since αp+1 ′remains in a cell labelled by np +2, it can evolve with object δnp+4by the rule [αp+1 ′]np+2[δnp+4]np+1⟶[y1]np+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 n1will be sent as n2to 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 n2cannot react with object δnp+4since it has been consumed in the previous step. At the last step of the computation, the only rule applicable will be [y2]np+20 ⟶np+2[yes]0. 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 Cjis not satisfied by the truth assignment corresponding to that cell. Therefore, at step np +3 rules [αjαp+1 ′]np+20 ⟶np+2[n1]0will be applied in all the cells. Therefore, at configuration Cnp+3there will not be any object αp+1 ′in the system, so object δnp+4remains in the cell labelled by np +1. In the next step, objects n1go to cells labelled by np +2, selected in a nondeterministic way. Since object δnp+4is in the cell labelled as np +1 it can make object n2evolve 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 ∈PMCTDEC(2,1) Proof. The family of P systems previously constructed verifies the following: (i) Every system of the family Πis a recognizer P system from T DE C(2,1). (ii) The family Πis polynomially uniform by Turing machines because, for each n, p ∈N, the rules of Π(〈n, p〉) of the family are recursively defined from n, p ∈N, and the amount of resources needed to build an element of the family is of a polynomial order in nand p, as shown below: (1)Size of the alphabet: 3n2p2+11np +p+ 17 ∈ Θ(n2p2) (2) Initial number of cells: np +3∈ Θ(np) 8Complexity (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 pair (cod, 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∈N,s−1(n)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 nthe number of variables in φ and pits 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⊆PMCTDEC(2,1) Proof. It is simple to prove this since it is known that SAT is a NP-complete problem, SAT ∈PMCTDEC(2,1)and the complexity class PMCTDEC(2,1)is closed under polynomialtime reduction and under complementary. □□ Corollary 2. NP ∪co −NP⊆PMCTDEC(3) 5. The Presumed Efficiency of TSEC(2,2) In this section, the presumed efficiency of TSEC(2,2)is established by providing a polynomial time uniform solution to the SAT problem by means of a family of membrane systems Π�Π(t)|t∈N { } from TSEC(2,2). For each pair of natural numbers n, p ∈N, we consider the recognizer tissue P system from TSEC(2,2), Π(〈n, p〉) � (Γ,Γ0,Γ1,E,Σ,M1,M2,R, iin, iout), defined as follows: (i) The working alphabet: Γ�yes,no, y1, y2, n1, n2,# 􏼈 􏼉∪ai,j|1≤i≤n, 0≤j≤i 􏽮 􏽯∪ ai,j ′|2≤i≤n, 0≤j≤i−1 􏽮 􏽯∪ aL i,j, aR i,j|2≤i≤n, 0≤j≤i−1 􏽮 􏽯∪ αj,αj ′,αL j,αR j|1≤j≤p+1 􏽮 􏽯∪ ti, fi, ti ′, ti ″, fi ″, tL i, tR i, fL i, fR i|1≤i≤n 􏽮 􏽯∪ βl,k,βl,k ′,βL l,k,βR l,k0|≤k≤n, 1≤l≤n 􏽮 􏽯∪ xi,j,k, xi,j,k, x∗ i,j,k|1≤i≤n, 1≤j≤p, 0≤k≤n+j−1 􏽮 􏽯∪ xi,j,k ′, xi,j,k ′, x∗ ′ i,j,k, xi,j,k ″, xi,j,k ″, x∗ ″ i,j,k, x″ ′ i,j,k, x″ ′ i,j,k, x∗″ ′ i,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 􏼈 􏼉. (14) (ii) The partition Γ0,Γ1 􏼈 􏼉􏼈 defined as: Γ1�Γ∖Γ0and Γ0�aL i,j|2≤i≤n, 1≤j≤i−1 􏽮 􏽯∪αL j|1≤j≤p+1 􏽮 􏽯∪ tL i, fL i|1≤i≤n 􏽮 􏽯∪βL l,k|0≤k≤n, k +1≤k≤n 􏽮 􏽯. (15) (iii) The input alphabet Σ�xi,j,0, xi,j,0, x∗ i,j,0| 􏽮 1≤i≤n, 1≤j≤p}. (iv) The environment alphabet E�c 􏼈 􏼉. (v) M1�δ0,δ0 ′ 􏼈 􏼉∪βn+p+1 l,0|1≤l≤n 􏽮 􏽯; M2�ai,0|1≤i≤n 􏽮 􏽯∪αj|1≤j≤p+1 􏽮 􏽯. (vi) The set Rconsists of the following rules: (1) Rules for steps 4k+1. Complexity 9