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

Research Article The Computational Complexity of Tissue P Systems with Evolutional Symport/Antiport Rules Linqiang Pan ,1,2 Bosheng Song ,1Luis Valencia-Cabrera,3and Mario J. Pérez-Jiménez3 1Key Laboratory of Image Information Processing and Intelligent Control of Education Ministry of China, School of Automation, Huazhong University of Science and Technology, Wuhan, Hubei 430074, China 2School of Electric and Information Engineering, Zhengzhou University of Light Industry, Zhengzhou 450002, China 3Research Group on Natural Computing, Department of Computer Science and Artificial Intelligence, University of Sevilla, Avda. Reina Mercedes s/n, 41012 Sevilla, Spain Correspondence should be addressed to Bosheng Song; boshengson[email protected]u.cn Received 29 May 2017; Accepted 18 December 2017; Published 23 April 2018 Academic Editor: Sigurdur F. Hafstein Copyright © 2018 Linqiang Pan 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. Tissue P systems with evolutional communication (symport/antiport) rules are computational models inspired by biochemical systems consisting of multiple individuals living and cooperating in a certain environment, where objects can be modified when moving from one region to another region. In this work, cell separation, inspired from membrane fission process, is introduced in the framework of tissue P systems with evolutional communication rules. The computational complexity of this kind of P systems is investigated. It is proved that only problems in class Pcan be efficiently solved by tissue P systems with cell separation with evolutional communication rules of length at most (𝑛,1), for each natural number 𝑛≥1. In the case where that length is upper bounded by (3,2), a polynomial time solution to the SAT problem is provided, hence, assuming that P= NP a new boundary between tractability and NP-hardness on the basis of the length of evolutional communication rules is provided. Finally, a new simulator for tissue P systems with evolutional communication rules is designed and is used to check the correctness of the solution to the SAT problem. 1. Introduction A cell is the basic unit of biological organization that constitutes all living organisms. There are many different types of biological cells, which have different specialized functions that maintain an organism working properly. Inspired by the structure and functioning of living cells, P˘ aun proposed a computing paradigm in 2000 [1], called membrane computing, which has become an active research area (for other research domains of natural computing, one can refer to [2, 3]). A large number of theoretical models were proposed [4–6] and they have been used to solve various real problems [7–10]. These distributed and parallel computation models investigated in membrane computing are called P systems. In general, there exist two main families of P systems: celllike P systems [1], which have a hierarchical arrangement of membranes described by a rooted tree (corresponding to celllike membrane structure), and tissue-like P systems [11] or neural-like P systems [12], which have a net of cells or neurons described by a directed graph. An overview of membrane computing can be found in [13]. The present work deals with tissue-like P systems. Inspired by the biological phenomenon of trans-mem- brane transport of couples of chemicals, communication P systems with symport/antiport rules were proposed in [14], where symport rules move objects (without evolution) between two regions in one direction, and antiport rules move objects (without evolution) between two regions in opposite directions. Later, symport/antiport rules were considered in tissue-like P systems [11], where cells are placed in nodes of a directed graph, and an arc between two nodes corresponds to a communication channel between cells placed in these nodes. Since the notion of tissue P systems was proposed, numerous research topics have been arisen [15–18], and various ingredients (energy, catalyst, mitosis, etc.) from other Hindawi Complexity Volume 2018, Article ID 3745210, 21 pages https://doi.org/10.1155/2018/3745210 2Complexity computational models were considered in the context of tissue P systems. In [19], tissue P systems with channel states controlling the communication between two regions were proposed, and several Turing universality results were achieved, where the systems work in a maximally parallel waywithsequentialbehavioronchannels.In[20],ageneral model of tissue P systems with channel states that allow us to model hybrid cooperating grammar systems was considered, where the results were established for strings and arrays. Tissue P systems have been used to find polynomial time solutions to NP-complete problems. In [21], membrane division rules used in P systems with active membranes have been introduced into tissue P systems yielding tissue P systems with cell division, and a polynomial time uniform solution to the SAT problem was shown. Since then, tissue P systems with cell division were also considered to solve other NP-complete problems: bin packing [22], subset sum [23], vertex cover [24], and so on. Cell division rules have a replication functioning; that is, two new created cells by a division rule have exactly the same objects except for at most a pair of different objects. Inspired from membrane fission process, cell separation rules are another way to obtain an exponential workspace in polynomial time, but they do not have the duplication functioning; that is, when a cell is separated, the objects in the cell are distributed in each of the newly created cells. Tissue P systems with cell separation have also been used to solve NP-complete problems in polynomial time; one can refer to [25, 26] for these investigations. Computational complexity theory in the framework of tissue P systems was introduced in [21] and it has been studied in [27–30]. It was shown that in the framework of tissue P systems with cell division, only tractable problems can be efficiently solved by using communication rules with length at most one [31] (the length of such a rule is the total number of objects involved in it), but a uniform polynomial time solution to the HAM-CYCLE problem by a family of such P systems using communication rules with length at most two has been given [30]. On the other hand, in the framework of tissue P systems with cell separation, by using communication rules with length at most two, only tractable problemscanbeefficientlysolved,buttheSAT problem can be solved by this kind of P systems using communication rules with length at most three [26]. Moreover, frontiers between efficiency and nonefficiency in terms of the length of symport/antiport rules in the framework of cell-like P systems have been investigated in [32]. Tissue-like P systems with evolutional symport/antiport rules (TESA P systems, for short) were proposed in [33], where objects are moved from one region to another region andmaybeevolvedduringthisprocess.In[33],thecomputational efficiency of TESA P systems with cell division (TESAD P systems, for short) was investigated. It is shown that a limit on the efficiency of TESAD P systems is provided with evolutional communication rules of length at most 2. However, when using evolutional communication rules of length at most 4, the SAT problem can be solved by TESAD P systems. However, it is still an open problem as formulated in [33] related to the role of evolutional communication rules in tissue P systems with cell separation from a computational complexitypointofview. During those computational complexity studies for new variants of P systems, the solutions designed for NP-complete problems are frequently difficult to follow, and requerying makes sure that the evolution of the systems is exactly as expected. In this context, the aid of computer tools to assist in both the design and verification tasks may be crucial, producing much more reliable solutions. In this sense, the development of P-Lingua [34–36] implied a significant progress. This open source framework includes a standard language aiming to specify the elements of different types of P systems using a notation very close to the researchers in membrane computing community. Besides, it contains simulation engines for a number of P system types. On top of that, MeCoSim [37, 38] provides an additional layer of abstraction with a visual application where researchers can explore at a higher level the evolution of their solutions based on P systems. In this work, we investigate tissue P systems with evolutional symport/antiport rules and cell separation (TESAS P systems, for short) from a computational complexity point of view. Contributions of the present work are summarized as follows: (a) A variant of tissue P systems with evolutional symport/antiport rules, called tissue P systems with evolutional symport/antiport rules and cell separation (TESAS P systems, for short), and the corresponding recognizer version are proposed. In TESAS P systems, the length of an evolutional symport/antiport rule 𝑟is defined as an ordered pair whose first component is the total number of objects involved in the left hand side (LHS) of the rule and the second component is the total number of objects involved in the right hand side (RHS) of the rule; that is, length(𝑟) = (length(LHS(𝑟)), length(RHS(𝑟))).The setofallrecognizerTESASPsystemswithevolutional communication rules of length at most (𝑘1,𝑘2)is denoted by TSEC(𝑘1,𝑘2). (b) The computation efficiency of recognizer TESAS P systems is investigated in terms of the length of evolutional communication rules. It is shown that only tractable problems can be efficiently solved by families of systems from TSEC(𝑛,1) or from TSEC(1,𝑛),foreachnaturalnumber𝑛≥1.We further show that the SAT problem can be solved in polynomial time by a family of systems from TSEC(3,2),hence,assumingthatP= NP,anew boundary between tractability and NP-hardness on the basis of the length of evolutional communication rules, is provided. (c) A new simulator MeCoSim is designed in order to check the correctness of the solution to the SAT problem. By using the software MeCoSim, we can analyse the designed P systems, then run the simulation, and obtain the computation results. Complexity 3 2. Tissue P Systems with Evolutional Symport/Antiport Rules and Cell Separation Let us start this section by recalling some notions from formal language theory used in this work; the reader can find details in [39]. An alphabet Γis a nonempty set. Any sequence 𝑢of elements from Γis called a string over Γ.Thelength of 𝑢, denoted by |𝑢|, is the number of occurrences in 𝑢of symbols from Γ. Amultiset over an alphabet Γis a function 𝑚from Γto the set of natural numbers N.Themultiplicityofasymbol 𝑎∈Γin the multiset 𝑚is 𝑚(𝑎).Thesupport of 𝑚is the set of symbols 𝑎such that 𝑚(𝑎) > 0. A multiset is finite and its support is a finite set. The set of all finite multisets over Γis denoted by 𝑀𝑓(Γ),andby𝑀+ 𝑓(Γ)we denote the set of all nonempty finite multisets over an alphabet Γ,andtheempty multiset is denoted by 0.Thecardinalofafinitemultiset𝑚, denoted by |𝑚|, is the sum of all multiplicities of elements in the support of 𝑚.If𝑚1and 𝑚2are multisets over Γ,thenwe define the union of 𝑚1and 𝑚2, denoted by 𝑚1+𝑚2, as follows: (𝑚1+𝑚2)(𝑎) = 𝑚1(𝑎)+𝑚2(𝑎),foreach𝑎∈Γ. Definition 1. A tissue P system with evolutional symport/ antiport rules and cell separation of degree 𝑞≥1is a tuple Π=(Γ,Γ 0,Γ 1,E,M1,...,M𝑞,R,𝑖out), (1) where (i) Γand Eare finite alphabets such that E⊆Γ; (ii) Γ0,Γ1are nonempty sets such that Γ0∪Γ 1=Γand Γ0∩Γ 1=0; (iii) M1,...,M𝑞are multisets over Γ; (iv) Ris a finite set of rules of the following forms: (1) evolutional communication rules: (a) [𝑢]𝑖[] 𝑗→[] 𝑖[𝑢󸀠]𝑗,where0≤𝑖,𝑗≤𝑞, 𝑖 =𝑗,𝑢∈𝑀 + 𝑓(Γ),𝑢󸀠∈𝑀 𝑓(Γ) (evolutional symport rules); (b) [𝑢]𝑖[V]𝑗→[V󸀠]𝑖[𝑢󸀠]𝑗,where0≤𝑖,𝑗≤𝑞,𝑖 = 𝑗,𝑢,V∈𝑀 + 𝑓(Γ),𝑢󸀠,V󸀠∈𝑀 𝑓(Γ)(evolutional antiport rules); (2) separation rules: (a) [𝑎]𝑖→[Γ 0]𝑖[Γ1]𝑖,where𝑖 ∈ {1,...,𝑞},𝑖 = 𝑖out,𝑎∈Γ; (v) 𝑖out ∈{0,1,...,𝑞}. A tissue P system with evolutional symport/antiport rules and cell separation of degree 𝑞≥1,Π=(Γ,Γ 0,Γ 1,E, M1,...,M𝑞,R,𝑖out),canbeviewedasasetof𝑞cells, labelled by 1,...,𝑞such that (a) M1,...,M𝑞represent the multisets of objects initially placed in the 𝑞cells of the system; (b) E is the set of objects initially located in the environment of the system, all of them available in an arbitrary number of copies; and (c) 𝑖out represents a distinguished region which will encode the output of the system. We use the term region 𝑖(0≤𝑖≤𝑞) to refer to cell 𝑖in the case 1≤𝑖≤𝑞andtorefer to the environment in the case 𝑖=0. Aconfiguration at any instant of a TESAS P system is described by multisets of objects in each cell and the multiset of objects over Γ\Ein the environment at that moment. The initial configuration of Π=(Γ,Γ 0,Γ 1,E,M1,...,M𝑞,R,𝑖out) is (M1,...,M𝑞,0). An evolutional symport rule [𝑢]𝑖[] 𝑗→[] 𝑖[𝑢󸀠]𝑗is enabled at a configuration C𝑡at an instant 𝑡if there is a region 𝑖from C𝑡which contains multiset 𝑢.Byapplyingan evolutional symport rule, the multiset of objects 𝑢in region 𝑖from C𝑡is consumed and the multiset of objects 𝑢󸀠is generatedinregion𝑗from C𝑡+1. An evolutional antiport rule [𝑢]𝑖[V]𝑗→[V󸀠]𝑖[𝑢󸀠]𝑗is enabled at a configuration C𝑡at an instant 𝑡if there is a region 𝑖from C𝑡which contains multiset of objects 𝑢and a region 𝑗from C𝑡which contains multiset of objects V. By applying an evolutional antiport rule, (a) the multiset of objects 𝑢in region 𝑖from C𝑡and the multiset of objects Vin region 𝑗from C𝑡are consumed; (b) the multiset of objects 𝑢󸀠isgeneratedinregion𝑗from configuration C𝑡+1; and (c) the multiset of objects V󸀠is generated in region 𝑖from configuration C𝑡+1.Thelengthofanevolutional symport/antiport rule 𝑟is an ordered pair of natural numbers: length(𝑟) = (length(LHS(𝑟)), length(RHS(𝑟))). Aseparationrule[𝑎]𝑖→[Γ 0]𝑖[Γ1]𝑖is enabled at a configuration C𝑡at an instant 𝑡if there is a cell 𝑖from C𝑡 which contains object 𝑎and 𝑖 =𝑖 out. By applying a separation rule to a such a cell 𝑖, (a) object 𝑎is consumed from such cell; (b) two new cells with label 𝑖are generated at configuration C𝑡+1;(c)intheoriginalcell𝑖,theobjectsfromΓ0are placed inoneofthenewcells,whiletheotherobjectsfromΓ1are placed in another one. The rules of a TESAS P system are applied in a maximally parallel manner, and we have the restriction that when a cell 𝑖is separated at one transition step, no other rules can be applied for that cell 𝑖at that step. A transition from a configuration C𝑡to another configuration C𝑡+1 is obtained by applying rules in a maximally parallel manner following the previous remarks. A computation of the system is a (finite or infinite) sequence of transitions starting from the initial configuration, where any term of the sequence other than the first is obtained from the previous configuration in one transition step. If the sequence is finite (called halting computation) then the last term of the sequence is a halting configuration, that is, a configuration where no rule is applicable to it. A computation gives a result only when an halting configuration is reached, and that result is encoded by the multiset of objects present in the output region 𝑖out. A natural framework to solve decision problems is to use recognizer P systems; one can refer to [21, 29] for further details. Definition 2. A recognizer tissue P system with evolutional symport/antiport rules and cell separation of degree 𝑞≥1is atuple Π=(Γ,Γ 0,Γ 1,E,Σ,M1,...,M𝑞,R,𝑖in,𝑖out), (2) 4Complexity where (i) the tuple (Γ,Γ0,Γ 1,E,M1,...,M𝑞,R,𝑖out)is a TESAS P system of degree 𝑞≥1,whereΓstrictly contains an (input) alphabet Σandtwodistinguishedobjectsyes, no,andM𝑖(1≤𝑖≤𝑞)aremultisetsoverΓ\Σ; (ii) 𝑖in ∈{1,...,𝑞}is the input cell and 𝑖out is the label of the environment; (iii) for each multiset 𝑚over the input alphabet Σ,any computation of the system Πwith input 𝑚starts from the configuration of the form (M1,...,M𝑖in + 𝑚,...,M𝑞;0)and always halts and either object yes or object no (but not both) must appear in the environment at the last step. It is worth pointing out that, in any recognizer TESAS P systems, all computations halt. Then, any symport rule of the type [𝑢]0[] 𝑗→[] 0[𝑢󸀠]𝑗must verify the following condition: multiset 𝑢contains some object from Γ\E. For each ordered pair of natural numbers (𝑘1,𝑘2)greater than or equal to 1, the class of recognizer TESAS P systems with cell separation and with evolutional communication rulesoflengthatmost(𝑘1,𝑘2)is denoted by TSEC(𝑘1,𝑘2). This means that the LHS (resp., RHS) of any evolutional communication rule in a system from TSEC(𝑘1,𝑘2)involves at most 𝑘1objects (resp., 𝑘2objects). Next, we define the concept of solving a problem in a uniform way and in polynomial time by a family of recognizer TESAS P systems (see [40] for details). Definition 3. Adecisionproblem𝑋=(𝐼 𝑋,𝜃𝑋)is solvable in a uniform way and in polynomial time by a family Π= (Π(𝑛))𝑛∈Nof recognizer TESAS P systems if the following conditions hold: (i) the family Πis polynomially uniform by Turing machines; (ii) there exists a polynomial encoding (cod,𝑠)of 𝐼𝑋in Π such that (a) for each instance 𝑢∈𝐼 𝑋,𝑠(𝑢)is a natural number and cod(𝑢)isaninputmultisetofthesystem Π(𝑠(𝑢)); (b) for each 𝑛∈N,𝑠−1(𝑛) is a finite set; and (c) the family Πis polynomially bounded, sound, and complete with regard to (𝑋,cod,𝑠). The set of all decision problems that can be solved by recognizer TESAS P systems with evolutional communicationrulesoflengthatmost(𝑘1,𝑘2)in a uniform way and polynomial time is denoted by PMCTSEC(𝑘1,𝑘2). 3. The Computational Complexity of Tissue P Systems with Evolutional Symport/Antiport Rules 3.1. The Limitation on the Efficiency of TSEC(2,1).In this subsection, we use tissue P systems with cell separation and evolutional communication rules of length at most (2,1) to provide a new characterization of the classical complexity class P. The proof uses a similar technique as in [32]. Firstly, some representations of TESAS P systems Π=(Γ,Γ 0,Γ 1,E,Σ, M1,...,M𝑞,R,𝑖in,𝑖out)from TSEC(2,1) aregiven.ByR𝐶 (resp., R𝑆) we denote the set of communication rules (resp., separation rules) of Π.WewillfixatotalorderinR𝐶and a total order in R𝑆. Because several cells with the same label are generated by using separation rules, in order to identify the different cells with the same label, the following recursive definition is used to modify the labels of the new generated cells: (i) We denote the label of a cell as a pair (𝑖,𝜎),where1≤ 𝑖≤𝑞and 𝜎∈{0,1}is a binary string. (ii) If a separation rule is applied to a cell with label (𝑖,𝜎), then the new created two cells will be labelled by (𝑖,𝜎0) and (𝑖,𝜎1), respectively. We mention that, for the system during any computation, we consider a lexicographical order over the set of labels of cells. Note that if communication rules occur in two cells, then the labels of these two cells do not change. Aconfigurationataninstant𝑡of a tissue P system from TSEC(2,1) is described by the multisets of objects over Γ contained in each cell and the multiset of objects over Γ\ Ein the environment. Hence, a configuration of Πcan be described as follows: {(𝑎,𝑖,𝜎)|𝑎∈Γ∪{𝜆},1≤𝑖≤𝑞,𝜎∈{0,1}∗} ∪{(𝑎,0)|𝑎∈Γ\E}.(3) Let 𝑟 = [𝑎𝑏]𝑖[] 𝑗→[] 𝑖[𝑐]𝑗,1≤𝑖,𝑗≤𝑞,bean evolutional symport rule of Πand 𝑛∈N.Wedenoteby𝑛⋅ LHS(𝑟,(𝑖,𝜎𝑖),(𝑗,𝜎𝑗))the multiset of objects (𝑎,𝑖,𝜎𝑖)𝑛(𝑏,𝑖,𝜎𝑖)𝑛 and the corresponding 𝑛⋅RHS(𝑟,(𝑖,𝜎𝑖),(𝑗,𝜎𝑗)) the multiset of objects (𝑐,𝑗,𝜎𝑗)𝑛.Inasimilarway,𝑛⋅LHS(𝑟,(𝑖,𝜎𝑖),(𝑗,𝜎𝑗)) and 𝑛⋅RHS(𝑟,(𝑖,𝜎𝑖),(𝑗,𝜎𝑗))are defined when 𝑟is of the form [𝑎]𝑖[] 𝑗→[] 𝑖[𝑐]𝑗. Let 𝑟 = [𝑎𝑏]𝑖[] 𝑗→[] 𝑖[𝜆]𝑗,1≤𝑖,𝑗≤𝑞,be an evolutional symport rule of Πand 𝑛∈N. We denote by 𝑛⋅LHS(𝑟,(𝑖,𝜎𝑖),(𝑗,𝜎𝑗)) the multiset of objects (𝑎,𝑖,𝜎𝑖)𝑛(𝑏,𝑖,𝜎𝑖)𝑛, and the corresponding 𝑛⋅RHS(𝑟,(𝑖,𝜎𝑖), (𝑗,𝜎𝑗)) is 0.Inasimilarway,𝑛⋅LHS(𝑟,(𝑖,𝜎𝑖),(𝑗,𝜎𝑗)) and 𝑛⋅RHS(𝑟,(𝑖,𝜎𝑖),(𝑗,𝜎𝑗)) are defined when 𝑟is of the form [𝑎]𝑖[] 𝑗→[] 𝑖[𝜆]𝑗. Let 𝑟 = [𝑎𝑏]0[] 𝑗→[] 0[𝑐]𝑗,1≤𝑗≤𝑞,beanevolutional symport rule of Πand 𝑛∈N. We denote by 𝑛⋅LHS(𝑟,(𝑗,𝜎𝑗),0) the multiset of objects (𝑎,0)𝑛(𝑏,0)𝑛,if 𝑎,𝑏 ∈ Γ\E; (𝑎,0)𝑛,if 𝑎∈Γ\E,𝑏∈E; (𝑏,0)𝑛,if 𝑏∈Γ\E,𝑎∈E; 0, otherwise; (4) and we denote by the corresponding 𝑛⋅RHS(𝑟,(𝑗,𝜎𝑗),0) the multiset of objects (𝑐,𝑗,𝜎𝑗)𝑛.Inasimilarway,𝑛⋅ LHS(𝑟,(𝑗,𝜎𝑗),0) and 𝑛⋅RHS(𝑟,(𝑗,𝜎𝑗),0) are defined when 𝑟is of the form [𝑎]0[] 𝑗→[] 0[𝜆]𝑗. Complexity 5 Let 𝑟 = [𝑎𝑏]0[] 𝑗→[] 0[𝜆]𝑗,1≤𝑗≤𝑞,beanevolutional symport rule of Πand 𝑛∈N. We denote by 𝑛⋅LHS(𝑟,(𝑗,𝜎𝑗),0) the multiset of objects (𝑎,0)𝑛(𝑏,0)𝑛,if 𝑎,𝑏 ∈ Γ\E; (𝑎,0)𝑛,if 𝑎∈Γ\E,𝑏∈E; (𝑏,0)𝑛,if 𝑏∈Γ\E,𝑎∈E; 0, otherwise. (5) The corresponding 𝑛⋅RHS(𝑟,(𝑗,𝜎𝑗),0)is 0.Inasimilarway, 𝑛⋅LHS(𝑟,(𝑗,𝜎𝑗),0)and 𝑛⋅RHS(𝑟,(𝑗,𝜎𝑗),0)are defined when 𝑟is of the form [𝑎]0[] 𝑗→[] 0[𝜆]𝑗. Let 𝑟=[𝑎] 𝑖[𝑏]𝑗→[𝑐] 𝑖[𝜆]𝑗,1≤𝑖,𝑗≤𝑞,be an evolutional antiport rule of Πand 𝑛∈N. We denote by 𝑛⋅LHS(𝑟,(𝑖,𝜎𝑖),(𝑗,𝜎𝑗)) the multiset of objects (𝑎,𝑖,𝜎𝑖)𝑛(𝑏,𝑗,𝜎𝑗)𝑛and the corresponding 𝑛⋅RHS(𝑟,(𝑖,𝜎𝑖), (𝑗,𝜎𝑗)) the multiset of objects (𝑐,𝑖,𝜎𝑖)𝑛.Inasimilarway,𝑛⋅ LHS(𝑟,(𝑖,𝜎𝑖),(𝑗,𝜎𝑗))and 𝑛⋅RHS(𝑟,(𝑖,𝜎𝑖),(𝑗,𝜎𝑗))are defined when 𝑟is of the form [𝑎]𝑖[𝑏]𝑗→[𝜆] 𝑖[𝑐]𝑗. Let 𝑟=[𝑎] 𝑖[𝑏]𝑗→[𝜆] 𝑖[𝜆]𝑗,1≤𝑖,𝑗≤𝑞,bean evolutional antiport rule of Πand 𝑛∈N. We denote by 𝑛⋅LHS(𝑟,(𝑖,𝜎𝑖),(𝑗,𝜎𝑗)) the multiset of objects (𝑎,𝑖,𝜎𝑖)𝑛(𝑏,𝑗,𝜎𝑗)𝑛, and the corresponding 𝑛⋅RHS(𝑟,(𝑖,𝜎𝑖), (𝑗,𝜎𝑗))is 0. Let 𝑟=[𝑎] 0[𝑏]𝑗→[𝑐] 0[𝜆]𝑗,1≤𝑗≤𝑞,beanevolutional antiport rule of Πand 𝑛∈N.Wedenoteby𝑛⋅LHS(𝑟,(𝑗,𝜎𝑗),0) the multiset of objects (𝑎,0)𝑛(𝑏,𝑗)𝑛,if 𝑎∈Γ\E; (𝑏,𝑗)𝑛,otherwise;(6) and we denote by the corresponding 𝑛⋅RHS(𝑟,(𝑗,𝜎𝑗),0)the multiset of objects (𝑐,0)𝑛,if 𝑐∈Γ\E; 0, otherwise.(7) Let 𝑟=[𝑎] 0[𝑏]𝑗→[𝜆] 0[𝑐]𝑗,1≤𝑗≤𝑞,beanevolutional antiport rule of Πand 𝑛∈N.Wedenoteby𝑛⋅LHS(𝑟,(𝑗,𝜎𝑗),0) the multiset of objects (𝑎,0)𝑛(𝑏,𝑗)𝑛,if 𝑎∈Γ\E; (𝑏,𝑗)𝑛,otherwise;(8) and we denote by the corresponding 𝑛⋅RHS(𝑟,(𝑗,𝜎𝑗),0)the multiset of objects (𝑐,𝑗,𝜎𝑗)𝑛. Let 𝑟=[𝑎] 0[𝑏]𝑗→[𝜆] 0[𝜆]𝑗,1≤𝑗≤𝑞,beanevolutional antiport rule of Πand 𝑛∈N.Wedenoteby𝑛⋅LHS(𝑟,(𝑗,𝜎𝑗),0) the multiset of objects (𝑎,0)𝑛(𝑏,𝑗)𝑛,if 𝑎∈Γ\E; (𝑏,𝑗)𝑛,otherwise.(9) The corresponding 𝑛⋅RHS(𝑟,(𝑗,𝜎𝑗),0)is 0. If C𝑡is a configuration of Π, then the multiset obtained by replacing in C𝑡every occurrence of (𝑥,𝑖,𝜎)by (𝑥,𝑖,𝜎󸀠)is denoted by C𝑡+{(𝑥,𝑖,𝜎)/𝜎󸀠}. Moreover, we denote by C𝑡+𝑚 (resp., C𝑡\𝑚)amultiset𝑚of labelled objects added to (resp., removed from) the configuration C𝑡. Next,weshowthatTESASPsystemsfromTSEC(2,1)can only solve tractable problems. If C={C𝑡}𝑡<𝑟+1 of Π(𝑟∈N) is a halting computation, then we denote by |C|=𝑟the length of C.Foreach𝑖(1≤𝑖≤ 𝑞),themultisetofobjectsoverΓcontained in all cells labelled by 𝑖at configuration C𝑡is denoted by C𝑡(𝑖). We denote by C𝑡(0) the multiset of objects over Γ\Econtained in the environment at configuration C𝑡.Finally,thefinitemultiset C𝑡(0)+C𝑡(1)+⋅⋅⋅+C𝑡(𝑞)is denoted by C∗ 𝑡. Lemma 4. Let Π=(Γ,Γ 0,Γ 1,E,Σ,M1,...,M𝑞,R,𝑖𝑖𝑛,𝑖𝑜𝑢𝑡) be a recognizer tissue P system of degree 𝑞≥1from TSEC(2,1). Let 𝑀=|M1+⋅⋅⋅+M𝑞|and let C={C0,...,C𝑟}be a computation of Π.Then,onehas (1) |C∗ 0|=𝑀,andforeach𝑡,0≤𝑡<𝑟,|C∗ 𝑡+1|≤|C∗ 𝑡|; (2) for each 𝑡,0≤𝑡≤𝑟,|C∗ 𝑡|≤𝑀; (3) the number of created cells along the computation C by the application of cell separation rules is bounded by 2𝑀. Proof. (1) Let us notice that 󵄨 󵄨 󵄨 󵄨C∗ 0󵄨 󵄨 󵄨 󵄨=󵄨 󵄨 󵄨 󵄨C0(0)+C0(1)+⋅⋅⋅+C0(𝑞)󵄨 󵄨 󵄨 󵄨 =󵄨 󵄨 󵄨 󵄨 󵄨M1+⋅⋅⋅+M𝑞󵄨 󵄨 󵄨 󵄨 󵄨=𝑀. (10) Let Πbe a recognizer tissue P system from TSEC(2,1) and let Rbe the set of rules associated with Π,whichcontains the following types of evolutional communication rules: (a) [𝑎𝑏]𝑖[] 𝑗→[] 𝑖[𝑐]𝑗,(𝑖 = 0 ∧ {𝑎,𝑏} ⊆ E)or(𝑖 =0∧ {𝑎,𝑏} ⊆ Γ); (b) [𝑎𝑏]𝑖[] 𝑗→[] 𝑖[𝜆]𝑗,(𝑖 = 0 ∧ {𝑎,𝑏} ⊆ E)or(𝑖 =0∧ {𝑎,𝑏} ⊆ Γ); (c) [𝑎]𝑖[𝑏]𝑗→[𝑐] 𝑖[𝜆]𝑗,{𝑎,𝑏} ⊆ Γ; (d) [𝑎]𝑖[𝑏]𝑗→[𝜆] 𝑖[𝑐]𝑗,{𝑎,𝑏} ⊆ Γ; (e) [𝑎]𝑖[𝑏]𝑗→[𝜆] 𝑖[𝜆]𝑗,{𝑎,𝑏} ⊆ Γ; (f) [𝑎]𝑖[] 𝑗→[] 𝑖[𝑏]𝑗,(𝑖=0∧𝑎∈Γ\E)or(𝑖 =0∧𝑎∈Γ); (g) [𝑎]𝑖[] 𝑗→[] 𝑖[𝜆]𝑗,(𝑖=0∧𝑎∈Γ\E)or(𝑖 =0∧𝑎∈Γ). For each 𝑡,0≤𝑡<𝑟, in the transition from configuration C𝑡 to configuration C𝑡+1, by using any rules of types from (a) to (g), at least one object from C𝑡is consumed and at most one object is produced in C𝑡+1. Hence, in any transition step the number of objects in the system is not increased. (2) By induction on 𝑡,letusstartanalyzingthebasiccase 𝑡=0.Theresultistrivialbecauseof|C∗ 0|=𝑀.Byinduction hypothesis, let us suppose the result holds for 𝑡,0≤𝑡<𝑟. Then, 󵄨 󵄨 󵄨 󵄨C∗ 𝑡+1󵄨 󵄨 󵄨 󵄨(1) ≤󵄨 󵄨 󵄨 󵄨C∗ 𝑡󵄨 󵄨 󵄨 󵄨 h.i. ≤𝑀. (11) Hence,theresultisalsotruefor𝑡+1. 6Complexity Input:A P system Πfrom TSEC(2,1) and an input multiset 𝑚 Initialization phase:C0is the initial configuration of Π+𝑚 𝑡←0 while C𝑡is a non-halting configuration do Selection phase:Input C𝑡,Output (C󸀠 𝑡,𝐴) Execution phase:Input (C󸀠 𝑡,𝐴), Output C𝑡+1 𝑡←𝑡+1 end while Output:Yes if Π+𝑚has an accepting computation, No otherwise Pseudocode 1 (3) According to the fact that the application of a cell separation rule consumes an object and produces two new cells, result (3) can be obtained from (2) easily. Next, a deterministic algorithm Aworking in polynomial time is presented, which receives as input a P system Πfrom TSEC(2,1)and an input multiset 𝑚of Π,insuchmannerthat algorithm Areproduces the behaviour of a computation of Π+𝑚.IfthesystemΠis confluent, then the algorithm Awill provide the same answer of Π.WegivePseudocode1ofthe algorithm Ato describe the simulation process. The algorithm Areceives a recognizer tissue P system Π=(Γ,Γ 0,Γ 1,E,Σ,M1,...,M𝑞,R,𝑖in,𝑖out)(12) from TSEC(2,1) and an input multiset 𝑚.Let𝑀=|M1+ ⋅⋅⋅+M𝑞|. Let any computation of Πperform at most 𝑝(𝑝 is a natural number) transition steps. Hence, from Lemma 4, the number of cells in the system along any computation is bounded by 2𝑀+𝑞. A transition of a recognizer tissue P system Π+𝑚 is performed in two phases: selection phase and execution phase (see Algorithms 1 and 2). For the detailed information of a transition of such P system, one can refer to [32]. It is easy to check that Algorithm 1 is deterministic and the running time of this algorithm is polynomial in the size of Πbecause the number of cycles of the first main loop for is of order 𝑂(|R|⋅𝑀2⋅𝑞2); the number of cycles of the second main loop for is of order 𝑂(|R|⋅𝑀⋅𝑞);andthenumberof cycles of the third main loop for is of order 𝑂(|R|⋅𝑀⋅𝑞⋅|Γ|). Algorithm 2 is deterministic and the running time of this algorithm is polynomial in the size of Πbecause the number of cycles of the first main loop for is of order 𝑂(|R|⋅𝑀2⋅𝑞2); thenumberofcyclesofthesecondmainloopfor is of order 𝑂(|R|⋅𝑀⋅𝑞);andthenumberofcyclesofthethirdmain loop for is of order 𝑂(|R|⋅𝑀⋅𝑞⋅|Γ|). Theorem 5. One has P=PMCTSEC(2,1). Proof. BecausePMCTSEC(2,1) is closed under polynomial time reduction and nonempty, hence P⊆PMCTSEC(2,1).Inwhat follows, we show that CTSEC(2,1) ⊆P.Let𝑋∈PMCTSEC(2,1) and let Π={Π(𝑛)|𝑛∈N}be a family of recognizer tissue P systems from TSEC(2,1)solving 𝑋according to Definition 3. Let (cod,𝑠)be a polynomial encoding associated with that solution. If 𝑢∈𝐼 𝑋is an instance of the problem 𝑋,then𝑢will be processed by the system Π(𝑠(𝑢))+cod(𝑢). We consider the deterministic algorithm A󸀠as shown in Algorithm 3. The algorithm A󸀠receives an instance 𝑢of the decision problem 𝑋=(𝐼 𝑋,𝜃𝑋), working in a polynomial time. The following three assertions are equivalent: (i) 𝜃𝑋(𝑢) = 1;thatis,theanswerofproblem𝑋to instance 𝑢is affirmative. (ii) Every computation of Π(𝑠(𝑢))+cod(𝑢)is an accepting computation. (iii) The output of the algorithm A󸀠with input 𝑢is Yes. Hence, 𝑋∈P. Corollary 6. For each 𝑛∈N,𝑛≥1,onehasPMCTSEC(𝑛,1) = P. Proof. Indeed, it suffices to notice that, at any transition step, the application of each rule consumes at least one object from Γ\Eand produces at most one object from Γ.Thus,along any computation of the system, the total number in it is not increased. Theorem 7. For each 𝑛∈N,𝑛≥1,onehasPMCTSEC(1,𝑛) =P. Proof. In[31],itwasshownthattheclassofdecisionproblems solvable in polynomial time by means of families of tissue P systems with cell division and symport rules with length 1isequaltoclassP.Bearinginmindthatsystemsfrom TSEC(1,𝑛) are noncooperative ones, the dependency graph techniqueusedinthecitedpapercanbeusedtoobtainthe result, in a similar way. 3.2. An Efficient Solution to the SAT Problem by P Systems in TSEC(3,2).The SAT problem is a well-known NP-complete problem; here we give an efficient solution to the SAT problem by a family of tissue P systems with evolutional communication rules of length at most (3,2). Theorem 8. One has SAT ∈PMCTSEC(3,2). Proof. We provide a polynomial time uniform solution to the SAT problem [41] by a family of recognizer tissue P systems Π={Π(𝑡)|𝑡∈N}from TSEC(3,2). Each system Π(𝑡) (𝑡= ⟨𝑛,𝑚⟩ = ((𝑛+𝑚)(𝑛+𝑚+1)/2)+𝑛)canprocessallBoolean formula 𝜑in conjunctive normal form with 𝑛variables and 𝑚 clauses. Complexity 7 Input:A configuration C𝑡of Π+𝑚at instant 𝑡 C󸀠 𝑡←C𝑡;𝐴←0;𝐵←0 for 𝑟=[𝑢] 𝑖[V]𝑗→[V󸀠]𝑖[𝑢󸀠]𝑗∈R𝐶, according to the order chosen do for each pair of cells (𝑖,𝜎𝑖),(𝑗,𝜎𝑗)of C󸀠 𝑡according to the lexicographical order do 𝑛𝑟←maximum number of times that 𝑟is applicable to (𝑖,𝜎𝑖), (𝑗,𝜎𝑗)if 𝑛𝑟>0then C󸀠 𝑡←C󸀠 𝑡−𝑛𝑟⋅LHS(𝑟,(𝑖,𝜎𝑖),(𝑗,𝜎𝑗)) 𝐴 ← 𝐴∪{(𝑟,𝑛𝑟,(𝑖,𝜎𝑖),(𝑗,𝜎𝑗))} 𝐵 ← 𝐵∪{(𝑖,𝜎𝑖),(𝑗,𝜎𝑗)} end if end for end for for 𝑟=[𝑢] 𝑖[V]0→[V󸀠]𝑖[𝑢󸀠]0∈R𝐶according to the order chosen do for each cell (𝑖,𝜎𝑖)of C󸀠 𝑡according to the lexicographical order do 𝑛𝑟←maximum number of times that 𝑟is applicable to (𝑖,𝜎𝑖) if 𝑛𝑟>0then C󸀠 𝑡←C󸀠 𝑡−𝑛𝑟⋅LHS(𝑟,(𝑖,𝜎𝑖),0) 𝐴 ← 𝐴∪{(𝑟,𝑛𝑟,(𝑖,𝜎𝑖),0)} 𝐵 ← 𝐵∪{(𝑖,𝜎𝑖)} end if end for end for for 𝑟=[𝑎] 𝑖→[Γ 0]𝑖[Γ1]𝑖∈R𝑆according to the order chosen do for each (𝑎,𝑖,𝜎𝑖)∈C󸀠 𝑡according to the lexicographical order,and such that (𝑖,𝜎𝑖)∉𝐵do C󸀠 𝑡←C󸀠 𝑡\{(𝑎,𝑖,𝜎𝑖)} 𝐴←𝐴∪{(𝑟,1,(𝑖,𝜎𝑖))} end for end for Algorithm 1: Selection phase. For each 𝑛,𝑚 ∈ N,weconsidertherecognizertissueP system Π(⟨𝑛,𝑚⟩) = (Γ,Γ0,Γ 1,E,Σ,M1,M2,M3,R,𝑖in,𝑖out), (13) where Γ=Σ∪E∪{𝐴𝑖,𝐴󸀠 𝑖,𝐴𝑖,𝐴󸀠 𝑖, 𝐴𝑖, 𝐴󸀠 𝑖,𝐵𝑖,𝐵󸀠 𝑖,𝐵𝑖,𝐵󸀠 𝑖, 𝐵𝑖, 𝐵󸀠 𝑖,𝐶𝑖, 𝑇𝑖,𝑇𝑖,𝑇󸀠 𝑖,𝐹 𝑖,𝐹𝑖,𝐹󸀠 𝑖,𝑎𝑖,𝑎󸀠 𝑖,𝑏 𝑖,𝑏󸀠 𝑖,𝑐 𝑖,𝑡𝑖,𝑓 𝑖,ℎ𝑖,𝑦𝑖,𝑠𝑖,V𝑖,𝑤𝑖,𝑧𝑖|1 ≤𝑖≤𝑛}∪{ 𝐷𝑖,𝑗,𝑞𝑖,𝑗,𝑟𝑖,𝑗,𝑢𝑖,𝑗 |1≤𝑖,𝑗≤𝑛} ∪{𝐷𝑖,𝑛+1 |1≤𝑖≤𝑛+1}∪{𝑔 𝑖,𝑗,𝑘,𝑔𝑖,𝑗,𝑘 |1≤𝑖,𝑘 ≤𝑛,1≤𝑗≤𝑚}∪{𝐸 𝑖,𝑗,𝐸𝑖,𝑗,𝑒𝑖,𝑗,𝑒𝑖,𝑗,𝑙𝑗,𝑖 |1≤𝑖≤𝑛, 1≤𝑗≤𝑚}∪{𝑙 𝑗,𝑙𝑗,𝑙𝑗,0,𝐸𝑗|1≤𝑗≤𝑚}∪{𝐴𝑛+1, 𝐴𝑛+1,𝐴󸀠 𝑛+1,𝐵𝑛+1,𝐵𝑛+1,𝐵󸀠 𝑛+1,𝐶𝑛+1,𝐸𝑚+1,𝑆,𝑝,yes,no}, Γ1={𝑇 󸀠 𝑖,𝐹󸀠 𝑖|1≤𝑖≤𝑛}∪{𝐴 󸀠 𝑖,𝐵󸀠 𝑖|2≤𝑖≤𝑛+1}, Γ0=Γ\Γ 1, Σ={𝑥 𝑖,𝑗,𝑥𝑖,𝑗 |1≤𝑖≤𝑛,1≤𝑗≤𝑚}, E={ 𝐴𝑖, 𝐵𝑖,𝑎𝑖, 𝑎𝑖,𝑏𝑖, 𝑏𝑖,𝑐𝑖, 𝑐𝑖, 𝑑𝑖,𝑓𝑖, 𝑠𝑖,𝑡𝑖,V𝑖, V𝑖,𝑛+1, 𝑤𝑖,𝑦𝑖, 𝑦𝑖,  𝑧𝑖|1≤𝑖≤𝑛}∪{𝑟𝑖,𝑗, 𝑟𝑖,𝑗, 𝑢𝑖,𝑗, V𝑖,𝑗 |1≤𝑖,𝑗≤𝑛} ∪{𝑔󸀠 𝑖,𝑗,𝑘,𝑔󸀠 𝑖,𝑗,𝑘 |1≤𝑖≤𝑛,1≤𝑗≤𝑚,0≤𝑘≤𝑛} ∪{𝑙𝑗,𝑘 |1≤𝑗≤𝑚,0≤𝑘≤𝑛}∪{𝛼 𝑖|0≤𝑖≤4𝑛 +3𝑚+4}∪{𝐸0}, M1={𝐴1,𝐵1}, M2={𝐴1,𝐵1,𝐶1,𝐷1,1}, M3={𝑙 1,0,...,𝑙𝑚,0,𝛼0,𝑝}, 𝑖in =3is the input cell, 𝑖out =0is the output region, (14) 8Complexity Input:The output (C󸀠 𝑡,𝐴)of the selection phase for each (𝑟,𝑛𝑟,(𝑖,𝜎𝑖),(𝑗,𝜎𝑗)) ∈ 𝐴 do C󸀠 𝑡←C󸀠 𝑡+𝑛𝑟⋅RHS(𝑟,(𝑖,𝜎𝑖),(𝑗,𝜎𝑗)) end for for each (𝑟,𝑛𝑟,(𝑖,𝜎𝑖),0) ∈ 𝐴 do C󸀠 𝑡←C󸀠 𝑡+𝑛𝑟⋅RHS(𝑟,(𝑖,𝜎𝑖),0) end for for each (𝑟,1,(𝑖,𝜎𝑖)) ∈ 𝐴 do C󸀠 𝑡←C󸀠 𝑡+{(𝜆,𝑖,𝜎𝑖)/𝜎𝑖0} C󸀠 𝑡←C󸀠 𝑡+{(𝜆,𝑖,𝜎𝑖1)} for each (𝑥,𝑖,𝜎𝑖)∈C󸀠 𝑡according to the lexicographical order do if 𝑥∈Γ 0then C󸀠 𝑡←C󸀠 𝑡+{(𝑥,𝑖,𝜎𝑖)/𝜎𝑖0} else C󸀠 𝑡←C󸀠 𝑡+{(𝑥,𝑖,𝜎𝑖)/𝜎𝑖1} end if end for end for C𝑡+1 ←C󸀠 𝑡 Algorithm 2: Execution phase. Input:an instance 𝑢of the problem 𝑋 Construct the system Π(𝑠(𝑢))+cod(𝑢) Run algorithm Awith input Π(𝑠(𝑢))+cod(𝑢) Output:Yes if Π(𝑠(𝑢))+cod(𝑢) has an accepting computation No otherwise Algorithm 3 and the set Rof rules consists of the following rules: 𝑟1,𝑖 ≡[𝐴𝑖]1[𝐴𝑖]2󳨀→ [𝐴𝑖]1[ 𝐴𝑖]2, 1≤𝑖≤𝑛, 𝑟2,𝑖 ≡[𝐴 󸀠 𝑖]1[𝐴𝑖]2󳨀→ [𝐴󸀠 𝑖]1[ 𝐴󸀠 𝑖]2, 1≤𝑖≤𝑛, 𝑟3,𝑖 ≡[𝐵 𝑖]1[𝐵𝑖]2󳨀→ [𝐵𝑖]1[ 𝐵𝑖]2, 1≤𝑖≤𝑛, 𝑟4,𝑖 ≡[𝐵 󸀠 𝑖]1[𝐵𝑖]2󳨀→ [𝐵󸀠 𝑖]1[ 𝐵󸀠 𝑖]2, 1≤𝑖≤𝑛, 𝑟5,𝑖 ≡[𝐶𝑖]2[V𝑖]0󳨀→ [V𝑖]2[] 0, 1≤𝑖≤𝑛, 𝑟6,𝑖,𝑗 ≡[𝐷𝑖,𝑗]2[ V𝑖,𝑗]0󳨀→ [𝑞𝑖,𝑗]2[] 0,1≤𝑖,𝑗≤𝑛, 𝑟7,𝑖 ≡[𝑇 𝑖]1[𝑡𝑖]2󳨀→ [𝑡𝑖]1[] 2, 1≤𝑖≤𝑛, 𝑟8,𝑖 ≡[𝑇 󸀠 𝑖]1[𝑡𝑖]2󳨀→ [𝑡𝑖]1[] 2,1≤𝑖≤𝑛, 𝑟9,𝑖 ≡[𝐹 𝑖]1[𝑓𝑖]2󳨀→ [𝑓𝑖]1[] 2, 1≤𝑖≤𝑛, 𝑟10,𝑖 ≡[𝐹 󸀠 𝑖]1[𝑓𝑖]2󳨀→ [𝑓𝑖]1[] 2, 1≤𝑖≤𝑛, 𝑟11,𝑖 ≡[𝐴𝑖]1[ 𝐴𝑖]0󳨀→ [𝑎𝑖𝑎󸀠 𝑖]1[] 0,1≤𝑖≤𝑛, 𝑟12,𝑖 ≡[𝐴󸀠 𝑖]1[ 𝐴𝑖]0󳨀→ [𝑎𝑖𝑎󸀠 𝑖]1[] 0, 2≤𝑖≤𝑛, 𝑟13,𝑖 ≡[𝐵𝑖]1[ 𝐵𝑖]0󳨀→ [𝑏𝑖𝑏󸀠 𝑖]1[] 0, 1≤𝑖≤𝑛, 𝑟14,𝑖 ≡[𝐵󸀠 𝑖]1[ 𝐵𝑖]0󳨀→ [𝑏𝑖𝑏󸀠 𝑖]1[] 0, 2≤𝑖≤𝑛, 𝑟15,𝑖 ≡[ 𝐴𝑖]2[ 𝐴𝑖]0󳨀→ [𝐴 𝑖]2[] 0, 1≤𝑖≤𝑛, 𝑟16,𝑖 ≡[ 𝐴󸀠 𝑖]2[ 𝐴𝑖]0󳨀→ [𝐴󸀠 𝑖]2[] 0, 2≤𝑖≤𝑛, 𝑟17,𝑖 ≡[ 𝐵𝑖]2[ 𝐵𝑖]0󳨀→ [𝐵𝑖]2[] 0, 1≤𝑖≤𝑛, 𝑟18,𝑖 ≡[ 𝐵󸀠 𝑖]2[ 𝐵𝑖]0󳨀→ [𝐵󸀠 𝑖]2[] 0, 2≤𝑖≤𝑛, 𝑟19,𝑖 ≡[V𝑖]2[𝑦𝑖]0󳨀→ [𝑦2 𝑖]2[] 0,1≤𝑖≤𝑛, 𝑟20 ≡[𝑞 1,1]2[𝑟1,1]0󳨀→ [𝑟1,1]2[] 0, 𝑟21,𝑖,𝑗 ≡[𝑞 𝑖,𝑗]2[𝑟𝑖,𝑗]0󳨀→ [𝑟2 𝑖,𝑗]2[] 0, 1≤𝑖≤𝑛,2≤𝑗≤𝑛, 𝑟22,𝑖 ≡[𝑡 𝑖]1[𝑡𝑖]0󳨀→ [𝑇𝑖𝑇󸀠 𝑖]1[] 0, 1≤𝑖≤𝑛, 𝑟23,𝑖 ≡[𝑓 𝑖]1[𝑓𝑖]0󳨀→ [𝐹𝑖𝐹󸀠 𝑖]1[] 0,1≤𝑖≤𝑛, 𝑟24,𝑖 ≡[𝐴𝑖]2[𝑐𝑖]0󳨀→ [𝑐𝑖]2[] 0, 1≤𝑖≤𝑛, 𝑟25,𝑖 ≡[𝐴 󸀠 𝑖]2[ 𝑐𝑖]0󳨀→ [𝑐𝑖]2[] 0, 2≤𝑖≤𝑛, Complexity 9 𝑟26,𝑖 ≡[𝐵 𝑖]2[𝑐𝑖]0󳨀→ [𝑐𝑖]2[] 0, 1≤𝑖≤𝑛, 𝑟27,𝑖 ≡[𝐵 󸀠 𝑖]2[ 𝑐𝑖]0󳨀→ [𝑐𝑖]2[] 0, 2≤𝑖≤𝑛, 𝑟28,𝑖 ≡[𝑎 𝑖]1[𝑎𝑖]0󳨀→ [𝑇𝑖𝐴𝑖+1]1[] 0,1≤𝑖≤𝑛, 𝑟29,𝑖 ≡[𝑎 󸀠 𝑖]1[ 𝑎𝑖]0󳨀→ [𝐹󸀠 𝑖𝐴󸀠 𝑖+1]1[] 0, 1≤𝑖≤𝑛, 𝑟30,𝑖 ≡[𝑏 𝑖]1[𝑏𝑖]0󳨀→ [𝐵𝑖+1𝑆]1[] 0,1≤𝑖≤𝑛, 𝑟31,𝑖 ≡[𝑏 󸀠 𝑖]1[ 𝑏𝑖]0󳨀→ [𝐵󸀠 𝑖+1]1[] 0,1≤𝑖≤𝑛, 𝑟32,𝑖 ≡[𝑦 𝑖]2[ 𝑦𝑖]0󳨀→ [𝑧𝑖𝑤𝑖]2[] 0,1≤𝑖≤𝑛, 𝑟33,𝑖,𝑗 ≡[𝑟 𝑖,𝑗]2[ 𝑟𝑖,𝑗]0󳨀→ [𝑠𝑖𝑢𝑖,𝑗]2[] 0, 1≤𝑖,𝑗≤𝑛, 𝑟34,𝑖 ≡[𝑤 𝑖]2[ 𝑤𝑖]0󳨀→ [𝐴𝑖+1]2[] 0, 1≤𝑖≤𝑛, 𝑟35,𝑖 ≡[𝑐 𝑖]2[ 𝑑𝑖]0󳨀→ [𝐵𝑖+1]2[] 0, 1≤𝑖≤𝑛, 𝑟36,𝑖 ≡[𝑧 𝑖]2[ 𝑧𝑖]0󳨀→ [𝐶𝑖+1]2[] 0,1≤𝑖≤𝑛, 𝑟37,𝑖 ≡[𝑠 𝑖]2[ 𝑠𝑖]0󳨀→ [𝑡𝑖𝑓𝑖]2[] 0,1≤𝑖≤𝑛, 𝑟38,𝑗 ≡[𝑢 1,𝑗]2[ 𝑢1,𝑗]0󳨀→ [𝐷1,𝑗+1𝐷2,𝑗+1]2[] 0, 1≤𝑗≤𝑛, 𝑟39,𝑖,𝑗 ≡[𝑢 𝑖,𝑗]2[ 𝑢𝑖,𝑗]0󳨀→ [𝐷𝑖+1,𝑗+1]2[] 0, 2≤𝑖,𝑗≤𝑛, 𝑟40 ≡[𝑆]1󳨀→ [Γ0]1[Γ1]1, 𝑟41,𝑖 ≡[𝐷𝑖,𝑛+1]2[ V𝑖,𝑛+1]0󳨀→ [ℎ2 𝑖]2[] 0, 1≤𝑖≤𝑛, 𝑟42 ≡[𝐴𝑛+1]1[𝐴𝑛+1]2󳨀→ [𝐸1]1[] 2, 𝑟43 ≡[𝐴 󸀠 𝑛+1]1[𝐵𝑛+1]2󳨀→ [𝐸1]1[] 2, 𝑟44,𝑖 ≡[𝑇 𝑖𝑇󸀠 𝑖]1[ℎ𝑖]2󳨀→ [𝑇𝑖]1[] 2, 1≤𝑖≤𝑛, 𝑟45,𝑖 ≡[𝐹 𝑖𝐹󸀠 𝑖]1[ℎ𝑖]2󳨀→ [𝐹𝑖]1[] 2, 1≤𝑖≤𝑛, 𝑟46,𝑖,𝑗 ≡[𝑥 𝑖,𝑗]3[𝑔󸀠 𝑖,𝑗,0]0󳨀→ [𝑔2 𝑖,𝑗,1]3[] 0, 1≤𝑖≤𝑛,1≤𝑗≤𝑚, 𝑟47,𝑖,𝑗 ≡[𝑥𝑖,𝑗]3[𝑔󸀠 𝑖,𝑗,0]0󳨀→ [𝑔2 𝑖,𝑗,1]3[] 0, 1≤𝑖≤𝑛,1≤𝑗≤𝑚, 𝑟48,𝑖,𝑗,𝑘 ≡[𝑔 𝑖,𝑗,𝑘]3[𝑔󸀠 𝑖,𝑗,𝑘]0󳨀→ [𝑔2 𝑖,𝑗,𝑘+1]3[] 0, 1≤𝑖≤𝑛,1≤𝑗≤𝑚,1≤𝑘≤𝑛−1, 𝑟49,𝑖,𝑗,𝑘 ≡[𝑔𝑖,𝑗,𝑘]3[𝑔󸀠 𝑖,𝑗,𝑘]0󳨀→ [𝑔2 𝑖,𝑗,𝑘+1]3[] 0, 1≤𝑖≤𝑛,1≤𝑗≤𝑚,1≤𝑘≤𝑛−1, 𝑟50,𝑖,𝑗 ≡[𝑔 𝑖,𝑗,𝑛]3[𝑔󸀠 𝑖,𝑗,𝑛]0󳨀→ [𝑒𝑖,𝑗]3[] 0, 1≤𝑖≤𝑛,1≤𝑗≤𝑚, 𝑟51,𝑖,𝑗 ≡[𝑔𝑖,𝑗,𝑛]3[𝑔󸀠 𝑖,𝑗,𝑛]0󳨀→ [𝑒𝑖,𝑗]3[] 0, 1≤𝑖≤𝑛,1≤𝑗≤𝑚, 𝑟52,𝑗,𝑘 ≡[𝑙 𝑗,𝑘]3[𝑙𝑗,𝑘]0󳨀→ [𝑙2 𝑗,𝑘+1]3[] 0, 1≤𝑗≤𝑚,0≤𝑘≤𝑛−1, 𝑟53,𝑗 ≡[𝑙 𝑗,𝑛]3[𝑙𝑗,𝑛]0󳨀→ [𝑙𝑗]3[] 0, 1≤𝑗≤𝑚, 𝑟54,𝑖,𝑗 ≡[𝑇𝑖𝐸𝑗]1[𝑒𝑖,𝑗]3󳨀→ [𝐸𝑖,𝑗]1[] 3, 1≤𝑖≤𝑛,1≤𝑗≤𝑚, 𝑟55,𝑖,𝑗 ≡[𝐹𝑖𝐸𝑗]1[𝑒𝑖,𝑗]3󳨀→ [𝐸𝑖,𝑗]1[] 3, 1≤𝑖≤𝑛,1≤𝑗≤𝑚, 𝑟56,𝑖,𝑗 ≡[𝐸 𝑖,𝑗]1[𝑙𝑗]3󳨀→ [𝑙𝑖,𝑗]1[𝐸𝑖,𝑗]3, 1≤𝑖≤𝑛,1≤𝑗≤𝑚, 𝑟57,𝑖,𝑗 ≡[𝐸𝑖,𝑗]1[𝑙𝑗]3󳨀→ [𝑙𝑖,𝑗]1[𝐸𝑖,𝑗]3, 1≤𝑖≤𝑛,1≤𝑗≤𝑚, 𝑟58,𝑖,𝑗 ≡[𝑙 𝑖,𝑗]1[𝐸𝑖,𝑗]3󳨀→ [𝑇𝑖𝐸𝑗+1]1[] 3, 1≤𝑖≤𝑛,1≤𝑗≤𝑚, 𝑟59,𝑖,𝑗 ≡[𝑙𝑖,𝑗]1[𝐸𝑖,𝑗]3󳨀→ [𝐹𝑖𝐸𝑗+1]1[] 3, 1≤𝑖≤𝑛,1≤𝑗≤𝑚, 𝑟60,𝑖 ≡[𝛼 𝑖]3[𝛼𝑖]0󳨀→ [𝛼𝑖+1]3[] 0, 0 ≤ 𝑖 ≤ 4𝑛+3𝑚+3, 𝑟61 ≡[𝐸 𝑚+1]1[𝑝]3󳨀→ [] 1[yes]3, 𝑟62 ≡[yes]3[] 0󳨀→ [] 3[yes]0, 𝑟63 ≡[𝛼 4𝑛+3𝑚+4𝑝]3[] 0󳨀→ [] 3[no]0. (15) We consider a propositional formula 𝜑=𝐶 1∧⋅⋅⋅∧𝐶𝑚, which contains 𝑚(𝑚≥1)clauses,𝐶𝑖=𝑦 𝑖,1 ∨⋅⋅⋅∨𝑦𝑖,𝑝𝑖,for 𝑝𝑖≥1,and𝑦𝑖,𝑗 ∈{𝑥 𝑘,¬𝑥𝑘|1≤𝑘≤𝑛},for1≤𝑖≤𝑚, 1≤𝑗≤𝑝 𝑖. Let (cod,𝑠)be a polynomial encoding of instances from SAT in Π,where𝑠(𝜑) = ⟨𝑛,𝑚⟩ and cod(𝜑) = {𝑥𝑖,𝑗 |𝑥 𝑖∈ 𝐶𝑗}∪{𝑥𝑖,𝑗 |¬𝑥 𝑖∈𝐶 𝑗}.Sothepropositionalformula𝜑will be processed by the system Π(𝑠(𝜑))+cod(𝜑). An instance of the SAT problem is solved by the system Π(𝑠(𝜑)) + cod(𝜑),whichcanbeseparatedintothreephases: generation phase, checking phase, and output phase. 16 Complexity of the paper are the following: (a) only problems in class PcanbeefficientlysolvedbymeansoffamiliesoftissueP systems with cell separation and evolutional communication rules of length at most (𝑛,1)(or rules of length at most (1,𝑛)), for each natural number 𝑛≥1;(b)computationallyhard problemscanbesolvedinpolynomialtimebyrecognizer TESAS P systems when using evolutional communication rules of length at most (𝑛,2),foreachnaturalnumber 𝑛≥3;and(c)anewMeCoSim based simulator has been designed to check the correctness of the solution to the SAT problem. As future works, we propose the following: (1) In Section 3, a polynomial time solution to the SAT problem by means of a family of tissue P systems from TSEC(3,2) has been provided. It remains open whether NP-complete problems can be efficiently solved by tissue P systems from TSEC(2,2).What about the computational efficiency of TSEC(2,𝑛),for each natural number 𝑛≥2?Moreover,thesolutionto the SAT probleminTheorem8hasbothevolutional symport rules and evolutional antiport rules. It is of interest to investigate the computational power of tissue P systems with cell separation that use only either evolutional symport or evolutional antiport rules. (2) In the framework of tissue P systems, the environment is a singular region since the objects initially placed in it have an arbitrary large number of copies. Tissue P systemswithcellseparationandwithoutenvironment (the alphabet of the environment is empty) were considered in [43]. It would be interesting to analyze the computational efficiency of recognizer TESAS P systems when the alphabet of the environment is an empty set. (3) Besides much investigated maximal parallelism, several ways of using rules were also considered in membrane computing, such as flat maximal parallelism [44, 45]. It remains open what the computation power of recognizer TESAS P systems working in a flat maximally parallel manner is. (4) In [33], recognizer TESA P systems with cell division were introduced and the length of an evolutional communication rule was defined as the total number of objects involved in it. The computational efficiency of TDEC(4), the class of all recognizer TESA P systems with cell division using evolutional communication rules with length at most 4, wasprovided.Weproposetoanalyzetheefficiency of recognizer TESA P systems with cell division with respect to the length of evolutional communication rules given in this paper: length(𝑟) = (length(LHS(𝑟)), length(RHS(𝑟))).Infact,thesolution to SAT problemprovidedinthecitedpaper corresponds to a family from TDEC(3,2).What about the computational efficiency of TDEC(2,𝑛),for each natural number 𝑛≥2? Appendix A Software Aid for Validation: Details and Remarks The solution to the SAT problem by TESAS P systems is very complicated (see Theorem 8); it is not obviously a trivial solution, easy to follow and check. In order to check whether the solution to the SAT problem by TESAS P systems is correct, a custom visual application based on MeCoSim (http://www.p-lingua.org/mecosim/)was provided (see [25] for further study). With this software application, P systems designers could analyse carefully their design; in addition, end users were able to introduce their propositional formulas visually, then run the simulations, and finally get the results. In what follows, we will develop a new simulator MeCoSimtocheckthecorrectnessofthesolutiontotheSAT problems. Taking the existing P-Lingua syntax for P systems introduced in [25] as a starting point, we will introduce the syntax for tissue P systems with evolutional symport/antiport rules (that we will abbreviate referring to the class as TSEC), alongthefollowingsubsections.Then,wewillprovideabrief description about the simulators developed to run this kind of systems. New Elements in P-Lingua Framework. P-Lingua framework includes up to now a significant number of P systems supported; however, it cannot obviously include elements not conceived so far. Therefore, if we want to simulate a new model, some elements might be necessary. The following types of rules were available for classical symport/antiport rules: (i) (1,𝑇1/𝑡1,2); (ii) (3,𝐸3/𝜆,0). The P-Lingua syntax for these classical types of communication rules was the following: [T{1}]’1 <-->[t{1}]’2; /∗antiport rule $(1, T 1/t i, 2))$ ∗/ [E{3}]’3 <-->[ ]’0. /∗symport rule $(3, E 3/\lambda, 0))$ ∗/ Thus, the syntax tried to mimic the theoretical description of the computing model. This kind of rules might also be present in P systems in TSEC. However, in this new model, additional types of rules appear, and the previous ingredients are not enough, so P-Lingua language had to be extended to include the possibility of rules with two cells in the left hand side of the rule, as the ones described along the paper: (i) [𝐸𝑖,𝑗]1[𝑙𝑗]3→[𝑙𝑖,𝑗]1[𝐸𝑖,𝑗]3,1≤𝑖≤𝑛,1≤𝑗≤𝑚; (ii) [𝛼4𝑛+3𝑚+4𝑝]3[] 0→[] 3[no]0. Complexity 17 Model Specification. Any P-Lingua file defining a P system in TSEC must set tsec asitsmodel,thusbeginningsuchfile with the sentence: @model<tsec> The rest of the file will then define the main elements describing the P system, typically consisting of Π=(Γ,Γ 0,Γ 1,E,Σ,M1,...,M𝑞,R,𝑖in,𝑖out). (A.1) These elements are described in detail in the following subsections. The sets of rules will include the new elements introduced by this work, and other subsections, without significant changes with respect to other existing models, are included here to make the work self-contained. Cells Structure. Before starting with the translation of the elements explicitly written in Π, let us pay attention to thestructureofthesystem.Whilethestructureofcells is implicit in the definition above, which is deduced from M1,...,M𝑞, in P-Lingua, the structure of cells must be explicitly described. For instance, the structure of a tissue P system in TSEC with 𝑞=3should be defined as follows: @mu = [ [ ]’1 [ ]’2 [ ]’3 ]’0; As it can be seen, an external structure labelled by 0is included, representing the environment containing the three cells. Alphabets. The first element appearing in the definition of a PsystemisΓ, with partition divided into Γ0and Γ1.These alphabets are described in P-Lingua in the following way: @ms1=a,b,c; /∗Describe $\Gamma 0$), containing the set $\{a,b,c\})$ ∗/ @ms2 = d, e, f; /∗Describe $\Gamma 1$), containing the set $\{d,e,f\})$ ∗/ The alphabet of the environment Eis specified through the assignment of an initial set of elements to the environment, in the usual way to specify multisets in P-Lingua, butinthiscasewiththetargetregion0representingthe environment. For instance, let us consider an alphabet of the environment as E={𝐸 0}∪{𝛼 𝑖|0≤𝑖≤4𝑛+3𝑚+4}. (A.2) It would be written in P-Lingua as @ms(0) = E{0}; @ms(0) += al{i}:0<=i<=4∗n+3∗m+4; /∗$\alpha i$ is written as al{i}∗/ Note that while a simple set can be assigned by the symbol =, the incremental inclusion of new elements requires the use of symbol +=.Otherwise,thepreviousassignmentisreplaced by the new one, not only between the first instruction and the second, but also for each iteration of the loop involving variable i. No explicit definition of Σis given in P-Lingua. On the contrary, the corresponding symbols are introduced in Γ0or Γ1,thusbeingpartofΓ, and their use as elements of the input alphabet will be given by its inclusion in the input cell, which is also not explicitly given. Definition of Initial Multisets. When defining P systems in TSEC, a relevant element to include is the multiset of objects initially present inside each cell, M1,...,M𝑞. This is performed through the assignment of the multiset to the label of the corresponding cell. Thus, given M1={𝐴 1,𝐵1},itcan be specified in P-Lingua as follows: @ms(1)=A{1},B{1}; Definition of Rules.Themainfocusofthisworkwasonthe study of the computational complexity of tissue P systems with evolutional symport/antiport rules. More specifically, relevant results regarding frontiers of the efficiency of P systems in TSEC were provided, and in this kind of systems the role of the evolutional rules was crucial. It is not therefore surprising that the most relevant ingredients included in P- Lingua framework as part of this work were the evolutional communication rules needed as part of the definition of the sets 𝑅𝑖described below. (i) [𝐸𝑖,𝑗]1[𝑙𝑗]3→[𝑙𝑖,𝑗]1[𝐸𝑖,𝑗]3,1≤𝑖≤𝑛,1≤𝑗≤𝑚, (ii) [𝛼4𝑛+3𝑚+4𝑝]3[] 0→[] 3[no]0 The grammar designed in P-Lingua for tsec includes the required elements, so that these rules can be specified as shown: [Eb{i,j }]'1 [l{j}]'3 -->[lb{i,j }]'1 [Eb{i,j }]'3 : 1<=j<=m, 1<=i<=n; [al{4*n+3*m+4 },p]'3 [ ]'0 -->[ ]'3 [no]'0; Note that the suffix bin some objects stands for bar,given the impossibility to express the top bars over the letters in plain text files. Apart from that, the design of the language triedtopreservethesyntaxascloseaspossibleofthatfor defining the P systems throughout the paper. Thus, the first rule is an evolutional antiport rule involving cells 1 and 3, and the second one is an evolutional symport rule. Input and Output Region. The last syntactic elements in the definition of P systems in TSEC aretheinputandtheoutput region. There is no explicit definition of these elements in P- Lingua. Instead, some elements can be defined in MeCoSim website in relation with that input/output. Regarding the input, MeCoSim provides most user-oriented layer of the framework, allowing the customization of input tables in the user interface. The data introduced in these tables are then converted into parameters for the model that can be used to generate the corresponding cod(𝜑). Let us illustrate this with the solution for the SAT problem given in the previous section and whose P-Lingua file is given in Algorithm 4. A MeCoSim custom app has been defined, 18 Complexity Figure 2: MeCoSim input table. including an input table whose rows represent tuples (clause, variable, and value), so that, for each variable appearing in a clauseandinputformula,thevaluecanbe1ifthevariable appears in the clause in positive form and −1ifitisnegated (see Figure 2). For each row i, the configuration given in MeCoSim defines parameters for variable{i},clause{i}, and value{n}; this last parameter is converted to other two parameters,valandvaln,eachonebeing1ifthevalueis1 (resp., −1), and 0 otherwise. In the given solution, the input cell is 3, so the input multiset cod(𝜑) is finally generated, from an input given by the input and automatically converted into parameters, with the following sentence in P-Lingua: def define input () { @ms(3) += xb{variable{i},clause{i}}∗valn{i}, x{variable{i},clause{i}}∗val{i}:1<=i<=nvals; } As it can be seen, the assignment of objects to the input cell iterates over each pair ⟨variable,clause⟩(note that nvals is another parameter corresponding with the number of rows in the input table, that is, the number of pairs ⟨variable,clause⟩). Thus, if row 1 of the input table states that variable 2 appears in clause 1 in negated form (resp., in affirmed form), then an object xb{2,1 }(resp., x{2,1 })is added to the input multiset, as expected by the definition of the input given in the previous subsection, where objects 𝑥𝑖,𝑗 (resp., 𝑥𝑖,𝑗) were described. It is worth noting at this point thattheenduserwasprovidedwithanadditionalaidto introduce their formulas, through a MeCoSim plugin for SAT that generates the information for the tables from a more user-friendly input format, as shown in Figure 3. Regarding the output cell, again there is no explicit definition in P-Lingua, but the whole system will follow a computation; when a halting configuration is reached, one can interpret the output in many different ways. However, another mechanism in MeCoSim allows the customization of outputs to focus on the regions, objects, or results expected by the user. Thus, for SAT problem, a P system designer can Figure 3: MeCoSim SAT plugin. Figure 4: MeCoSim output for P systems designer. pay attention to every object appearing inside each cell or in the environment, as shown in Figure 4; however, an end user interested in SAT problem itself will only focus on the final answer, given internally by the presence of object 𝑦𝑒𝑠 or 𝑛𝑜 in the environment in the last step of the computation and abstractedtotheuserbytablesorchartsasshowninFigure5. New Simulators for Tissue P Systems with Evolutional Rules. The main elements of the language designed for the specification of P systems in TSEC within the framework of P- Lingua have been described. In addition, some features have been shown concerning the interaction layer provided by MeCoSim, the introduction of inputs, and the visualization of results. However, nothing has been said about what happens with the specification of the P system given in P-Lingua and theinputgivenbytheenduser,beforetheresultactually appears. Obviously, the answer is clear: we need something able to generate the initial configuration of the P system and perform its computation until a halting configuration is reached. In the proof of Theorem 5, a deterministic algorithm wasgiventoreproducethebehaviourofacomputationof Π+𝑚,with𝑚an input multiset coding the input of the system. We will see that a simulator has been developed to mimic the algorithm described, but before that other alternative approaches have been followed to complement it. Thus, several simulators have been developed within the Complexity 19 Figure 5: MeCoSim output for end user. engine of P-Lingua, in order to perform the computations of P systems in TSEC.Allthesimulatorsfollowageneralschema: (1) Initialization (2) For each computation step, while some rules are applicable: (a) Selection of rules (b) Execution of rules The initialization phase will set the initial structures needed by the algorithm, and the details are mainly technical, not considered very relevant for scientific purposes. Then, the main loop will run until a halting configuration is reached, that is, until no rule is applicable at a given computation step. The selection phase will check which rules can be applied. The simulators developed present subtle differences in this phase, but all of them meet the semantics defined for this kind of newly defined systems. Thus, the maximality is guaranteed,andtheapplicabilityoftherulesisthesamein all the cases: the multisets present in the left hand side of the rules must be present in order to make a rule applicable. Besides,atmostoneselectionrulecanbeperformedover the same cell in a computation step, and the simultaneous execution of separation and communication rules in the same step affecting the same cell is not allowed. In addition, the simulators developed prioritize the selection of evolutional symport/antiport rules (abbreviated as communication rules), so that selection rules will only be applied to a cell if no evolutional symport/antiport rules can be selected affecting the cell. The main differences in the four simulators developed are the following: (i) Nondeterministic simulator: this simulator distinguishes two states (first communication rules are selected and later separation rules if no communication rules can be selected over a cell); this simulator visits cell by cell, according to its order of appearance in P-Lingua file; for each cell, the set of rules is shuffled and then applied as many times as possible, to guarantee maximality. (ii) Deterministic by cell: the selection phase keeps the same two states of the previous simulator, but the cells are visited according to the lexicographical order of their labels. The set of rules inside each cell is not shuffled but visited according to P-Lingua file order. (iii) Deterministic by rule:thissimulatorismoresimilar to the deterministic algorithm described in the proof of Theorem 5. Thus, its selection phase, instead of goingcellbycell(astheprevioussimulators),starts visiting at the most external level each rule. As described in that section, the rules are visited in the following order: direct communication between cells, then communication with environment, and finally separation,ifpossible;foreachtypeofrulesofthe same type, it selects the rules following the order in the P-Lingua file. (iv) Deterministic by rule, lexicographically:itperforms the computations as described in the proof of Theorem 5. In addition to the most external visit of the different set of rules, in the same order of the previous simulator, inside a specific type of rules, the cells are visited according to the lexicographical order of their labels, thus meeting the structure defined in the referred section. As a result of this selection phase, a set of rules will have been selected, verifying that every membrane with applicable rules has selected exactly one. Then, the execution phase applies the change in the configuration, passing from C𝑡to C𝑡+1,removingtheobjects consumed by the selected rules, and adding the objects produced by the rules to the corresponding target indicators. Computer-Aided Design and Validation of Tissue P Systems with Evolutional Symport/Antiport Rules.Thetoolsdescribed in the previous subsections have played a significant role in the design, simulation, and validation of the solution for the SAT problem described in Theorem 8. As mentioned at the beginning of the present section, handling complex solutions as the one presented here is not an easy task, frequently tedious end error-prone. Therefore, the availability of the software tools developed has provided a significant help in the checking of the model and its properties. First of all, these tools include parsers to detect possible errors in P-Lingua files that could be translation errors or duetoinaccuraciesfromthesolution,maybenotmeeting some features required by the computing model. Throughout the debugging process, we are informed about the rules that are being generated for the system, so that we can check that the expected sets of rules are actually available for the computation of the system, as shown in Figure 6. If some errors are detected, we are informed in Errors tab. Other possible alerts are given in Warnings tab. In addition, parsing tab will show at the end the initial configuration of the system, thus allowing the P systems designer to contrast if the expected multisets were produced. Once the solution has been proved correct after the debugging process, we can be interested in checking that the systemevolvesaccordingtoourmanualtraces;todoso,we can follow the computation step by step, informing about the rules applied for each step and the objects contained inside each region of every configuration, as shown in Figure 7. In addition, several visual aids are available to ease the checking of information concerning alphabets, structure, or 20 Complexity Figure 6: Debugging process. Figure 7: Step by step simulation process. Figure 8: An example of simulation information in a computation. multisets inside each region. These aids can be visualized in any moment of the computation. An example of this kind of viewers is given in Figure 8. Additionally, along with the checking of the specific solution, the development of this type of tools shows itself as a good way of revisiting the general algorithms proposed for the model, paying attention to subtle details, given the need of reproducing every detail specified in the formal definition of the model, so these development tasks emerge as enriching complementary tasks for the robustness of the computing models and their corresponding theoretical definitions. Conflicts of Interest The authors declare that there are no conflicts of interest regarding the publication of this article. Acknowledgments The work of Linqiang Pan and Bosheng Song was supported by National Natural Science Foundation of China (61602192, 61772214, 61320106005, and 61033003), China Postdoctoral Science Foundation (2016M600592, 2017T100554), and the Innovation Scientists and Technicians Troop Construction Projects of Henan Province (154200510012). References [1] Gh. P˘ aun, “Computing with membranes,” JournalofComputer and System Sciences,vol.61,no.1,pp.108–143,2000. [2] M. Amos, A. Gibbons, and P. E. Dunne, “Toward feasible and efficient DNA computation,” Complexity,vol.4,no.1,pp.20– 24, 1998. [3] C. S. Calude and Gh. P˘ aun, “Computing with cells and atoms in anutshell,”Complexity, vol. 6, no. 1, pp. 38–48 (2001), 2000. [4] B. Aman, P. Batty´ anyi,G.Ciobanu,andG.Vaszil,“Simulating P systems with membrane dissolution in a chemical calculus,” Natural Computing,vol.15,no.4,pp.521–532,2016. [5] M. Ionescu, Gh. P˘ aun, and T. Yokomori, “Spiking neural P systemswithanexhaustiveuseofrules,”International Journal of Unconventional Computing,vol.3,no.2,pp.135–156,2007. [6] S. N. Krishna and Gh. P˘ aun, “P systems with mobile membranes,” Natural Computing,vol.4,no.3,pp.255–274,2005. [7] V. Manca and L. Marchetti, “Solving dynamical inverse problems by means of Metabolic P systems,” BioSystems,vol.109,no. 1,pp.78–86,2012. [8]H.Peng,J.Wang,M.J.P ´ erez-Jim´ enez, and A. Riscos-N´ u˜ nez, “An unsupervised learning algorithm for membrane computing,” Information Sciences, vol. 304, pp. 80–91, 2015. [9]H.Peng,J.Wang,P.Shi,M.J.P ´ erez-Jim´ enez, and A. Riscos- N´ u˜ nez, “An extended membrane system with active membranes to solve automatic fuzzy clustering problems,” International Journal of Neural Systems,vol.26,no.3,pp.1–17,2016. [10]G.Zhang,H.Rong,F.Neri,andM.J.P ´ erez-Jim´ enez, “An optimization spiking neural P system for approximately solving combinatorial optimization problems,” International Journal of Neural Systems,vol.24,no.5,2014. [11] C. Mart´ ın-Vide, J. Pazos, Gh. P˘ aun, and A. Rodr´ ıguez-Pat´ on, “Tissue P systems,” Theoretical Computer Science,vol.296,no. 2, pp. 295–326, 2003. [12] M. Ionescu, Gh. P˘ aun, and T. Yokomori, “Spiking neural P systems,” Fundamenta Informaticae,vol.71,no.2-3,pp.279–308, 2006. [13] Gh. P˘ aun, G. Rozenberg, and A. Salomaa, Eds., The Oxford Handbook of Membrane Computing, Oxford University Press, New York, NY, USA, 2010. [14] A. P˘ aun and Gh. P˘ aun, “The power of communication: P systems with symport/antiport,” New Generation Computing, vol.20,no.3,pp.295–305,2002. [15] A. Alhazov, R. Freund, and M. Oswald, “Cell/symbol complexity of tissue P systems with symport/antiport rules,” International Journal of Foundations of Computer Science,vol.17,no. 1, pp. 3–25, 2006. [16] S. N. Krishna, K. Lakshmanan, and R. Rama, “Tissue P systems with contextual and rewriting rules,” Lecture Notes in Computer Science, vol. 2597, pp. 339–351, 2003. [17] A. P˘ aun, Gh. P˘ aun, and G. Rozenberg, “Computing by communication in networks of membranes,” International Journal Complexity 21 of Foundations of Computer Science, vol. 13, no. 6, pp. 779–798, 2002. [18] B. Song, T. Song, and L. Pan, “A time-free uniform solution to subset sum problem by tissue P systems with cell division,” Mathematical Structures in Computer Science,vol.27,no.1,pp. 17–32, 2017. [19] R. Freund, Gh. P˘ aun, and M. J. P´ erez-Jim´ enez, “Tissue P systems with channel states,” Theoretical Computer Science,vol. 330, no. 1, pp. 101–116, 2005. [20] R. Freund and M. Oswald, “Modelling grammar systems by tissue P systems working in the sequential mode,” Fundamenta Informaticae,vol.76,no.3,pp.305–323,2007. [21] Gh. P˘ aun, M. J. P´ erez-Jim´ enez, and A. Riscos-N´ u˜ nez, “Tissue P systems with cell division,” International Journal of Computers, Communications & Control,vol.3,no.3,pp.295–303,2008. [22] B. Aman and G. Ciobanu, “Efficiently solving the bin packing problem through bio-inspired mobility,” Acta Informatica,vol. 54, no. 4, pp. 435–445, 2017. [23] D. D´ ıaz-Pernil,M.A.Guti ´ errez-Naranjo, M. J. P´ erez-Jim´ enez, and A. Riscos-N´ u˜ nez, “Solving subset sum in linear time by using tissue P systems with cell division,” Lecture Notes in Computer Science,vol.4527,no.1,pp.170–179,2007. [24] D. D´ ıaz-Pernil,M.J.P ´ erez-Jim´ enez,A.Riscos-N ´ u˜ nez, and ´ A. Romero-Jim´ enez, “Computational efficiency of cellular division in tissue-like membrane systems,” RomanianJournalofInformation, Science and Technology,vol.11,no.3,pp.229–241,2008. [25] I. P´ erez-Hurtado, L. Valencia-Cabrera, J. M. Chac´ on, A. Riscos- N´ u˜ nez, and M. J. P´ erez-Jim´ enez, “A P-Lingua based simulator for tissue P systems with cell separation,” Romanian Journal of Information Science and Technology,vol.17,no.1,pp.89–102, 2014. [26] M. J. P´ erez-Jim´ enez and P. Sos´ ık, “An optimal frontier of the efficiency of tissue P systems with cell separation,” Fundamenta Informaticae,vol.138,no.1-2,pp.45–60,2015. [27] A.Alhazov,A.Leporati,G.Mauri,A.E.Porreca,andC.Zandron, “Space complexity equivalence of P systems with active membranes and Turing machines,” Theoretical Computer Science,vol.529,pp.69–81,2014. [28] A.Leporati,L.Manzoni,G.Mauri,A.E.Porreca,andC.Zandron, “Membrane division, oracles, and the counting hierarchy,” Fundamenta Informaticae, vol. 138, no. 1-2, pp. 97–111, 2015. [29] L. Pan and M. J. P´ erez-Jim´ enez, “Computational complexity of tissue-like P systems,” Journal of Complexity,vol.26,no.3,pp. 296–315, 2010. [30] A. E. Porreca, N. Murphy, and M. J. P´ erez-Jim´ enez, “An optimal frontier of the efficiency of tissue P systems with cell division,” in Proceedings of the Tenth Brainstorming Week on Membrane Computing, pp. 141–166, Seville, Spain, 2012. [31] R. Guti´ errez-Escudero, M. J. P´ erez-Jim´ enez, and M. Rius-Font, “Characterizing tractability by tissue-like P systems,” Lecture Notes in Computer Science,vol.5957,pp.289–300,2009. [32] L. F. Mac´ ıas-Ramos, B. Song, L. Valencia-Cabrera, L. Pan, and M. J. P´ erez-Jim´ enez, “Membrane fission: a computational complexity perspective,” Complexity,vol.21,no.6,pp.321–334, 2016. [33] B. Song, C. Zhang, and L. Pan, “Tissue-like P systems with evolutional symport/antiport rules,” Information Sciences,vol.378, pp.177–193,2017. [34] D. D´ ıaz-Pernil, I. P´ erez-Hurtado, M. J. P´ erez-Jim´ enez, and A. Riscos-N´ u˜ nez, “A P-lingua programming environment for membrane computing,” Lecture Notes in Computer Science,vol. 5391, pp. 187–203, 2009. [35] M. Garca-Quismondo, R. Guti´ errez-Escudero, I. P´ erez-Hur- tado,M.J.P ´ erez-Jim´ enez, and A. Riscos-N´ u˜ nez, “An overview of P-Lingua 2.0,” Lecture Notes in Computer Science,vol.5957, pp. 264–288, 2010. [36] P-Lingua, http://www.p-lingua.org/. [37] I. P´ erez-Hurtado, L. Valencia-Cabrera, M. J. P´ erez-Jim´ enez, M. A. Colomer, and A. Riscos-N´ u˜ nez, “MeCoSim: A general purpose software tool for simulating biological phenomena by means of P systems,” in Proceedings of the 2010 IEEE 5th International Conference on Bio-Inspired Computing: Theories and Applications, BIC-TA 2010,K.Li,Z.Tang,R.Li,A.K. Nagar, and R. Thamburaj, Eds., vol. 1, pp. 637–643, IEEE Press, Changsha, China, September 2010. [38] MeCoSim, http://www.p-lingua.org/mecosim/. [39] G. Rozenberg and A. Salomaa, Eds., Handbook of Formal Languages, vol. 3, Springer, Berlin, Germany, 1997. [40] M. J. P´ erez Jim´ enez, A. Romero, and F. Caparrini, “Complexity classes in models of cellular computing with membranes,” Natural Computing,vol.2,no.3,pp.265–285,2003. [41] M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness,W.H.Freeman,Ed., San Francisco, Calif, USA, 1979. [42] L. Pan, M. J. P´ erez-Jim´ enez, A. Riscos-N´ u˜ nez, and M. Rius- Font, “New frontiers of the efficiency in tissue P systems,” in Proceedings of the Asian Conference on Membrane Computing, pp.61–73,Wuhan,China,2012. [43] L. F. Mac´ ıas-Ramos, M. J. P´ erez-Jim´ enez, A. Riscos-N´ u˜ nez, M. Rius-Font, and L. Valencia-Cabrera, “The efficiency of tissue P systems with cell separation relies on the environment,” Lecture Notes in Computer Science,vol.7762,pp.243–256,2013. [44] L. Pan, Gh. P˘ aun, and B. Song, “Flat maximal parallelism in P systems with promoters,” Theoretical Computer Science,vol.623, pp.83–91,2016. [45] B. Song, M. J. P´ erez-Jimenez, Gh. P˘ aun, and L. Pan, “Tissue P systems with channel states working in the flat maximally parallel way,” IEEE Transactions on NanoBioscience,vol.15,no. 7,pp.645–656,2016. Hindawi www.hindawi.com Volume 2018 Mathematics Journal of Hindawi www.hindawi.com Volume 2018 Mathematical Problems in Engineering Applied Mathematics Journal of Hindawi www.hindawi.com Volume 2018 Probability and Statistics Hindawi www.hindawi.com Volume 2018 Journal of Hindawi www.hindawi.com Volume 2018 Mathematical Physics Advances in Complex Analysis Journal of Hindawi www.hindawi.com Volume 2018 Optimization Journal of Hindawi www.hindawi.com Volume 2018 Hindawi www.hindawi.com Volume 2018 Engineering Mathematics International Journal of Hindawi www.hindawi.com Volume 2018 Operations Research Advances in Journal of Hindawi www.hindawi.com Volume 2018 Function Spaces Abstract and Applied Analysis Hindawi www.hindawi.com Volume 2018 International Journal of Mathematics and Mathematical Sciences Hindawi www.hindawi.com Volume 2018 Hindawi Publishing Corporation http://www.hindawi.com Volume 2013 Hindawi www.hindawi.com The Scientific World Journal Volume 2018 Hindawi www.hindawi.com Volume 2018 Volume 2018 Numerical Analysis Numerical Analysis Numerical Analysis Numerical Analysis Numerical Analysis Numerical Analysis Numerical Analysis Numerical Analysis Numerical Analysis Numerical Analysis Numerical Analysis Numerical Analysis Advances in Advances in Discrete Dynamics in Nature and Society Hindawi www.hindawi.com Volume 2018 Hindawi www.hindawi.com Differential Equations International Journal of Volume 2018 Hindawi www.hindawi.com Volume 2018 Decision Sciences Advances in Hindawi www.hindawi.com Volume 2018 Analysis International Journal of Hindawi www.hindawi.com Volume 2018 Stochastic Analysis International Journal of Submit your manuscripts at www.hindawi.com