1. Introduction
The main objective of Computability Theory is to define the informal idea of mechanical/algorithmic problems resolution in a rigorous way. Each formal definition of the said concept provides a computing model. A basic question is to determine the class of all problems that can be solved by a computing model when using the algorithms defined in it. In any computing model that captures the informal idea of an algorithm, there will always be undecidable problems, that is, problems that cannot be solved by using the algorithms of the model.
Analysing an algorithm that solves a problem consists of determining an upper bound for the minimal resource requirements with which the problem can be solved. One of the main goals of Complexity Theory is the study of the resources required for solving problems, and to provide tools allowing one to classify the problems with respect to the amount of resources needed for their resolution. These classes allow us to detect some of the inherent difficulties to the computational resolution of some problems, and they provide a classification of the abstract problems according to the resources they need to be solved in a given model.
Membrane Computing is a branch of Natural Computing providing distributed, parallel, synchronous and non-deterministic models of computation whose computational devices are called membrane systems. They are inspired by some basic biological features of the living cells (their structure, organization and functioning), as well as from the cooperation of cells in tissues, organs, and organisms. Membrane Computing was selected by the Thomson Institute for Scientific Information as a fast Emerging Research Front in computer science in 2003.
In this discipline there are basically two ways to consider computational devices: cell-like membrane systems (P systems) and tissue-like membrane systems (tissue P systems). The first one, using the biological membranes arranged hierarchically, inspired from the structure of the cell, and the second one using the biological membranes (called cells in this approach) placed in the nodes of a directed graph, inspired from the cell inter–communication in tissues. The objective of this paper is to introduce a Computational Complexity Theory in the framework of Membrane Computing and to analyse the P versus NP problem from the new perspective provided by this unconventional bio-inspired model of computing. We also present new frontiers of the efficiency of Membrane Computing models, in the sense of determining their capability to provide feasible solutions to hard problems. Each one of such borderlines provides new tools to attack the aforementioned problem.
The paper is organized as follows. First, we introduce the basic concepts that will be used throughout this paper. Next, we study the efficiency of different models of cell-like membrane systems (Section 3) and tissue-like membrane systems (Section 4). Some conclusions are presented in the final section.
2. Membrane Systems
A membrane system can be viewed as a finite set of basic units of processors (called membranes in the case of cell-like approach and cells in the case of tissue-like) arranged in an organised structure (a rooted tree in the case of cell-like and a directed graph in the case of tissue-like) and delimiting regions able to contain multisets of objects (symbols from a working alphabet Γ), which are abstractions of chemical substances. A finite set R of rewriting rules, abstractions of chemical reactions, provides the dynamics of the system. There exists a double parallelism in the application of rules, once at the level of each region (the rules are used in parallel) and once at the level of the system (all regions evolve concomitantly). Different models of membrane systems can be considered according to the syntax and the semantics of the rules used.
For cell-like systems the tree structure is explicitly included in their definition. The root of the tree is called the skin membrane of the system, and the leaves of the tree are called elementary membranes. However, in tissue-like systems the graph structure is not explicitly given, it comes implicitly determined through some especial rules of the system (communication rules). Every membrane system also has an associated environment, which represents the region surrounding the system. In the case of cell-like approach, it has a passive role, in the sense that it is initially empty and only receives objects from the system through the root of the tree (the skin membrane). On the other hand, in tissue-like systems, the environment is considered to have initially an arbitrarily large number of copies of objects from a distinguished alphabet E, contained within the working alphabet. Besides, the environment can interact with any cell of the system, not only receiving objects but also sending objects inside the cells. For this reason, the environment is considered as an additional region in tissue-like approach.
A configuration at any instant of a membrane system is described by all multisets of objects over the working alphabet, associated with all the processors (membranes or cells) present in the system. In cell-like systems the current tree structure must be considered, and in tissue P systems we also consider the multiset of objects from Γ\E present in the environment at that moment. A configuration is a halting configuration if no rule of the system is applicable to it. We can pass from the current configuration to another one in one transition step by applying the rules from R. The objects to evolve in a transition step and the rules by which they evolve are chosen in a non-deterministic and maximally parallel manner: we assign objects to rules but in such a way that after this assignation no further rule can be applied to the remaining objects.
A computation of the system is a (finite or infinite) sequence of configurations such that: (a) the first term of the sequence is the initial configuration of the system; (b) each remaining term is obtained from the previous configuration by applying rules of the system; and (c) if the sequence is finite (called halting computation) then the last term of the sequence must be a halting configuration.
Throughout this paper any membrane system has a distinguished alphabet, the input alphabet Σ, contained in the working alphabet, Γ, which allows us to encode instances of a problem. The idea is to impose that the initial multisets appearing in the definition of the system can only contain objects from Γ\Σ, and an additional multiset over Σ, encoding the instance to be solved, will be introduced into a distinguished (input) region/processor before starting the computation. For each multiset m over the input alphabet we have an initial configuration associated with it, obtained by adding m to the initial multiset associated with the input region. It is worth pointing out that the answer of a halting computation of a membrane system will be encoded by the contents of the environment associated with the corresponding halting configuration, as it will be explained below.
2.1. Recognizer Membrane Systems
In order to study the computational efficiency of membrane systems, the notions from classical Computational Complexity Theory are adapted for Membrane Computing, and a special class of cell-like P systems was introduced in Ref. Reference Pérez-Jiménez, Romero-Jiménez and Sancho-Caparrini1: recognizer P systems (called accepting P systems in a previous paperReference Pérez-Jiménez, Romero-Jiménez and Sancho-Caparrini2). The same idea was adapted for the tissue-like case in Ref. Reference Păun, Pérez-Jiménez and Riscos-Núñez3, introducing recognizer tissue P systems.
A membrane system is a recognizer system if: (a) the working alphabet has two distinguished objects yes and no, but in the case of tissue P systems, at least, one copy of them is present in some initial multisets but none of them are present initially in the environment; (b) all computations halt; and (c) for each computation of the system, either object yes or object no (but not both) must have been released into the environment, and only at the last step of the computation.
We say that a computation C of a recognizer membrane system is an accepting computation (respectively, rejecting computation) if object yes (respectively, object no) appears in the environment associated with the corresponding halting configuration of C, and neither object yes nor object no appears in the environment associated with any non–halting configuration of C.
2.2. Polynomial Complexity Classes of Membrane Systems
Let us recall that a decision problem is a pair (IX,ΘX) where IX is a language over a finite alphabet (whose elements are called instances) and ΘX is a total Boolean function over IX. Next, we define what solving a decision problem efficiently means in the framework of membrane systems.
Definition 1. We say that a decision problem X = (IX,ΘX) is solvable in polynomial time by a family ∏ = {Π(n) | n∈N} of recognizer membrane systems if the following holds.
(1) The family ∏ is polynomially uniform by Turing machines, that is, there exists a deterministic Turing machine working in polynomial time such that on input 1n, constructs the system Π(n).
(2) There exists a pair (cod; s) of polynomial-time computable functions over IX such that:
(a) for each instance u∈IX, s(u) is a natural number and cod(u) is an input multiset of the system Π(s(u));
(b) for each n∈N, s −1(n) is a finite set;
(c) the family ∏ is polynomially bounded with regard to (X; cod; s), that is, there exists a polynomial function p, such that for each instance u∈IX every computation of Π(s(u)) with input cod(u) is halting and it performs at most p(|u|) steps;
(d) the family ∏ is sound with regard to (X; cod; s), that is, for each instance u∈IX, if there exists an accepting computation of Π(s(u)) with input cod(u), then ΘX(u) = 1;
(e) the family ∏ is complete with regard to (X; cod; s), that is, for each instance u∈IX, if ΘX(u) = 1, then every computation of Π(s(u)) with input cod(u) is an accepting one.
From the soundness and completeness conditions above we deduce that every system Π(n) from the family is confluent, in the following sense: every computation of a system Π(s(u))+cod(u) processing an instance u of the problem must always give the same answer.
Let us recall that an instance of a decision problem is accepted by a non-deterministic Turing machine processing it, if there exists, at least, an accepting computation. Then, the classical notion of acceptance is not a true algorithmic concept. Nevertheless, an instance will be accepted by a membrane system processing it, if and only if each computation of the system is an accepting computation. Thus, the presented definition of acceptance by a membrane system substantially differs from the acceptance by a non-deterministic Turing machine.
Let R be a class of recognizer membrane systems. We denote by PMCR the set of all decision problems that can be solved in polynomial time by means of families of systems from R. The class PMCR is closed under complement and polynomial–time reductions.Reference Pérez-Jiménez, Romero-Jiménez and Sancho-Caparrini2
3. Efficiency of Cell-like Membrane Systems
This section studies the computational efficiency of several models of cell-like membrane systems, that is, their capability to solve computationally hard problems in an efficient way. These variants are considered by using specific kind of rules and, also, by adding new ingredients as electrical charges.
3.1. Basic Transition P Systems
Basic transition P systems are a kind of cell-like membrane systems whose membrane structure does not grow, that is, there are no rules that produce new membranes in the system.
First of all, in order to formally define what it means that a family of membrane systems simulates a Turing machine in an efficient way, we shall introduce for each Turing machine a decision problem associated with it.
Definition 2. Let M be a deterministic Turing machine with input alphabet ΣM. The decision problem associated with M is the problem XM = (I M; ΘM), where I M = ΣM*, and for every u∈ΣM*, ΘM(u) = 1 if and only if M accepts u.
Obviously, the decision problem X M is solvable by the Turing machine M.
Definition 3. Let R be a class of recognizer membrane systems. We say that a deterministic Turing machine M is simulated in polynomial time by a family of systems from R if X M∈PMCR.
A basic transition P system is a cell-like membrane system whose rules are of the following form: [u→v]h, u[ ]h→[v]h, [u]h→[ ]h v, and [u]h→v, where h is the label of a membrane and u,v are multisets over the working alphabet. These rules do not increase the size of the membrane structure, but the application of a rule of the last type decreases the number of membranes. We denote by T the class of recognizer basic transition P systems.
In Ref. Reference Gutiérrez-Naranjo, Pérez-Jiménez, Riscos-Núñez, Romero-Campero and Romero-Jiménez4 an efficient simulation of deterministic Turing machines by recognizer basic transition P systems was given. Thus, we have the following result.
Proposition 1. (Sevilla theorem)
Every deterministic Turing machine working in polynomial time can be simulated in polynomial time by a family of recognizer basic transition P systems.
It was also proved that each confluent basic transition P system can be (efficiently) simulated by a deterministic Turing machine.Reference Gutiérrez-Naranjo, Pérez-Jiménez, Riscos-Núñez, Romero-Campero and Romero-Jiménez4 As a consequence, these membrane systems efficiently solve at most tractable problems. Therefore, we have the following.
Proposition 2. If a decision problem is solvable in polynomial time by a family of recognizer basic transition P systems, then there exists a deterministic Turing machine solving it in polynomial time.
From Proposition 1 and Proposition 2 we deduce the following result.
Theorem 1. P = PMCT.
Thus, the ability of a basic transition P system to create exponential workspace (in terms of number of objects) in polynomial time (e.g. via rules of the type [a→a 2]h) is not enough to efficiently solve NP–complete problems (assuming that P ≠ NP).
Theorem 1 provides a tool to attack conjecture P ≠ NP in the framework of Membrane Computing.
Corollary 1. P ≠ NP if and only if every, or at least one, NP-complete problem cannot be solved in polynomial time by families of basic transition P systems.
3.2. P Systems with Active Membranes
Replication is one of the most important functions of a cell and, in ideal circumstances, a cell produces two identical copies by division. Mitosis is an elegant process of cell division that results in the production of two daughter cells from a single parent cell. Daughter cells are identical to one another and to the original parent cell. Through a sequence of steps, the replicated genetic material in a parent cell is equally distributed to two daughter cells. While there are some subtle differences, mitosis is remarkably similar across organisms. Bearing in mind that the reactions that take place in a cell are related to membranes, rules for membrane division are considered.
P systems with active membranes were first introduced by Gh. Păun.Reference Păun5 This kind of cell-like membrane systems has electrical charges associated with membranes, which can be modified by the application of some rules (although labels always remain unchanged). They do not use cooperation, and they incorporate membrane division rules.
The rules of a P system with active membranes are of the following forms:
(a)
$$$ [a \rightarrow u]_{h}^{\alpha } $$$
(object evolution rules).(b)
$$$ a[]_{h}^{{\alpha 1}} \rightarrow [b]_{h}^{{\alpha 2}} $$$
(send-in communication rules).(c)
$$$ [a]_{h}^{{\alpha 1}} \rightarrow []_{h}^{{\alpha 2}} b $$$
(send-out communication rules).(d)
$$$ [a]_{h}^{\alpha } \rightarrow b $$$
(dissolution rules).(e)
$$$ [a]_{h}^{{\alpha 1}} \rightarrow [b]_{h}^{{\alpha 2}} [c]_{h}^{{\alpha 3}} $$$
(division rules for elementary membranes).(f)
$$$[[]_{{h1}}^{{\alpha 1}} []_{{h2}}^{{\alpha 2}} ]_{h}^{\alpha } \rightarrow [[]_{{h1}}^{{\alpha 3}} ]_{h}^{\beta } [[]_{{h2}}^{{\alpha 4}} ]_{h}^{\gamma } $$$
(division rules for non–elementary membranes).
where a,b,c are objects, u is a multiset of objects, and 
$$$ \alpha, \beta, \gamma, \alpha 1,\alpha 2,\alpha 3,\alpha 4 $$$
are electrical charges from the set {+,0,−}.
The rules of a P system with active membranes are applied according to the following principles (see Ref. Reference Păun5 for details).
• The rules associated with membranes labelled by h are used for all copies of this membrane. At one step, a membrane can be the subject of only one rule of types (b)–(f).
• All the rules are applied in parallel and in a maximal manner. In one step, one object of a membrane can be used by only one rule (chosen in a non-deterministic way), but any object that can evolve by one rule of any form, must evolve, with the restriction just mentioned above.
• If a membrane is dissolved, its contents (multiset and internal membranes) are left free in the surrounding region, or in the nearest non-dissolved ancestor. The skin membrane cannot be dissolved.
• If at the same time a membrane labelled by h is divided by a rule of type (e) and there are objects in this membrane that evolve by means of rules of type (a), then we suppose that first the evolution rules of type (a) are used, and then the division is produced. Of course, this process takes only one step. Analogously for rules of type (f). The skin membrane cannot be divided.
Let us denote by AM the class of recognizer P systems with active membranes, and let NAM be the class of recognizer P systems with active membranes that do not make use of division rules.
In the framework of cell-like membrane systems, confluent recognizer P systems with active membranes making use of no division rule, can be efficiently simulated by a deterministic Turing machine. This can be shown by adapting the proof of the following result, given in Ref. Reference Zandron, Ferretti and Mauri6.
Proposition 3. (Milano theorem.) A deterministic P system with active membranes but without membrane division can be simulated by a deterministic Turing machine with a polynomial slowdown.
As a consequence of the previous result, the following holds.
Corollary 2. PMCNAM ⊆ P.
In Ref. Reference Porreca7, a simple proof of each tractable problem being solvable by a family of recognizer P systems with active membranes (without polarizations) operating in exactly one step and using only send-out communication rules, has been provided. Thus, we have the following.
Proposition 4. P ⊆ PMCNAM.
From Corollary 2 and Proposition 4 we deduce the following result.
Proposition 4. P = PMCNAM.
Let us notice that Theorem 2 can be considered as a version of Theorem 1 for the class NAM.
Remark 1. In the framework of P systems with active membranes, the use or not of the division rules provides a borderline for the tractability of decision problems, assuming that P ≠ NP, that is, by using division rules we can solve NP-complete problems in polynomial time, but without division rules only problems in P can be solved in an efficient way.
We denote by AM(+n) (respectively, AM(–n)) the class of recognizer P systems with active membranes using division rules for elementary and non–elementary membranes (respectively, only for elementary membranes).
In the framework of AM(–n), efficient solutions to weakly NP–complete problems (Knapsack,Reference Pérez-Jiménez and Riscos-Núñez8 Subset Sum,Reference Pérez-Jiménez and Riscos-Núñez9 PartitionReference Gutiérrez-Naranjo, Pérez-Jiménez and Riscos-Núñez10), and strongly NP–complete problems (SAT,Reference Pérez-Jiménez, Romero-Jiménez and Sancho-Caparrini2 Clique,Reference Alhazov, Martín-Vide and Pan11 Bin Packing,Reference Pérez-Jiménez and Romero-Campero12 Common Algorithmic ProblemReference Pérez-Jiménez and Romero-Campero13) have been given. In particular, the following.
Proposition 5. SAT ∈ PMCAM(−n).
Since PMCR is closed under complement and polynomial-time reductions, for any class R of recognizer membrane systems, the following result holds.
Proposition 6. NP ∪ co-NP ⊆ PMCAM(−n).
In the framework of AM(+n) it has been shownReference Alhazov, Martín-Vide and Pan14 that the QBF-SAT problem can be solved in a linear time by a family of recognizer P systems with active membranes (without using dissolution rules) and using division rules for elementary and non-elementary membranes. Thus, we have the following result.
Proposition 7. PSPACE ⊆ PMCAM(+n).
In Ref. Reference Porreca, Mauri and Zandron15, a (deterministic and efficient) algorithm simulating a single computation of any confluent recognizer P system with active membranes, has been described. Such P systems can be simulated by a deterministic Turing machine working with exponential space, and spending a time of the order O(2p(n)), for some polynomial p(n). Thus, we have PMCAM (+n) ⊆ EXP, and hence we have the following.
Proposition 8. PSPACE ⊆ PMCAM(+n) ⊆ EXP.
Previous results show that the usual framework of P systems with active membranes for solving decision problems is too powerful from the computational complexity point of view. Therefore, it would be interesting to investigate weaker models of P systems with active membranes able to characterize classical complexity classes below NP and providing borderlines between efficiency and non–efficiency.
3.3. Polarizationless P Systems with Active Membranes
In this kind of P system with active membranes, the membranes of the system have no electrical charges. We denote AM0(α,β) as the class of all recognizer polarizationless P systems with active membranes such that: (a) if α = +d (respectively, α = –d) then dissolution rules are permitted (respectively, forbidden); and (b) if β = +n (respectively, –n) then division rules for elementary and non–elementary membranes (respectively, only for elementary membranes) are permitted.
At the beginning of 2005, Gh. Păun (problem F from Ref. Reference Păun16) wrote:
My favorite question (related to complexity aspects in P systems with active membranes and with electrical charges) is that about the number of polarizations. Can the polarizations be completely avoided? The feeling is that this is not possible – and such a result would be rather sound: passing from no polarization to two polarizations amounts to passing from non–efficiency to efficiency.
This so-called Păun's conjecture can be formally formulated in terms of membrane computing complexity classes as follows: P = PMCAM0(+d ,−n ).
Let Π be a recognizer polarizationless P system with active membranes that do not make use of dissolution rules. A directed graph (called a dependency graph) can be associated with Π verifying the following property: every accepting computation of Π is characterized by the existence of a path in the graph between two distinguished nodes. Based on this concept and by using the tractability of the reachability problem, the following result has been proved.Reference Gutiérrez-Naranjo, Pérez-Jiménez, Riscos-Núñez and Romero-Campero17
Theorem 3. P = PMCAM0(−d ,−n ) = PMCAM0(−d ,+n )
Thus, polarizationless P systems with active membranes that do not make use of dissolution rules cannot solve NP-complete problems in polynomial time (unless P = NP). This result can be considered as a partial affirmative answer to the Păun's conjecture.
Let us now consider polarizationless P systems with active membranes making use of dissolution rules. Will it be possible to solve NP-complete problems in that framework? Several authorsReference Gutiérrez-Naranjo, Pérez-Jiménez, Riscos-Núñez and Romero-Campero17, Reference Alhazov, Pan and Păun18 gave a positive answer when division for non-elementary membranes are allowed. The mentioned papers provide solutions in a linear time to SAT and Subset Sum problems, respectively. Thus, we have the following result.
Theorem 4. NP ∪ co-NP ⊆ PMCAM0(+d ,+n ).
As a consequence of Theorem 4, a partial negative answer to Păun's conjecture is given: assuming that P ≠ NP and making use of dissolution rules and division rules for elementary and non-elementary membranes, computationally hard problems can be efficiently solved avoiding polarizations. The answer is partial because efficient resolvability of NP–complete problems by polarizationless P systems with active membranes making use of dissolution rules and division only for elementary membranes is unknown.
Remark 2. In the framework of polarizationless P systems with active membranes, the use or not of the dissolution rules provides a borderline for the tractability of decision problems, assuming that P ≠ NP, that is, in the framework AM0(+n) by using dissolution rules we can solve NP–complete problems in polynomial time, but without dissolution rules only problems in P can be solved in an efficient way.
4. Efficiency of Tissue–like Membrane Systems
In this section, we study the efficiency of different models of tissue-like membrane systems. These variants are considered by using specific kind of rules. The basic one only considers communication rules but we also analyse tissue P systems where division or separation rules are also permitted.
4.1. Basic Tissue P Systems
Basic tissue P systems are characterized by the fact that they use only communication rules, that is, rules of the symport/antiport type: (i,u/v,j), where i,j are different regions of the system (one of which might be the environment) and u,v are multisets of objects not simultaneously empty. These rules provide one or two arcs according to the following: one arc from region i to region j (if u is nonempty), and another arc from region j to region i (if v is nonempty). When applying a rule (i,u/v,j), the objects of the multiset represented by u are transferred from region i to region j and, simultaneously, the objects of multiset v are sent from region j to region i in exchange. The length of the communication rule (i,u/v,j) is the total sum of objects that appear in multisets u and v.
We denote by TC the class of all recognizer basic tissue P systems. In Ref. Reference Díaz-Pernil, Gutiérrez-Naranjo, Pérez-Jiménez and Romero-Jiménez19 it was shown that every family of recognizer basic tissue P systems, which solves a decision problem, can be efficiently simulated by a family of recognizer basic transition P systems solving the same problem. Then, we have the following result.
Theorem 5. P = PMCTC
That is, basic tissue P system models are non-efficient in the sense that only problems in P can be solved by this kind of membrane systems in polynomial time, assuming that P ≠ NP.
4.2. Tissue P Systems with Cell Division
In tissue P systems with cell division, the rules of the system are communication rules and cell division rules, which are of the form [a]i→[b]i[c]i. When applying this rule, under the influence of object a, the cell with label i is divided into two cells with the same label; in the first copy, object a is replaced by object b, in the second one, object a is replaced by object c; all the other objects are replicated and copies of them are placed in the two new cells.
The rules of a tissue P system with cell division are applied in a non-deterministic maximally parallel manner as it is customary in Membrane Computing, with the following important remark: if a cell divides, only the division rule is applied to that cell at that step; the objects inside that cell do not evolve by means of communication rules. In other words, we can think that before division a cell interrupts all its communication channels with the other cells and with the environment. The new cells resulting from division will only interact with other cells or with the environment at the next step – providing they do not divide once again. The label of a cell identifies the rules that can be applied to it precisely.
For each natural number k ≥ 1, we denote by TDC(k) the class of recognizer tissue P systems with cell division such that each communication rule of the system has a length at most k.
By using the concept of a dependency graph associated with tissue P systems with cell division and communication rules with length at most 1, it has been proved that this kind of membrane system can only efficiently solve tractable problems (see Ref. Reference Gutiérrez-Escudero, Pérez-Jiménez and Rius–Font20 for details). Thus, the following holds.
Theorem 6. P = PMCTDC(1).
In Ref. Reference Porreca, Murphy and Pérez-Jiménez21, a polynomial–time solution of the HAM-CYCLE problem was given by using a family of recognizer tissue P systems with cell division and communication rules of length at most 2. Therefore, we have the following.
Proposition 9. NP ∪ co-NP ⊆ PMCTDC(2).
Remark 3. From Theorem 6 and Proposition 9, we deduce that in the framework of recognizer tissue P systems with cell division, the length of the communication rules provides a borderline of the tractability of decision problems. Specifically, passing from length 1 to length 2 amounts to passing from non–efficiency to efficiency, assuming that P ≠ NP. Moreover, another frontier is obtained when we add cell division rules in basic tissue P systems.
4.3. Tissue P Systems with Cell Separation
The biological inspiration of tissue P systems with cell separation is the following: alive tissues are not static network of cells, since new cells are generated by membrane fission in a natural way. In this kind of tissue P system, the rules of the system are communication rules and separation rules. A separation rule is of the form [a]i→[Γ1]i[Γ2]i, being {Γ1,Γ2} a fixed partition of the working alphabet associated with the system. This rule is applicable to cell i if object a is contained in that cell. When applying such a separation rule, in reaction with an object a, the cell i is separated into two cells with the same label; at the same time, object a is consumed; while the rest of the contents of the cell are distributed as follows: objects from Γ1 are placed in the first cell, and those from Γ2 are placed in the second cell; the output cell i out cannot be separated.
The rules are used in a non-deterministic maximally parallel manner, with a restriction: when a cell is separated, the separation rule is the only one that is applied for that cell at that step; thus, the objects inside that cell do not evolve by means of communication rules.
For each natural number k ≥ 1, we denote by TSC(k) the class of recognizer tissue P systems with cell separation such that each communication rule of the system has a length at most k.
By using the concept of dependency graph associated with tissue P systems with cell separation and communication rules with length at most 1, it has been proved that this kind of membrane systems can only efficiently solve tractable problems (see Ref. Reference Pan and Pérez-Jiménez22 for details). This result has been extended to tissue P systems with cell separation and communication rules with length at most twoReference Pan, Pérez-Jiménez, Riscos-Núñez and Rius-Font23 through an algorithmic method. Then, we have the following result.
Theorem 7. P = PMCTSC(2).
Remark 4. From Proposition 9 and Theorem 7 we deduce that the use of cell division rules instead of cell separation rules in tissue P systems with communication rules with length at most 2, provides efficient computing models.
In Ref. Reference Pérez-Jiménez and Sosík24, a polynomial–time solution of the SAT problem was given by using a family of recognizer tissue P systems with cell separation and communication rules of length at most 3. Thus, we have the following result.
Proposition 10. NP ∪ co-NP ⊆ PMCTSC(3).
Remark 5. From Theorem 7 and Proposition 10, we deduce that in the framework of recognizer tissue P systems with cell separation the length of the communication rules provides a borderline of the tractability of decision problems. Specifically, passing from length 2 to length 3 amounts to passing from non-efficiency to efficiency, assuming that P ≠ NP. Moreover, another frontier is obtained by adding separation rules to basic tissue P systems.
4.4. Tissue P Systems without Environment
Classical tissue P systems with cell division have a special alphabet whose elements initially appear in an arbitrary large number of copies. These objects are shared in a distinguished place of the system, called the environment. This property is not so nice from the complexity point of view. In this section we deal with tissue-like membrane systems where there is not an environment having the property mentioned above. Specifically, we analyse the role played by the environment in tissue-like membrane systems where division or separation rules are considered.
A tissue P system without environment is a tissue P system such that the alphabet of the environment is an empty set. For each natural number k ≥ 1, we denote by 
$$$ \overline{{TDC}} (k) $$$
(respectively, 
$$$ \overline{{TSC}} (k) $$$
) the class of recognizer tissue P systems with cell division (respectively, with cell separation), with communication rules of length at most k, and without environment.
In Ref. Reference Pérez-Jiménez, Riscos-Núñez, Rius-Font and Romero-Campero25, it is shown that every family Π of tissue P systems with cell division solving a decision problem can be simulated by a family Π′ of tissue P systems with cell division and without environment, in an efficient way. Moreover, the upper bound of the length of communication rules of the systems from Π is equal to the maximum length of communication rules of the system from Π′. That is, we have the following result.
Theorem 8. For each k ≥ 1 we have 
$$$ {\bf {{PM}}}{{{\bf {{C}}}}_{TDC{\rm{(}}k{\rm{)}}}} = {\bf {{PMC}}}{{\,}_{\overline{{TDC}} (k)}}. $$$
From this theorem we deduce that the environment is not relevant for the efficiency of tissue P systems with cell division. That is, for each polynomial–time solution of a decision problem X in TDC(k) we can construct a family of systems from 
$$$ \overline{{TDC}} (k) $$$
solving X in polynomial time. Moreover, the proof of the previous theorem provides a method to construct such a family.
Concerning the role of the environment in tissue P systems with cell separation, in Ref. Reference Macías, Pérez-Jiménez, Riscos-Núñez and Rius-Font26 it is shown that only tractable problems can be solved efficiently by using tissue P systems with communication rules, separation rules and without environment. That is, the following holds.
Theorem 9. For each k ≥ 1 we have 
$$${\bf {{PMC}}}{{\,}_{\overline{{TSC}} (k)}} = {\bf {{P}}}$$$
.
From this theorem we deduce that the environment is relevant for the efficiency of tissue P systems with cell separation.
Remark 6. From Theorem 9 and Proposition 10, we deduce that in the framework of recognizer tissue P systems with cell separation and communication rules with length at most 3, passing from having an environment to not having it amounts to passing from efficiency to non-efficiency, assuming that P ≠ NP.
Remark 7. Bearing in mind that NP-complete problems can be efficiently solved by using tissue P systems with cell division and without environment, we deduce that in the framework of tissue P systems without environment, the kind of rules (separation versus division) provides a new frontier of the tractability of decision problems, assuming that P ≠ NP.
5. Conclusions
In this paper, a computational complexity in the membrane computing field has been presented. Assuming that P ≠ NP, different boundaries of the efficiency have been described in terms of syntactical ingredients of membrane systems. Each of them provide new tools to attack the P ≠ NP conjecture. Specifically, in the framework of membrane systems, the following ingredients provide new borderlines of the efficiency of computing models.
• The use of division rules in P systems with active membranes.
• The use of dissolution rules in polarizationless P systems with active membranes.
• The length of communication rules (passing from 1 to 2) in tissue P systems with cell division.
• The length of communication rules (passing from 2 to 3) in tissue P systems with cell separation.
• The use of cell division (or cell separation) rules in basic tissue P systems.
• The use of the environment in tissue P systems with cell separation.
It is worth highlighting that each one of the frontiers just mentioned can be seen as a new tool to attack the P versus NP conjecture, in the sense indicated in Corollary 1.
Mario J. Pérez-Jiménez received a BSc degree in Mathematics from Barcelona University, Spain, in 1971, and currently is a full Professor in the Department of Computer Science and Artificial Intelligence at the University of Seville. His research interests include the theory of computation, computational complexity theory, natural computing, bioinformatics, and computational modelling for systems biology and population biology. Some years ago, he was a Guest Professor of the Huazhong University of Science and Technology, Wuhan, China (2005–2007). He is member of the Academia Europaea, the European Molecular Computing Consortium, the Board of Directors at the Foundation for the Research and Development of Technology in Andalusia as well as a member of the Institute of Mathematics of the University of Seville. He was the first scientist to receive an award for ‘Important Contributions to Membrane Computing’ under the auspices of the European Molecular Computing Consortium (Edinburgh 2008). Nowadays, he is a member of the Editorial Board of four ISI journals. From 2003 on, he has been an expert-reviewer of the Prospective and Evaluation National Agency of Spain. In addition, he has been an independent expert to the evaluation of NEST (New and Emergent Science and Technology) proposals under the Sixth Framework Programme of the European Community, and, from May 2006 onwards, he has been a European Science Foundation peer reviewer.
