A protocol for solutions to DP-complete problems through tissue membrane systems

Citation: Orellana-Martín, D.; Ramírez-de-Arellano, A.; Andreu-Guzmán, J.A.; Romero-Jiménez, Á.; Pérez-Jiménez, M.J. A Protocol for Solutions to DP-Complete Problems through Tissue Membrane Systems. Mathematics 2023,11, 2797. https:// doi.org/10.3390/math11132797 Academic Editor: Andrea Scozzari Received: 8 May 2023 Revised: 13 June 2023 Accepted: 20 June 2023 Published: 21 June 2023 Copyright: © 2023 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (https:// creativecommons.org/licenses/by/ 4.0/). mathematics Article A Protocol for Solutions to DP-Complete Problems through Tissue Membrane Systems David Orellana-Martín 1,2,* , Antonio Ramírez-de-Arellano 1,2 , José Antonio Andreu-Guzmán 1, Álvaro Romero-Jiménez 1,2 and Mario J. Pérez-Jiménez 1,2 1Research Group on Natural Computing, Department of Computer Science and Artificial Intelligence, Universidad de Sevilla, Avda. Reina Mercedes s/n, 41012 Sevilla, Spain; aramirezdear[email protected] (A.R.-d.-A.); [email protected] (J.A.A.-G.); romero.alvar[email protected] (Á.R.-J.); [email protected] (M.J.P.-J.) 2SCORE Laboratory, I3US, Universidad de Sevilla, Avda. Reina Mercedes s/n, 41012 Sevilla, Spain *Correspondence: dor[email protected] Abstract: Considering a class R comprising recognizer membrane systems with the capability of providing polynomial-time and uniform solutions for NP -complete problems (referred to as a “presumably efficient” class), the corresponding polynomial-time complexity class PMCR encompasses both the NP and co −NP classes. Specifically, when R represents the class of recognizer presumably efficient cell-like P systems that incorporate object evolution rules, communication rules, and dissolution rules, PMCR includes both the DP and co −DP classes. Here, DP signifies the class of languages that can be expressed as the difference between any two languages in NP (it is worth noting that NP ⊆DP and co −NP ⊆co −DP ). As DP -complete problems are believed to be more complex than NP -complete problems, they serve as promising candidates for studying the P vs NP problem. This outcome has previously been established within the realm of recognizer P systems with active membranes. In this paper, we extend this result to encompass any class R of presumably efficient recognizer tissue-like membrane systems by presenting a detailed protocol for transforming solutions of NP-complete problems into solutions of DP-complete problems. Keywords: complexity class; DP; membrane computing; tissue P systems MSC: 68Q07; 68Q15 1. Introduction Roughly speaking, a mechanical procedure consists of a set of elementary tasks, possibly repeated, structured by a total order. A mechanical solution of an abstract problem is a mechanical procedure such that the execution of the corresponding tasks in the order prefixed by the procedure provides the correct solution of the problem. A computing model basically consists of a formal/mathematical definition of the intuitive concept of mechanical procedure. Consequently, in a computing model will be possible to define in a rigorous way what solving an abstract problem through a mechanical way means. A computing paradigm is a mathematical theory that allows us to consider computing models satisfying some syntactic and/or semantic properties previously established in the theory. Membrane Computing is a branch of Natural Computing introduced by Gh. P˘aun at the end of 1998 [ 1 ]. It is a computing paradigm inspired by the architecture and the functioning of living cells, as well as from the way the cells are organized in tissues, organs or other higher-order structures. This paradigm provides distributed, parallel non-deterministic computing models whose computational devices are generically called membrane systems. This paper deals with tissue-like membrane systems inspired by the cell inter-communication in tissues, where the processor units, called cells, are considered to be the nodes of a directed graph. In this context, cells can communicate through some kind Mathematics 2023,11, 2797. https://doi.org/10.3390/math11132797 https://www.mdpi.com/journal/mathematics Mathematics 2023,11, 2797 2 of 13 of rewriting rules (called symport/antiport rules), which were introduced in membrane computing in [ 2 ]. The basic concept of tissue P systems [ 3 , 4 ] gave rise to several research lines and variants: see, for example [ 5 – 7 ]. These systems can present cooperative behavior in the following sense: two or more objects can interact to fire a rule. It can be seen in rules where two or more objects are necessary to be executed. Replication stands as a fundamental function within a cell, where, under optimal conditions, cell division (mitosis) yields two identical copies. Drawing inspiration from this phenomenon, cell division rules were incorporated into the framework of tissue P systems. These rules serve as a mechanism for generating an exponential workspace in terms of the number of objects and cells involved. By employing such rules, the two newly formed cells resulting from the division process contain precisely the same objects, differing at most by a pair of distinct objects. It is a well-established fact that every decision problem can be associated with a language in a manner that solving the decision problem corresponds to recognizing the “corresponding” language. In the field of Membrane Computing, the concept of “Recognizer membrane systems” was introduced in [ 8 ] as a natural framework for solving decision problems through language recognition. A membrane system is considered a recognizer if it exhibits specific syntactic and semantic characteristics: (a) The working alphabet comprises two distinguished objects, namely, yes and no . (b) There exists an input alphabet that is strictly contained within the working alphabet, along with an input “compartment” (a distinguished membrane in the case of cell-like devices, or a distinguished cell in the case of tissue-like devices). (c) The initial content of each cell consists of a multiset of objects from the working alphabet, excluding those from the input alphabet. (d) All computations performed by the system eventually halt. (e) During each computation, either the object yes or the object no (but not both) must be released to the environment, and only at the final step. For a given recognizer membrane system Π , the notation Π+m represents the membrane system obtained by adding the multiset m to the content of the input compartment in the initial configuration of Π. The construction of a recognizer membrane system must be done in polynomial time. Therefore, while all the instances of a decision problem can be solved by a single Turing machine, we must define an infinite family of recognizer membrane systems to solve it. In [ 9 ], the concept of a family Π={Π(n)|n∈N} of recognizer membrane systems solves a decision problem X in polynomial time in a uniform way is described. If such family Π can be generated by a deterministic Turing machine working in polynomial time, and there exists a pair (cod , s) of polynomial-time computable functions over the set of instances of X verifying the following: complete with regard to (X , cod , s) . (for more details, see [ 9 ]). Given a computing model R of recognizer membrane systems, PMCR denotes the set of decision problems solvable by families from R in polynomial-time and in a uniform way. The class PMCR is closed under complement and under polynomial-time reduction [ 9 ]. Thus, if X is a decision problem belongs to a complexity class K then we deduce that K∪ co - K ⊆ PMCR . In [ 10 ], a protocol to generate a solution to a DP -complete [ 11 ] Problem from a solution to a NP -complete problem is given in the framework of recognizer P systems with active membranes, that is applied in [ 12 ]. In this work, a similar protocol is introduced. It is interesting to point out that any solution to a decision problem can be integrated with another solution to create a single solution to the product problem in order to execute each of them in parallel, with the corresponding speedup of the system. The terms efficiency and presumed efficiency of a computing model were introduced in [ 13 ]. These concepts are associated with the ability of the model to provide polynomial-time solutions to computationally hard problems. Specifically, a computing model is said to be efficient (respectively, presumably efficient) if it has the ability to provide polynomial-time solutions for intractable problems (resp., NP -complete problems) [ 13 ]. The term presumably efficient refers to the fact that, as generally believed, if P6=NP then each NP -complete problem is an intractable one; consequently, under this hypothesis, any presumably efficient Mathematics 2023,11, 2797 3 of 13 model would be efficient. Thus, if R is a presumably efficient computing model of a recognizer tissue-like membrane system, then NP ∪co - NP ⊆PMCR , because of class PMCRis closed under complement and under polynomial-time reduction. In [ 14 ], the authors found that P#P is an upper bound of tissue P systems that use either division or separation rules and communication rules of any length. It is interesting to find lower bounds to know which complexity class characterizes the class of recognizer tissue P systems with symport/antiport rules and division/separation rules. In fact, in [ 15 ], the authors demonstrated that the class P#P characterizes the class of recognizer tissue P systems with symport/antiport rules and division/separation rules, softly changing the definition of recognizing a language by means of a family of membrane systems. Apart from that, different results have been obtained both obtaining lower or upper bounds [16–18]. The rest of the paper is organized as follows: Next section is devoted to introducing the methodology to construct a solution to a product problem. In Section 3, the protocol is applied to a specific solution of SAT to create a solution to the SAT - UNSAT problem that is explained in Section 4. Finally, some conclusions and insights for future works are explained. 2. Methodology Let us recall that for each k≥ 1, T DC(k) (respectively, T SC(k) ) denotes the computing model of recognizer tissue-like membrane systems with cell division (respectively, cell separation) and communication rules (of the type symport/antiport) with length at most k . On the one hand, the models T DC( 1 ) , T SC( 1 ) and T SC( 2 ) are non-efficient (see [ 19 , 20 ] for details). On the other hand, the models T DC(k) , for k≥ 2, and T SC(k) for k≥ 3, are presumably efficient (see [ 21 , 22 ] for details). We call a membrane system cooperative if it has at least one rule that needs two objects to be fired. In this case, P systems from T DC( 1 ) and T SC( 1 ) are non-cooperative membrane systems, while P systems from T DC(k) and T SC(k) ( k≥ 2) are cooperative membrane systems. Let X1= (IX1 , θX1) and X2= (IX1 , θX1) be decision problems, the product problem of X1 and X2 , denoted by X1⊗X2 , is defined as follows: θX1⊗X2(u1+u2) = 1iffθX1(u1) = 1∧θX2(u2) = 1 0otherwise , being u1∈IX1and u2∈IX2 The main contribution of this paper is to provide a lower bound ( DP ∪co - DP ) for PMCR thinner than NP ∪co - NP , in the case that R is a class of recognizer cooperative tissue-like P systems. Theorem 1. Let R be a computing model of recognizer cooperative tissue-like P systems. If X1 and X2 are decision problems belonging to the time complexity class PMCR , then X1⊗X2∈PMCR . Proof. For i= 1,2, let Π(i)={Π(i)(t)|t∈N} a family of recognizer tissue-like P systems from R solving Xi in polynomial-time in a uniform way. Let (codi , si) be a polynomial encoding from Xi into Π(i) . Let pi(n) be a polynomial function such that for each instance ui from Xi , any computation of Π(i)(si(ui)) + codi(ui) performs at most pi(|ui|) steps. Then, after n=max{p1(|u1|) , p2(|u2|)} transition steps, both answers of systems Π(1)(s1(u1)) + cod1(u1)and Π(2)(s2(u2)) + cod2(u2)are provided in the environment. In this situation, a family Π={Π(t)|t∈N} of membrane systems from R will be defined from Π(1) and Π(2) , in such a manner that Π provides a uniform and polynomialtime solution to the product problem X1⊗X2. First, a pair of polynomial-time functions (cod , s) over the set of instances of X1⊗X2 is considered as follows: (a) cod(u1 , u2) = cod1(u1) + cod2(u2) ; and (b) s(u1 , u2) = hs1(u1) , s2(u2)i , for each (u1 , u2)∈IX1⊗X2 , where h· , ·i denotes the Cantor pairing function, a (bijective and recursive) mapping from N×N onto N defined as ht1 , t2i= [(t1+t2)·(t1+t2+ 1 )/ 2 ] + t1 . The idea is that the instance (u1 , u2) will be Mathematics 2023,11, 2797 4 of 13 processed by the system Π(s(u1 , u2)) with input multiset cod(u1 , u2) . This system will be denoted by Π(hs1(u1),s2(u2)i) + cod(u1,u2). In the following, the membrane system Π(hs1(u1) , s2(u2)i) will be explicitly defined from Π(1)(s1(u1)) and Π(2)(s2(u2)) , for each instance (u1 , u2) of the product problem X1⊗X2 , so that: a computation of Π(hs1(u1) , s2(u2)i) + cod(u1 , u2) is an accepting one if and only if there exist accepting computations of the systems Π(1)(s1(u1)) + cod1(u1) and Π(2)(s2(u2)) + cod2(u2) . Consequently, we will have: (a) if there exist accepting computations of the system Π(hs1(u1) , s2(u2)i) + cod(u1 , u2) then θX1⊗X2= 1; and (b) if θX1⊗X2= 1 then any computation of Π(hs1(u1) , s2(u2)i) + cod(u1 , u2) is an accepting one. According to this, (cod , s) will be a polynomial encoding from the product problem X1⊗X2 into the family Π . It is worth pointing out that, in fact, only membrane systems Π(t) such that t∈range(s)are defined, and this is enough to achieve our goal. In what follows, we will denote t=hs1(u1) , s2(u2)i , t1=s1(u1) and t2=s2(u2) . Let us recall that given an arbitrary natural number t∈N there exists a unique pair of natural numbers t1,t2such that t=ht1,t2i. The underlying idea of the construction of Π(t)is the following: when cod(u1 , u2) is considered as the input multiset of this system, the multisets cod1(u1) and cod2(u2) are sent to the corresponding input cells of systems Π(1)(t1) and Π(2)(t2) , respectively. Then, computations of Π(1)(t1) + cod1(u1) and Π(2)(t2) + cod2(u2) will be simulated. The answers from both systems will be provisionally placed in a cell where the final decision is taken: accepting computations of Π(t) + cod(u1 , u2) only come from both accepting computations of Π(1)(t1) + cod1(u1)and Π(2)(t2) + cod2(u2). Without loss of generality, we can assume that Γ(i)(ti)\{yes , no} , for i= 1,2, are mutually disjoint, being Γ(i)(ti) the working alphabet of Π(i)(ti) . Likewise, we can assume the same with the corresponding sets of labels H(1)(t1)and H(2)(t2). The syntactical ingredients of Π(t)are the following: • Cells. The cells of Π(t) are the cells of Π(1)(t1) and Π(2)(t2) , plus three additional cells. •Working alphabet. The working alphabet is Γ(1)(t)∪Γ(2)(t)∪Γ(3)(t), where: Γ(1)(t)=[Γ(1)(t1)\{yes,no}]∪ {yes1,no1} Γ(2)(t)=[Γ(2)(t2)\{yes,no}]∪ {yes2,no2} Γ(3)(t) = {a0|a∈Γ(1)(t1)∪Γ(2)(t2)}. • Input alphabet. The input alphabet is Σ(t) = Σ(1∗)(t1)∪Σ(2∗)(t2) , being Σ(i∗)(ti) the input alphabet of Π(i)(ti) , by replacing objects yes and no by objects yesi and noi , for i=1,2, respectively. • Alphabet of the environment. The alphabet E of the environment of Π(t) is E1∪E2 , where Eiis the alphabet of the environment of Π(i)(ti), for i=1,2. • Set of labels. The set of labels is H(1)(t1)∪H(2)(t2)∪ {aux0 , aux+ , aux−} , where aux0 , aux+ , aux− are different from each other and none of them belong to the set H(1)(t1)∪H(2)(t2) . Specifically, aux0 , aux+ , aux− will be the labels associated with the three new cells. •Initial multisets. The initial multisets of Π(t)are the following: (a) For i= 1,2, if h is the label of a cell from Π(i)(ti) whose initial multiset is Mh(ti) then the initial multiset associated with h in Π(t) is Mh(t) = {a0|a∈ Mh(ti)} , that is, for each object a initially placed in cells of Π(i)(ti) , a primed version a0 is considered instead when Π(i)(ti)is taken as a part of Π(t). (b) Maux0(t) = M(t1)∪ M(t2)∪{yes , no} ,being M(ti) the union of the initial multisets of Π(i)(ti). (c) Maux+(t) = Maux−(t) = ∅. • Set of rules. The set of rules is RΠ(1)(t1)∪RΠ(2)(t2)∪R∗ t , where RΠ(i)(ti) is the set of rules of Π(i)(ti) , for i= 1,2, obtained through the replacement of objects yes and no Mathematics 2023,11, 2797 5 of 13 by objects yesi and noi , respectively, in each rule. In addition, R∗ t is the following set of rules: 1. Rules for simultaneously transporting codi(ui) from cell labeled by aux0 to the input cell inΠ(i) (ti) of Π(i) (ti), for i =1,2. 1.1. (aux0,a/λ,inΠ(1)(t1)), for each a∈Σ(1)(t1). 1.2. (aux0,a/λ,inΠ(2)(t2)), for each a∈Σ(2)(t2). 2. Rules to obtain the rules from Π(i)(ti) , for i= 1,2, started in the second transition step. 2.1. (h , a0/a , aux0) , for each a∈[Γ(1)(t1)∪Γ(2)(t2)] \[Σ(1)(t1)∪Σ(2)(t2)] and for each label hof a cell in Π(1)(t1)∪Π(2)(t2). 3. Rules for transporting the pair of answers of the systems Π(i)(ti) , for i= 1,2, from the environment to cell aux+or aux−. 3.1. (env ,yes1yes2/λ,aux+). 3.2. (env ,yes1no2/λ,aux−). 3.3. (env ,no1yes2/λ,aux−). 3.4. (env ,no1no2/λ,aux−). 4. Rules for the affirmative answer of the system Π(t) + cod(u1,u2): 4.1. (aux+,yes1/yes ,aux0). 4.2. (aux+,yes /λ,env). 5. Rules for the negative answer of the system Π(t) + cod(u1,u2): 5.1. (aux−,no1/no ,aux0). 5.2. (aux−,no2/no ,aux0). 5.3. (aux−,no /λ,env). •Input cell. The input cell is the cell labelled by aux0. The system Π(t)can be graphically depicted as in Figure 1. aux− cod1(u1) + cod2(u2) yes no aux0aux+ Π(1)(t1) Π(2)(t2) cod1(u1) inΠ(1)(t1) cod2(u2) inΠ(2)(t2) Figure 1. System Π(t)described from systems Π(1)(t1)and Π(2)(t2). An Overview of the Computations of Π(t) + cod(u1,u2) The proposed solution can be structured in the following stages: •Transport stage Once the input multiset cod(u1 , u2) = cod1(u1) + cod2(u2) is supplied to the input cell aux0 of the system Π(t) , by applying the rules from 1.1 , and 1.2 , in the first computation step multisets cod1(u1) and cod2(u2) enter into the input cell inΠ(1)(t1) and inΠ(2)(t2) , respectively. Simultaneously, in this first step, by applying the rules from Mathematics 2023,11, 2797 6 of 13 2.1 , objects a0 initially placed in each cell of Π(i)(ti) is transformed in the corresponding non-primed object a. This stage takes only one transition step. •Simulation stage Starting at the second transition step, computations of the system Π(i)(ti) with input multiset codi(ui) are simulated by applying the corresponding rules from Π(i)(ti) , for i= 1,2. Then, after at most 1 +max{p1(|u1|) , p2(|u2|)} transition steps, both systems Π(1)(t1) + cod1(u1) and Π(2)(t2) + cod2(u2) will send their answers to the environment. Therefore, this stage takes at most 1 +nsteps. •Output stage The system Π(t) with input multiset cod(u1 , u2) sends the right answer to the environment according to the results obtained in the previous stage. Bearing in mind that rules 3.1 , 3.2 , 3.3 and 3.4 are cooperative, they will only be applicable when the environment receive the answers from Π(1)(t1) + cod1(u1) and Π(2)(t2) + cod2(u2) . Let us assume that at instant k both answers reach the environment (obviously, kdepends on the computations selected in the simulations and k≤1+n). –Affirmative answer. In this case, the answers of Π(1)(t1) + cod1(u1) and Π(2)(t2) + cod2(u2) will be yes1 and yes2 , respectively. By applying rule 3.1 , objects yes1 and yes2 are sent to cell aux+ , that is Ck+1(aux+) = {yes1 , yes2} . By applying rule 4.1 we will have Ck+2(aux+) = {yes , yes2} and Ck+2(aux0) = {yes1 , no} . Finally, by applying rule 4.2 the system send out to the object yes and the system halts. It is graphically depicted in Figure 2. –Negative answer. In this case, at least one answer of Π(1)(t1) + cod1(u1) or Π(2)(t2) + cod2(u2) must be negative. By applying rule 3.2 or 3.3 or 3.4 , cell aux− from configuration Ck+1 will contain object no1 either object no2 either both of them. By applying rule 5.1 or rule 5.2 (only one of them because cell aux0 from configuration Ck+1 only contain one object no ) will have no ∈ Ck+2(aux−) . Finally, by applying rule 5.3 the system send out to the object no and the system halts. It is graphically depicted in Figure 3. Ck yes1yes2 yes no aux0 aux+ aux− 3.1 =⇒ Ck+1 yes no aux0 yes1 yes2 aux+ aux− 4.1 =⇒ Ck+2 yes1 no aux0 yes yes2 aux+ aux− 4.2 =⇒ Ck+3 yes yes1 no aux0 yes2 aux+ aux− Figure 2. The answer of Π(1)(t1)is yes and the answer of Π(2)(t2)is yes. Mathematics 2023,11, 2797 7 of 13 Ck yes1no2 yes no aux0 aux+ aux− 3.2 =⇒ Ck+1 yes no aux0 aux+ yes1 no2 aux− 5.2 =⇒ Ck+2 yes no2 aux0 aux+ yes1 no aux− 5.3 =⇒ Ck+3 no yes no2 aux0 aux+ yes1 aux− Figure 3. The answer of Π(1)(t1)is yes and the answer of Π(2)(t2)is no. Remark 1. Concerning the proof of Theorem 1, we would like to draw attention to several aspects: (a) Recognizer cooperative tissue-like membrane systems from class R are required to allow the use of communication rules with the length of at least 2, and the length of the new rules added is exactly 2. (b) A explicit solution of the product problem product is provided from two respective solutions of the problems involved in that operation. Corollary 1. If R is a presumably efficient computing model of a recognizer tissue-like membrane system, then DP ∪co-DP ⊆PMCR. Proof. First, let us note that if R is a presumably efficient computing model of a recognizer tissue-like membrane system and P6=NP , then systems from R are cooperative (see [ 19 , 20 ] for details). Let X be an NP complete problem such that X∈PMCR . Then, the complement problem X is a co - NP complete problem such that belongs to class PMCR . From Theorem 1, we deduce that X⊗X∈PMCR . Since the product problem X⊗X is a DP complete problem and the complexity class PMCR is closed under complement and under polynomial-time reduction, DP ∪co-DP ⊆PMCRfollows. Remark 2. According with the proofs of Theorem 1 and Corollary 1, a polynomial time and uniform solution to a DP -complete problem by means of a family of recognizer cooperative tissue-like membrane systems, can be explicitly designed from a given polynomial time and uniform solution to a NP -complete problem. In fact, given an NP -complete problem X such that X∈PMCR , where R is a class of presumably efficient computing model of a recognizer tissue-like membrane system, a DP -complete problem, the product problem X⊗X , is associated with it, in such a manner that if X∈PMCRthen X ⊗X∈PMCR, for such kind class Rof recognizer tissue-like systems. 3. Solving DP-Complete Problems by Using a New Methodology In this section, the main Theorem is used to provide solutions to some DP -complete problems obtained from specific solutions to NP -complete problems in the framework of recognizer cooperative tissue-like membrane systems. In particular we use the efficient solution to the SAT problem by means of a family of recognizer tissue P systems with symport/antiport rules with length at most 2 and division rules from [ 23 ], that is based on the classical generation-checking-output workflow. As mentioned in the methodology, given a family of recognizer P systems Π(1) from R efficiently solving a problem X from the complexity class C , then a family of recognizer P systems Π(2) from R that solves the complementary problem of X, being X∈co −C. The SAT-UNSAT problem is defined as follows: Let ϕ1 (respectively, ϕ2 ) be a propositional logic formula with n1 variables (resp., n2 variables) and p1 clauses (resp., p2 clauses). We say that the pair (ϕ1 , ϕ2) is true if and only if ϕ1 is satisfiable and ϕ2 is unsatisfi- Mathematics 2023,11, 2797 8 of 13 able. Formally, let SAT −UNSAT = (ISAT−UNSAT , θSAT−UNSAT) , where ISAT−UNSAT ={(ϕi , ϕ2)| ϕ1,ϕ2are propositional logic formulae in CNF and in a simplified form}. θSAT−UNSAT((ϕ1,ϕ2)) = 1iff ϕ1∈LSAT ∧ϕ2∈LUNSAT 0otherwise Let Γ(1) be the working alphabet of Π(1) and Γ(2) be the working alphabet of Π(2) . Given that we need that Γ(1)∩Γ(2)=∅ , we let Γ(2)={a|a∈Γ(1)} ; that is, objects from Γ(2) will be boldfaced versions of objects from Γ(1) . In Γ(1) (respectively, Γ(2) ) we will change objects yes and no by objects yes1 and no1 (resp., yes2 and no2 ). In addition, let H(1) be the working alphabet of Π(1) . The set of labels H(2) of Π(2) will be defined as H(2)={h|h∈H(1)} . For each quadruple of natural numbers n1 , p1 , n2 , p2∈N , we will consider the recognizer tissue P system with cell division and symport/antiport rules of length at most 2. Π(hhn1,p1i,hn2,p2ii) = (Γ,E,Σ,M1, . . . , Mn1p1+3,M1, . . . , Mn2p2+3,Maux+, Maux−,Maux0,R,iin,iout) of degree n1p1n2p2+6 defined as follows: (a) Γ=Γ0∪{a0|a∈Γ0}, Γ0=Σ∪ E ∪ {yes,no} ∪ {yes1,no1,α,β0,γ0} ∪ {cj|1≤k≤p1}∪ {αk|0≤k≤n1p1−1} ∪ {ai,j|1≤i≤n1,1 ≤j≤p1}∪ {Ti,j,Fi,j|1≤i≤n1,1 ≤j≤p1}∪ {xi,j,k,xi,j,k|1≤i≤n1,1 ≤j≤p1,0 ≤k≤n1p1}∪ {yes2,no2,ff,fi0,fl0} ∪ {cj|1≤k≤p2}∪ {ffk|0≤k≤n2p2−1} ∪ {ai,j|1≤i≤n2, 1 ≤j≤p2}∪ {Ti,j,Fi,j|1≤i≤n2,1 ≤j≤p2}∪ {xi,j,k,xi,j,k|1≤i≤n2,1 ≤j≤p2,0 ≤k≤n2p2} (b) E={αk|n1p1≤k≤2n1p1+2} ∪ {βk|1≤k≤2n1p1+4}∪ {γk|1≤k≤2n1p1+5}∪ {xi,j,k,xi,j,k|1≤i≤n1,1 ≤j≤p1,n1p1+1≤k≤2n1p1}∪ {ffk|n2p2≤k≤2n2p2+2} ∪ {fik|1≤k≤2n2p2+4}∪ {flk|1≤k≤2n2p2+5}∪ {xi,j,k,xi,j,k|1≤i≤n2,1 ≤j≤p2,n2p2+1≤k≤2n2p2} (c) Σ={xi,j,0,xi,j,0 |1≤i≤n1,1 ≤j≤p1}∪ {xi,j,0,xi,j,0|1≤i≤n2,1 ≤j≤p2} (d) Mi=∅ for i∈ {aux+ , aux−} , Maux0={β∗ 0 , γ∗ 0}∪ {a∗ i,j| 1 ≤i≤n1 ,1 ≤j≤ p1} ∪ {c∗ j| 1 ≤j≤p1} ∪ {α∗}∪ {α∗ 0} ∪ {fi0 , fl0}∪ {ai,j| 1 ≤i≤n2 ,1 ≤ j≤p2} ∪ {cj| 1 ≤j≤p2} ∪ {ff}∪ {ff0}∪ {yes1 , no1 , β∗ 0 , γ∗ 0}∪ {a∗ i,j| 1 ≤ i≤n1 ,1 ≤j≤p1}∪{c∗ j| 1 ≤j≤p1} ∪ {α∗}∪ {α∗ 0}∪{yes2 , no2 , fi∗ 0 , fl∗ 0}∪ {a∗ i,j| 1 ≤i≤n2 ,1 ≤j≤p2}∪{c∗ j| 1 ≤j≤p2}∪{ff∗}∪ {ff∗ 0} , Mi={a0|a∈ Miin the original solution},Mi={a0|a∈ Miin the original solution} (e) The set of rules Ris the following: [ai,j]n1p1+2→[Ti,j]n1p1+2[Fi,j]n1p1+2 (n1p1+2, Ti,jFi,j0, /λ,env)for 1≤i≤n1,1 ≤j,j0≤p1 (n1p1+1, xi,j,0/λ,i+n1·(j−1)) (n1p1+1, xi,j,0/λ,i+n1·(j−1)) for 1≤i≤n1, 1≤j≤p1 Mathematics 2023,11, 2797 9 of 13 [xi,j,k]i+n1·(j−1)→[xi,j,k+1]i+n1·(j−1)[xi,j,k+1]i+n1·(j−1) [xi,j,k]i+n1·(j−1)→[xi,j,k+1]i+n1·(j−1)[xi,j,k+1]i+n1·(j−1))for 1≤i≤n1, 1≤j≤p1, 0≤k≤n1p1−1 (i+n1·(j−1),xi,j,k/xi,j,k+1,env) (i+n1·(j−1),xi,j,k/xi,j,k+1,env)for 1≤i≤n1, 1≤j≤p1, n1p1≤k≤2n1p1−1 (n1p1+2, Ti,j/xi,j,2n1p1,i+n1·(j−1)) (n1p1+2, Fi,j/xi,j,2n1p1,i+n1·(j−1)) f or 1≤i≤n1, 1≤j≤p1 (n1p1+2, cjxi,j,2n1p1/λ,env) (n1p1+2, cjxi,j,2n1p1/λ,env)f or 1≤i≤n1,1 ≤j≤p1 [αk]n1p1+3→[αk+1]n1p1+3[αk+1]n1p1+3f or 0≤k≤n1p1−1 (n1p1+3, αn1p1+k/αn1p1+k+1,env)f or 0≤k≤n1p1+1 (n1p1+1, βk/βk+1,env)f or 0≤k≤2n1p1+3 (n1p1+1, γk/γk+1,env)f or 0≤k≤2n1p1+4 (n1p1+2, α/α2n1p1+2,n1p1+3) (n1p1+2, α2n1p1+2cj/λ,env)f or 1≤j≤p1 (n1p1+1, β2n1p1+4,γ2n1p1+5/λ,n1p1+3) (n1p1+1,no1/β2n1p1+4,n1p1+3) (n1p1+3,no1/λ,env) (n1p1+1, β2n1p1+4/α2n1p1+2,n1p1+2) (n1p1+1, α2n1p1+2yes1/λ,env) [ai,j]n2p2+2→[Ti,j]n2p2+2[Fi,j]n2p2+2 (n2p2+2,Ti,jFi,j0, /λ,env)for 1≤i≤n2,1 ≤j,j0≤p2 (n2p2+1,xi,j,0/λ,i+n2·(j−1)) (n2p2+1,xi,j,0/λ,i+n2·(j−1)) for 1≤i≤n2, 1≤j≤p2 [xi,j,k]i+n2·(j−1)→[xi,j,k+1]i+n2·(j−1)[xi,j,k+1]i+n2·(j−1) [xi,j,k]i+n2·(j−1)→[xi,j,k+1]i+n2·(j−1)[xi,j,k+1]i+n2·(j−1))for 1≤i≤n2, 1≤j≤p2, 0≤k≤n2p2−1 (i+n2·(j−1),xi,j,k/xi,j,k+1,env) (i+n2·(j−1),xi,j,k/xi,j,k+1,env)for 1≤i≤n2, 1≤j≤p2, n2p2≤k≤2n2p2−1 (n2p2+2,Ti,j/xi,j,2n2p2,i+n2·(j−1)) (n2p2+2,Fi,j/xi,j,2n2p2,i+n2·(j−1)) f or 1≤i≤n2, 1≤j≤p2 (n2p2+2,cjxi,j,2n2p2/λ,env) (n2p2+2,cjxi,j,2n2p2/λ,env)f or 1≤i≤n2,1 ≤j≤p2 [ffk]n2p2+3→[ffk+1]n2p2+3[ffk+1]n2p2+3f or 0≤k≤n2p2−1 (n2p2+3,ffn2p2+k/ffn2p2+k+1,env)f or 0≤k≤n2p2+1 (np +1,fik/fik+1,env)f or 0≤k≤2n2p2+3 (n2p2+1,flk/flk+1,env)f or 0≤k≤2n2p2+4 (n2p2+2,ff/ff2n2p2+2,n2p2+3) (n2p2+2,ff2n2p2+2cj/λ,env)f or 1≤j≤p2 (n2p2+1,fi2n2p2+4,fl2n2p2+5/λ,n2p2+3) (n2p2+1,yes2/fi2n2p2+4,n2p2+3) (n2p2+3,yes2/λ,env) (n2p2+1,fi2n2p2+4/ff2n2p2+2,n2p2+2) (n2p2+1,ff2n2p2+2no2/λ,env) Apart from these, all rules indicated in Section 2must be added.