# From NP-Completeness to DP-Completeness: A Membrane Computing Perspective

Authors: Luis Valencia-Cabrera; David Orellana-Martín; Miguel Á. Martínez-del-Amor; Ignacio Pérez-Hurtado; Mario J. Pérez-Jiménez
Journal: Complexity
 (2020)

---

## Abstract

Presumably efficient computing models are characterized by their capability to provide polynomial-time solutions for NP-complete problems. Given a class ℛ of recognizer membrane systems, ℛ denotes the set of decision problems solvable by families from ℛ in polynomial time and in a uniform way. PMCℛ is closed under complement and under polynomial-time reduction. Therefore, if ℛ is a presumably efficient computing model of recognizer membrane systems, then NP ∪ co-NP ⊆ PMCℛ. In this paper, the lower bound NP ∪ co-NP for the time complexity class PMCℛ is improved for any presumably efficient computing model ℛ of recognizer membrane systems verifying some simple requirements. Specifically, it is shown that DP ∪ co-DP is a lower bound for such PMCℛ, where DP is the class of differences of any two languages in NP. Since NP ∪ co-NP ⊆ DP ∩ co-DP, this lower bound for PMCℛ delimits a thinner frontier than that with NP ∪ co-NP.


---

## Body

## 1. Introduction

Membrane Computing is a computing paradigm inspired by some basic biological features. Specifically, it is inspired by the structure and functioning of the living cells, as well as from the cooperation of cells in tissues, organs, and organisms. This paradigm provides distributed, parallel nondeterministic computing models whose computational devices are generically calledmembrane systems or P systems and has processing units called compartments. In this framework, there basically exist two ways to consider computational devices: cell-like membrane systems and tissue-like membrane systems. The former uses the biological membranes arranged hierarchically as compartments, inspired by the structure of the cell. The latter takes as compartments the cells placed in the nodes of a directed graph, which is inspired by the cell intercommunication in tissues.Recognizer membrane systems were introduced in [1], in order to provide a natural framework in Membrane Computing, aiming to solve decision problems by means of language recognition. A recognizer membrane system has the following additional syntactic and semantic peculiarities: (a) the working alphabet has two distinguished objects (yes and no); (b) there exist an input compartment, and there is also an input alphabet strictly contained in the working alphabet; (c) the initial content of each compartment is a multiset of objects from the working alphabet not belonging to the input alphabet; (d) all computations halt; and (e) for each computation and only at its last step, either object yes or object no (but not both) must have been released to the environment. Recognizer membrane systems can only have accepting or rejecting computations, depending on whether they return yes or no to the environment, respectively.On this basis, given a recognizer membrane systemΠ, for each multiset m over the input alphabet, we denote by Π+m the membrane system obtained from Π by adding the multiset m to the content of the input membrane at the initial configuration. Unlike a Turing machine, all the elements that make up a recognizer membrane system have a finite description. Therefore, while a decision problem (with infinite instances) can be solved by a single Turing machine, an infinite family of recognizer membrane systems is necessary to solve it. We say that a family Π=Πnn∈ℕ of recognizer membrane systems solves a decision problem X in polynomial time in a uniform way if such family Π can be generated by a deterministic Turing machine working in polynomial time, and there exists a pair cod,s of polynomial-time computable functions over the set of instances of X verifying the following: (a) for each instance u∈IX, su is a natural number and codu is an input multiset of the system Πsu; (b) for each n∈ℕ, the set s−1n is a finite set; and (c) the family Π is polynomially bounded, sound, and complete with regard to X,cod,s. The pair cod,s is called a polynomial encoding from the decision problem X to the family Π. For more details, see [2]. Given a computing model ℛ of recognizer membrane systems, PMCℛ denotes the set of decision problems solvable by families from ℛ in polynomial time in a uniform way. The class PMCℛ is closed under complement and under polynomial-time reduction [2].A computing model is said to beefficient (respectively, presumably efficient) if it has the ability to provide polynomial-time solutions for intractable problems (resp., NP-complete problems) [3]. The term presumably efficient refers to the fact that, as generally believed, if P ≠ NP then each NP-complete problem is intractable and, consequently, any presumably efficient model would be efficient. The computing model AM of recognizer P systems with active membranes and electrical charges is presumably efficient [4], as well as the computing model AM0+d,+ne of recognizer polarizationless P systems with active membranes which makes use of dissolution rules and division for elementary and nonelementary membranes [5]. However, the computing model AM0−d of recognizer polarizationless P systems with active membranes not making use of dissolution rules is not efficient, even when allowing division rules for elementary and nonelementary membranes [5]. Thus, if ℛ is a presumably efficient computing model of recognizer membrane systems, then NP ∪ co-NP ⊆ PMCℛ.Several variants of P systems have been demonstrated to be presumably efficient. A solution to QSAT has been given in the framework of P systems with active membranes and division rules for elementary and nonelementary membranes but only evolution rules of the RHS limited to length 1 [6]. When creation rules are used instead of division rules as a method of generating an exponential workspace in polynomial time, it is possible to get rid of polarizations to obtain a solution to the QSAT problem [7]. A new research line taking tissue P systems with symport/antiport rules where objects can evolve during the application of the rules has been developed recently. Several results have been obtained, and new solutions to NP-complete problems have been given in this framework [8].The main contribution of this paper is to provide a lower bound forPMCℛ delimiting a frontier with such class that is thinner to the one found with respect to NP ∪ co-NP, with ℛ being a presumably efficient computing model of recognizer membrane systems verifying some simple requirements (e.g., in the case of cell-like membrane systems, allowing object evolution rules, dissolution rules, and communication rules). It is also worth pointing out that the methodology used to obtain this result is constructive in the following sense: given an NP-complete problem X, a DP-complete problem YX is associated, in such a manner that if X∈PMCℛ then YX∈PMCℛ, for such kind of presumably efficient computing model ℛ of recognizer membrane systems.The remainder of this paper is structured as follows. Section2 will be devoted to introduce some concepts that can be useful to understand the rest of the work. The complexity class DP is introduced in Section 3, where the main theorem presented in this paper is established. In Section 4, the methodology will be applied with an example. Finally, in Section 5, the most relevant conclusions are drawn, and some possible further developments are outlined.


## 2. Preliminaries

In order for the paper to be self-contained, several basic concepts and results will be introduced to facilitate a better understanding of the text.Analphabet is a nonempty set whose elements are called symbols. A stringu over an alphabet is an ordered finite sequence of symbols. The length of a string u, denoted by u, is the number of occurrences of symbols that it contains. The empty string (with length 0) contains no symbols, and it is denoted by λ. The set of all strings over an alphabet Γ is denoted by Γ∗. A language over Γ is a subset of Γ∗. If L1,L2 are languages over Γ, the set-theoretic difference of L1 and L2 (in this order), denoted by L1⧹L2, is defined as follows: L1⧹L2=u∈Γ∗u∈L1∧u∉L2.Amultisetm over an alphabet Γ is a mapping from Γ onto the set ℕ of natural numbers. A multiset m over Γ is finite (respectively, empty) if the set x∈Γmx>0 is a finite (respectively, empty) set. If m,m′ are multisets over Γ, then the union of m and m′, denoted by m+m′, is the multiset over Γ defined as follows: m+m′x=mx+m′x, for each x∈Γ.


### 2.1. The Cantor Pairing Function

The Cantor pairing function is the mapping fromℕ×ℕ onto ℕ defined as follows: the natural number t1+t2⋅t1+t2+1/2+t1 is associated with every ordered pair t1,t2 of natural numbers. We denote it by t1,t2, that is, t1,t2=t1+t2⋅t1+t2+1/2+t1. The Cantor pairing function is a primitive recursive function and bijective from ℕ×ℕ onto ℕ. Consequently, for each natural number t, there exists a unique pair of natural numbers t1andt2 such that t=t1,t2.


### 2.2. Decision Problems and Languages

A decision problemX is an ordered pair IX,θX, where IX is a language over a finite alphabet ΣX and θX is a total Boolean function over IX. The elements of IX are called instances of the problem X. If θXu=1 (respectively, θXu=0) then we say that the answer of the problem for instance u is “yes” (respectively, “no”). Each decision problem X has associated a language LX over ΣX: the set of instances whose answer is “yes.” Conversely, every language L over an alphabet Σ has associated a decision problem whose set of instances is Σ∗, and for each u∈Σ∗ the answer of the problem is “yes” if and only if u∈L.Thecomplement problemX¯ of a decision problem X=IX,θX is the decision problem with the same set of instances, characterized by the following property. For each instance u∈IX, the answer of X¯ for u is “yes” if and only if the answer of X for u is “no.” Obviously, X¯¯=X. In accordance with this definition, a problem X is an NP-complete problem if and only if its complement problem X¯ is a co-NP-complete problem.


### 2.3. The Satisfiability Problem

Let us recall that the set of propositional Boolean variablesVP is a countably infinite set x1,x2,… such that each of their elements can take only two possible Boolean values (truth values) from 0,1. Boolean expressions are captured through the recursive definition of the minimal set BE verifying: (a) any propositional Boolean variable is in BE; (b) if φ is in BE then its negation ¬φ is also in BE; and (c) if φ1 and φ2 are in BE then its disjunction φ1∨φ2 is also in BE. Every Boolean expression φ has a finite number of Boolean variables associated with it, being denoted by Varφ. A truth assignment σ for a Boolean expression φ is a mapping from Varφ onto the set 0,1. According to the classical definition of truth tables for negation and disjunction, every truth assignment σ for a Boolean expression φ provides a unique Boolean value to it. If the associated truth value is 1, then it is said that σ makes the Boolean expression φ true.Aliteral is a Boolean variable or the negation of a Boolean variable. A clause is a finite disjunction of literals. Moreover, a Boolean expression is in conjunctive normal form if it is a finite conjunction of clauses. We say that a Boolean expression is in a simplified conjunctive normal form if it is in conjunctive normal form, literals are not repeated in each clause, and a literal and its negation do not appear in the same clause. We say that a Boolean expression φ is satisfiable if and only if there exists a truth assignment for φ making such an expression true. Let us recall that the satisfiability problem, denoted by SAT, is the problem of deciding whether a given Boolean formula in a simplified conjunctive normal form is satisfiable. The complement problem SAT¯ is denoted by UNSAT: determining whether or not a Boolean expression in a simplified conjunctive normal form is unsatisfiable. That is, given a Boolean expression φ in a simplified conjunctive normal form, determine whether any truth assignment σ for φ makes it false. It is well known that the SAT problem is an NP complete problem [9]. Thus, the UNSAT problem is a co-NP complete problem.


### 2.4. The Polynomial-Time Hierarchy and the Boolean Hierarchy

Let us recall that ifC is a time complexity class and A is an oracle (a set of queries) then CA is the class of all languages decidable by deterministic or nondeterministic Turing machines working in time bound as in C and having A as oracle (see [10], for details).Thepolynomial-time hierarchy was introduced by Stockmeyer [11], inspired by the Kleene arithmetical hierarchy [12], where recursive time is replaced by deterministic polynomial time. The polynomial-time hierarchy is a sequence of complexity classes defined as follows: Δ0P=Σ0P=Π0P=P and Δk+1P=PΣkP, Σk+1P=NPΣkP, and Πk+1P=co−NPΣkP, for each k∈ℕ. The first level of this hierarchy is Δ1P=P, Σ1P=NP, and Π1P = co-NP and the second level is Δ2P=PNP, Σ2P=NPNP, and Π2P = co-NPNP. The cumulative polynomial-time hierarchy is the class PH=∪k∈ℕΣkP.TheBoolean hierarchy is a sequence of complexity classes obtained from NP by means of Boolean operations (union, intersection, and complementation). It was defined in [13] as follows: NP0=P, and NP2k+1=L∪L′L∈NP2k∧L′∈NP, NP2k+2=L∩L′¯L∈NP2k+1∧L′∈NP, for each k∈ℕ. Sometimes, NPk sets are denoted by BHk. The first level of this hierarchy is NP and the second level is the set of languages which are intersections of a language in NP and another one in co-NP.


## 2.1. The Cantor Pairing Function

The Cantor pairing function is the mapping fromℕ×ℕ onto ℕ defined as follows: the natural number t1+t2⋅t1+t2+1/2+t1 is associated with every ordered pair t1,t2 of natural numbers. We denote it by t1,t2, that is, t1,t2=t1+t2⋅t1+t2+1/2+t1. The Cantor pairing function is a primitive recursive function and bijective from ℕ×ℕ onto ℕ. Consequently, for each natural number t, there exists a unique pair of natural numbers t1andt2 such that t=t1,t2.


## 2.2. Decision Problems and Languages

A decision problemX is an ordered pair IX,θX, where IX is a language over a finite alphabet ΣX and θX is a total Boolean function over IX. The elements of IX are called instances of the problem X. If θXu=1 (respectively, θXu=0) then we say that the answer of the problem for instance u is “yes” (respectively, “no”). Each decision problem X has associated a language LX over ΣX: the set of instances whose answer is “yes.” Conversely, every language L over an alphabet Σ has associated a decision problem whose set of instances is Σ∗, and for each u∈Σ∗ the answer of the problem is “yes” if and only if u∈L.Thecomplement problemX¯ of a decision problem X=IX,θX is the decision problem with the same set of instances, characterized by the following property. For each instance u∈IX, the answer of X¯ for u is “yes” if and only if the answer of X for u is “no.” Obviously, X¯¯=X. In accordance with this definition, a problem X is an NP-complete problem if and only if its complement problem X¯ is a co-NP-complete problem.


## 2.3. The Satisfiability Problem

Let us recall that the set of propositional Boolean variablesVP is a countably infinite set x1,x2,… such that each of their elements can take only two possible Boolean values (truth values) from 0,1. Boolean expressions are captured through the recursive definition of the minimal set BE verifying: (a) any propositional Boolean variable is in BE; (b) if φ is in BE then its negation ¬φ is also in BE; and (c) if φ1 and φ2 are in BE then its disjunction φ1∨φ2 is also in BE. Every Boolean expression φ has a finite number of Boolean variables associated with it, being denoted by Varφ. A truth assignment σ for a Boolean expression φ is a mapping from Varφ onto the set 0,1. According to the classical definition of truth tables for negation and disjunction, every truth assignment σ for a Boolean expression φ provides a unique Boolean value to it. If the associated truth value is 1, then it is said that σ makes the Boolean expression φ true.Aliteral is a Boolean variable or the negation of a Boolean variable. A clause is a finite disjunction of literals. Moreover, a Boolean expression is in conjunctive normal form if it is a finite conjunction of clauses. We say that a Boolean expression is in a simplified conjunctive normal form if it is in conjunctive normal form, literals are not repeated in each clause, and a literal and its negation do not appear in the same clause. We say that a Boolean expression φ is satisfiable if and only if there exists a truth assignment for φ making such an expression true. Let us recall that the satisfiability problem, denoted by SAT, is the problem of deciding whether a given Boolean formula in a simplified conjunctive normal form is satisfiable. The complement problem SAT¯ is denoted by UNSAT: determining whether or not a Boolean expression in a simplified conjunctive normal form is unsatisfiable. That is, given a Boolean expression φ in a simplified conjunctive normal form, determine whether any truth assignment σ for φ makes it false. It is well known that the SAT problem is an NP complete problem [9]. Thus, the UNSAT problem is a co-NP complete problem.


## 2.4. The Polynomial-Time Hierarchy and the Boolean Hierarchy

Let us recall that ifC is a time complexity class and A is an oracle (a set of queries) then CA is the class of all languages decidable by deterministic or nondeterministic Turing machines working in time bound as in C and having A as oracle (see [10], for details).Thepolynomial-time hierarchy was introduced by Stockmeyer [11], inspired by the Kleene arithmetical hierarchy [12], where recursive time is replaced by deterministic polynomial time. The polynomial-time hierarchy is a sequence of complexity classes defined as follows: Δ0P=Σ0P=Π0P=P and Δk+1P=PΣkP, Σk+1P=NPΣkP, and Πk+1P=co−NPΣkP, for each k∈ℕ. The first level of this hierarchy is Δ1P=P, Σ1P=NP, and Π1P = co-NP and the second level is Δ2P=PNP, Σ2P=NPNP, and Π2P = co-NPNP. The cumulative polynomial-time hierarchy is the class PH=∪k∈ℕΣkP.TheBoolean hierarchy is a sequence of complexity classes obtained from NP by means of Boolean operations (union, intersection, and complementation). It was defined in [13] as follows: NP0=P, and NP2k+1=L∪L′L∈NP2k∧L′∈NP, NP2k+2=L∩L′¯L∈NP2k+1∧L′∈NP, for each k∈ℕ. Sometimes, NPk sets are denoted by BHk. The first level of this hierarchy is NP and the second level is the set of languages which are intersections of a language in NP and another one in co-NP.


## 3. The Complexity Class DP

The complexity classDP was introduced by Papadimitriou and Yannakis in 1982 [14] as follows.Definition 1.
A languageL is in the class DP if and only if there are two languages L1 and L2 such that L1,L2∈NP and L=L1⧹L2.
The complexity classDP can be easily characterized by the following property: a language L is in DP if and only if there exist two languages L1 and L2 in NP such that L=L1∩L2¯. Class DP is the second level in the Boolean hierarchy. Besides, classes in the Boolean hierarchy can be described by finite unions of DP sets (or by finite intersections of co-DP sets). For more details, see [13, 15].
The complexity classDP can also be expressed in terms of decision problems as follows: a decision problem X is in class DP if and only if the language LX associated with it belongs to class DP, that is, if there are two decision problems X1=IX1,θX1 and X2=IX2,θX2 such that LX1andLX2 are languages in NP and LX=LX1∩LX2¯. It is easy to prove that NP ∪ co-NP ⊆ DP ∩ co-DP.
Next, we define theproduct of two decision problems, and some properties of the new concept are analyzed.Definition 2.
LetX1=IX1,θX1 and X2=IX2,θX2 be two decision problems. The product problem of X1 and X2, denoted by X1⊗X2, is the decision problem IX1⊗X2,θX1⊗X2 defined as follows: IX1⊗X2 = IX1×IX2, and for each u1,u2∈IX1⊗X2, we have θX1⊗X2u1,u2=1 if and only if θX1u1=1 and θX2u2=1.
A product problemYX can be naturally associated to a problem X. This problem YX is the product problem, defined as follows: YX=IYX,θYX such that IYX=uX,uX¯uX∈IX,uX¯∈IX¯, being X¯ the complementary problem of X; θYXu1,u2=1 if and only if θXu1=θX¯u2=1.
According to these definitions, the following results concerning to the product of two decision problems are obtained.Proposition 1.
LetX1andX2 be decision problems:(i)
IfX1∈NP and X2 ∈ co-NP, then X1⊗X2∈DP(ii)
IfX1 is an NP complete problem and X2 is a co-NP complete problem, then X1⊗X2 is a DP complete problem(iii)
IfX1 is an NP complete problem, then the product problem X1⊗X1¯ is a DP complete problem
Since the SAT problem is anNP complete problem, we deduce that the product problem SAT⊗SAT¯ is a DP complete problem. This problem is referred as the SAT-UNSAT problem [10] and can be expressed as follows: given two Boolean expressions φ1 and φ2 in simplified conjunctive normal forms, determine whether or not φ1 is satisfiable and φ2 is unsatisfiable.


## 4. The Methodology

The main result of this paper refers to the robustness of the complexity classPMCℛ associated with some computing models of recognizer membrane systems, with respect to the operation product of two decision problems.Main Theorem 1.
Letℛ be a computing model of recognizer noncooperative cell-like P systems allowing dissolution rules, object evolution rules, and communication rules (send-in and send-out). If X1 and X2 are decision problems belonging to the time complexity class PMCℛ, then X1⊗X2∈PMCℛ.Proof.
First, without loss of generality, we can assume that the semantics associated with the application of the rules of systems fromℛ is similar to P systems with active membranes, that is, at one transition step, a membrane can be a subject of only one rule of type dissolution, communication, or division, but object evolution rules are applied simultaneously with one of these rules and, moreover, in a maximal way. By using a different semantics, only few parameters that will appear in the proof should be modified.
Fori=1,2, let Πi=Πitt∈ℕ be a family of membrane systems from ℛ solving Xi in polynomial-time in a uniform way. Let codi,si be a polynomial encoding from Xi into Πi. Let pin be a polynomial function such that, for each instance ui from Xi, any computation of Πisiui+codiui performs at most piui steps. In this situation, a family Π=Πtt∈ℕ of membrane systems from ℛ will be defined from Π1 and Π2, in such a manner that Π provides a uniform and polynomial-time solution to the product problem X1⊗X2. The family Π will be called the product family of families Π1 and Π2, and it will be denoted by Π1⊗Π2.
First, a pair of polynomial-time functionscod,s over the set of instances of X1⊗X2 is considered as follows: (a) codu1,u2=cod1u1+cod2u2 and (b) su1,u2=s1u1,s2u2, for each u1,u2∈IX1⊗X2. Hence, we want the instance u1,u2 to be processed by the system Πsu1,u2 with input multiset codu1,u2. In the following, the membrane system Πs1u1,s2u2 will be explicitly defined from Π1s1u1 and Π2s2u2, for each u1,u2∈IX1⊗X2, so that (a) if there exist accepting computations of the systems Π1s1u1+cod1u1 and Π2s2u2+cod2u2, then θX1⊗X2=1 and (b) if θX1⊗X2=1, then any computation of Π1s1u1+cod1u1 and any computation of Π2s2u2+cod2u2 are accepting ones. According to this, cod,s will be a polynomial encoding from the product problem X1⊗X2 into the family Π. It is worth pointing out that, in fact, only membrane systems Πt such that t∈ranges are defined, and this is enough to achieve our goal.
In what follows, we will denotet=s1u1,s2u2, t1=s1u1, and t2=s2u2. Let us recall that given t∈ℕ, there exists a unique pair of natural numbers t1andt2 such that t=t1,t2. The underlying idea of the construction of Πt is the following: when codu1,u2 is considered as the input multiset of this system; then, computations of Π1t1+cod1u1 and Π2t2+cod2u2 are simulated. The answers of these systems are placed in a membrane where the final decision is taken; accepting computations of Πt+codu1,u2 only come from accepting computations of Π1t1+cod1u1 and Π2t2+cod2u2.
Without loss of generality we can assume thatΓiti\yes,no, for i=1,2, are mutually disjoint, being Γiti the working alphabet of Πiti. Likewise, without loss of generality, we can assume the same with the corresponding sets of labels H1t1 and H2t2. For 1≤i≤2, let qi be the maximum value of codiui such that siui=ti, and let di be the depth of the input membrane inΠiti of Πiti in the corresponding membrane structure. Let us denote mi=qi+di+2, for i=1,2, and n=2+maxdi+qi+piui:1≤i≤2. Systems Πiti+codiui will be “prepared” after mi+1 steps, and computations of such systems will start at the next step. It will last piui transition steps. Besides, it will take n steps to have both responses prepared to let Πt+codu1,u2 give the answer.
The syntactical ingredients ofΠt are the following:(i)
Input alphabet. The input alphabet is Σt=Σ1∗t1∪Σ2∗t2, being Σi∗ti the input alphabet of Πiti, by replacing objects yes and no by objects yesi and noi, for i=1,2, respectively.(ii)
Working alphabet. The working alphabet is(1)Γ1∗t∪Γ2∗t∪Γ3t∪Γ4t∪Γ5t∪Γ6t,where(2)Γ1∗t=Γ1t1∪yes,no∪yes1,no1,Γ2∗t=Γ2t2∪yes,no∪yes2,no2,Γ3t=#,YES,NO∪a′a∈Σt,Γ4t=aj0≤j≤m1∧a∈Γ1∗t∪aj0≤j≤m2∧a∈Γ2∗t,Γ5t=α0,α1∪βj0≤j≤n,Γ6t=γj0≤j≤maxm1,m2,that is, objectsa′∈Γ3tandaj∈Γ4t are “copies” of objects a∈Γ1t1∪Γ2t2, and objects in Γ5tandΓ6t are counters for implementing a synchronization process.(iii)
Set of labels. The set of labels Ht is H1t1∪H2t2∪rt,rt′,rt″,h1t1,h2t2, where rt,rt′,rt″,h1t1,h2t2 are different from each other, and rt,rt′,rt″,h1t1,h2t2∉H1t1∪H2t2.(iv)
Compartment structure. The membrane structure of Πt is obtained from the membrane structures μΠiti, for i=1,2, by adding four new nodes rt,rt′,h1t1,h2t2 such that (a) rt is the skin membrane of Πt; (b) rt is the father of rt′; (c) rt′ is the father of rt″; (d) rt″ is the father of the skin membranes rΠiti of Πiti, for i=1,2; and (e) hiti is a new son of the input membrane inΠiti of Πiti, for i=1,2. More specifically, the membrane structure of Πt is rt,rt′,rt′,rt″,rt″,rΠ1t1,rt″,rΠ2t2∪inΠ1t1,h1t1,inΠ2t2,h2t2∪μΠ1t1∪μΠ2t2. It is graphically depicted in Figure 1.(v)
Initial multisets. The initial multisets of Πt are the following: if h is the label of a membrane from Πiti whose initial multiset ℳhiti associated with h is nonempty, then the initial multiset ℳht of Πt is a “copy” of ℳhiti by replacing each symbol a by a0. Moreover, ℳrtt=ℳrt′t=∅,ℳrt″t=α0,β0 and ℳhitit=γ0, for i=1,2.(vi)
Set of rules. The set of rules is ℛΠ1t1∪ℛΠ2t2∪ℛt∗, where ℛΠiti is the set of rules of Πiti, for i=1,2, obtained through the replacement of objects yes and no by objects yesi and noi, respectively, in each rule. ℛt∗ is the following set of rules.(1)
Rules for simultaneously transportingcodiuifromrt″tohiti, fori=1,2and transforming it intocodiui′:(1.1)
arΠiti⟶a′rΠiti, for i=1,2 and for each a∈Σi∗ti.(1.2)
a′h⟶a′h, for each a∈Σt and each membrane h being either h=hiti or being h an ancestor of it.(2)
Rules for simultaneously transportingcodiui′fromhitito the input membraneinΠiti, by transforming it intocodiui, fori=1,2:(2.1)
γj⟶γj+1hiti, for 0≤j≤mi−1.(2.2)
γmihiti⟶#.(2.3)
a′⟶ahiti, for each a∈Σt.(3)
Rules for synchronizing the simulation ofΠiti+codiuiin order to start at themi+2th transition step, fori=1,2:(3.1)
aj⟶aj+1h, for each a∈Γt,0≤j≤mi−1,a0∈ℳh.(3.2)
ami⟶ah, for each a∈Γt,a0∈ℳh.(4)
Rules for synchronizing the instantn=2+maxdi+qi+piui:1≤i≤2in which the answers ofΠ1t1+cod1u1andΠ2t2+cod2u2reach the membranert″:(4.1)
βj⟶βj+1rt″, for 0≤j≤n−1.(5)
Rules for the output of the systemΠt+codu1,u2:(5.1)
βnrt″⟶#.(5.2)
noirt′⟶NO, for i=1,2.(5.3)
NOrt⟶nort.(5.4)
α0⟶α1rt′.(5.5)
α1rt′⟶YESrt′.(5.6)
YESrt⟶yesrt.


### 4.1. Input Membrane

The input membrane is the membrane labelled byrt″.An overview of the computations ofΠt+codu1,u2 is as follows.The proposed solution can be structured in the following stages.(i)
Transport stageIt consists of several phases: fori=1,2, in a simultaneous way, (a) the input multiset codiui is transported from the input membrane rt″ of Πt to the skin membrane rΠiti of Πiti, being transformed into the multiset codiui′ obtained from codiui by replacing each symbol a in codiui by a′; (b) then, codiui′ is transported from the skin membrane rΠiti to membrane htii; finally, (c) codiui′ moves from htii to the input membrane of Πiti, being transformed into codiui.(ii)
Simulation stageComputations of the systemΠiti with input multiset codiui are simulated, for i=1,2.(iii)
Output stageThe systemΠt with input multiset codu1,u2 sends the right answer to the environment according to the results obtained in the previous stage.


#### 4.1.1. Transport Stage

Once the input multisetcodu1,u2=cod1u1+cod2u2 is supplied to the system Πt, by applying the rules from 1.1, multiset codiui, for i=1,2, enters into membrane rΠiti transformed in codiui′. Next, by applying the rules from 1.2, multiset ui′ is transported to membrane htii. Then, multiset codiui′ is transported from membrane htii to the input membrane of Πiti being transformed in codiui, by dissolving the membrane htii (rule 2.2) and evolving objects a′ to objects a by applying the rules from 2.3. This process can be observed in a graphical way in Figure 1.Figure 1
Transport of objects fromrt″ to the corresponding inΠiti. For this purpose, rules from 1 and 2 are applied. Besides these rules, rules from 3 are applied to make the objects from ℳhi be available in their corresponding membranes only when objects from Σt are in their corresponding input membranes.It is worth pointing out that, in this process, we must prevent the rules ofΠiti from being applied. In order to do that rules from 3.1 handle copies aj of objects initially placed in membranes during mi transition steps, and rules from 3.2 transform those objects in objects a in order to be used in the simulation of Πiti+codiui. Consequently, at the configuration Cmi+1, the simulation of Πiti+codiui, for i=1,2, will start.


#### 4.1.2. Simulation Stage

The simulation ofΠiti+codiui starts at the (mi+2)th transition step. Then, after at most piui transition steps, an answer will be sent to the membrane rt′. Consequently, after at most n=2+maxdi+qi+piui:1≤i≤2 transition steps, systems Π1t1+cod1u1 and Π2t2+cod2u2 will send their responses to membrane rt″, where counter βj has been evolving from β0 to βn by applying rules from 4.1.


#### 4.1.3. Output Stage

At then+1th transition step, the membrane rt″ is dissolved by applying the rule 5.1. Then, membrane rt′ will contain objects α0,# along with the two answers (yesi and/or noi) provided by the simulations of Πiti+codiui, for i=1,2.Case 1.
Membranert′ from configuration Cn+1 contains at least an object noi. In this case, the answer must be negative. In fact, at the n+2th step, by applying rule 5.2 one object noi dissolves the membrane rt′ and evolves to object NO. Simultaneously, by applying the rule 5.4, object α0 evolves to object α1. Then, at configuration Cn+2 the skin membrane rt contains objects α1,#,NO and one object yesi or noi. Finally, at the next step, by applying the rule 5.3, object no is sent out of system. A graphical interpretation of this case is present in Figure 2.Figure 2
Negative answer. With rules from 4 and 5, an object no is sent to the environment in the last step of the computation.Case 2.
Membranert′ from configuration Cn+1 does not contain any object noi. In this case, the answer must be affirmative. In fact, at the n+2th step, by applying rule 5.4, object α0 evolves to α1 inside membrane rt′. Then, membrane rt′ from configuration Cn+2 will contain objects α1,#,yes1, and yes2. Next, by applying rule 5.5, object YES reaches membrane rt. Finally, an object yes is sent out to the environment by applying rule 5.6. A graphical interpretation of this case is present in Figure 3.Figure 3
Affirmative answer. With rules from 4 and 5, an object yes is sent to the environment in the last step of the computation.Remark 1.
Concerning to the proof of Theorem1, we would like to draw attention to two aspects: (a) recognizer membrane systems from class ℛ are required to allow the use of dissolution rules, object evolution rules, and communication rules (in both directions: send-in and send-out) and (b) an explicit solution of the product problem product is provided from two solutions of the problems involved in that operation.Corollary 1.
Letℛ be a presumably efficient computing model of recognizer cell-like P systems allowing dissolution rules, object evolution rules, and communication rules (send-in and send-out). Then, DP ∪ co-DP ⊆ PMCℛ.Proof.
It suffices to note that ifX is an NP complete problem such that X∈PMCℛ, then the product problem X⊗X¯ is a DP complete problem such that X⊗X¯∈PMCℛ. Since the complexity class PMCℛ is closed under complement and under polynomial-time reduction, DP ∪ co-DP ⊆ PMCℛ follows.


## 4.1. Input Membrane

The input membrane is the membrane labelled byrt″.An overview of the computations ofΠt+codu1,u2 is as follows.The proposed solution can be structured in the following stages.(i)
Transport stageIt consists of several phases: fori=1,2, in a simultaneous way, (a) the input multiset codiui is transported from the input membrane rt″ of Πt to the skin membrane rΠiti of Πiti, being transformed into the multiset codiui′ obtained from codiui by replacing each symbol a in codiui by a′; (b) then, codiui′ is transported from the skin membrane rΠiti to membrane htii; finally, (c) codiui′ moves from htii to the input membrane of Πiti, being transformed into codiui.(ii)
Simulation stageComputations of the systemΠiti with input multiset codiui are simulated, for i=1,2.(iii)
Output stageThe systemΠt with input multiset codu1,u2 sends the right answer to the environment according to the results obtained in the previous stage.


### 4.1.1. Transport Stage

Once the input multisetcodu1,u2=cod1u1+cod2u2 is supplied to the system Πt, by applying the rules from 1.1, multiset codiui, for i=1,2, enters into membrane rΠiti transformed in codiui′. Next, by applying the rules from 1.2, multiset ui′ is transported to membrane htii. Then, multiset codiui′ is transported from membrane htii to the input membrane of Πiti being transformed in codiui, by dissolving the membrane htii (rule 2.2) and evolving objects a′ to objects a by applying the rules from 2.3. This process can be observed in a graphical way in Figure 1.Figure 1
Transport of objects fromrt″ to the corresponding inΠiti. For this purpose, rules from 1 and 2 are applied. Besides these rules, rules from 3 are applied to make the objects from ℳhi be available in their corresponding membranes only when objects from Σt are in their corresponding input membranes.It is worth pointing out that, in this process, we must prevent the rules ofΠiti from being applied. In order to do that rules from 3.1 handle copies aj of objects initially placed in membranes during mi transition steps, and rules from 3.2 transform those objects in objects a in order to be used in the simulation of Πiti+codiui. Consequently, at the configuration Cmi+1, the simulation of Πiti+codiui, for i=1,2, will start.


### 4.1.2. Simulation Stage

The simulation ofΠiti+codiui starts at the (mi+2)th transition step. Then, after at most piui transition steps, an answer will be sent to the membrane rt′. Consequently, after at most n=2+maxdi+qi+piui:1≤i≤2 transition steps, systems Π1t1+cod1u1 and Π2t2+cod2u2 will send their responses to membrane rt″, where counter βj has been evolving from β0 to βn by applying rules from 4.1.


### 4.1.3. Output Stage

At then+1th transition step, the membrane rt″ is dissolved by applying the rule 5.1. Then, membrane rt′ will contain objects α0,# along with the two answers (yesi and/or noi) provided by the simulations of Πiti+codiui, for i=1,2.Case 1.
Membranert′ from configuration Cn+1 contains at least an object noi. In this case, the answer must be negative. In fact, at the n+2th step, by applying rule 5.2 one object noi dissolves the membrane rt′ and evolves to object NO. Simultaneously, by applying the rule 5.4, object α0 evolves to object α1. Then, at configuration Cn+2 the skin membrane rt contains objects α1,#,NO and one object yesi or noi. Finally, at the next step, by applying the rule 5.3, object no is sent out of system. A graphical interpretation of this case is present in Figure 2.Figure 2
Negative answer. With rules from 4 and 5, an object no is sent to the environment in the last step of the computation.Case 2.
Membranert′ from configuration Cn+1 does not contain any object noi. In this case, the answer must be affirmative. In fact, at the n+2th step, by applying rule 5.4, object α0 evolves to α1 inside membrane rt′. Then, membrane rt′ from configuration Cn+2 will contain objects α1,#,yes1, and yes2. Next, by applying rule 5.5, object YES reaches membrane rt. Finally, an object yes is sent out to the environment by applying rule 5.6. A graphical interpretation of this case is present in Figure 3.Figure 3
Affirmative answer. With rules from 4 and 5, an object yes is sent to the environment in the last step of the computation.Remark 1.
Concerning to the proof of Theorem1, we would like to draw attention to two aspects: (a) recognizer membrane systems from class ℛ are required to allow the use of dissolution rules, object evolution rules, and communication rules (in both directions: send-in and send-out) and (b) an explicit solution of the product problem product is provided from two solutions of the problems involved in that operation.Corollary 1.
Letℛ be a presumably efficient computing model of recognizer cell-like P systems allowing dissolution rules, object evolution rules, and communication rules (send-in and send-out). Then, DP ∪ co-DP ⊆ PMCℛ.Proof.
It suffices to note that ifX is an NP complete problem such that X∈PMCℛ, then the product problem X⊗X¯ is a DP complete problem such that X⊗X¯∈PMCℛ. Since the complexity class PMCℛ is closed under complement and under polynomial-time reduction, DP ∪ co-DP ⊆ PMCℛ follows.


## 4.1.1. Transport Stage

Once the input multisetcodu1,u2=cod1u1+cod2u2 is supplied to the system Πt, by applying the rules from 1.1, multiset codiui, for i=1,2, enters into membrane rΠiti transformed in codiui′. Next, by applying the rules from 1.2, multiset ui′ is transported to membrane htii. Then, multiset codiui′ is transported from membrane htii to the input membrane of Πiti being transformed in codiui, by dissolving the membrane htii (rule 2.2) and evolving objects a′ to objects a by applying the rules from 2.3. This process can be observed in a graphical way in Figure 1.Figure 1
Transport of objects fromrt″ to the corresponding inΠiti. For this purpose, rules from 1 and 2 are applied. Besides these rules, rules from 3 are applied to make the objects from ℳhi be available in their corresponding membranes only when objects from Σt are in their corresponding input membranes.It is worth pointing out that, in this process, we must prevent the rules ofΠiti from being applied. In order to do that rules from 3.1 handle copies aj of objects initially placed in membranes during mi transition steps, and rules from 3.2 transform those objects in objects a in order to be used in the simulation of Πiti+codiui. Consequently, at the configuration Cmi+1, the simulation of Πiti+codiui, for i=1,2, will start.


## 4.1.2. Simulation Stage

The simulation ofΠiti+codiui starts at the (mi+2)th transition step. Then, after at most piui transition steps, an answer will be sent to the membrane rt′. Consequently, after at most n=2+maxdi+qi+piui:1≤i≤2 transition steps, systems Π1t1+cod1u1 and Π2t2+cod2u2 will send their responses to membrane rt″, where counter βj has been evolving from β0 to βn by applying rules from 4.1.


## 4.1.3. Output Stage

At then+1th transition step, the membrane rt″ is dissolved by applying the rule 5.1. Then, membrane rt′ will contain objects α0,# along with the two answers (yesi and/or noi) provided by the simulations of Πiti+codiui, for i=1,2.Case 1.
Membranert′ from configuration Cn+1 contains at least an object noi. In this case, the answer must be negative. In fact, at the n+2th step, by applying rule 5.2 one object noi dissolves the membrane rt′ and evolves to object NO. Simultaneously, by applying the rule 5.4, object α0 evolves to object α1. Then, at configuration Cn+2 the skin membrane rt contains objects α1,#,NO and one object yesi or noi. Finally, at the next step, by applying the rule 5.3, object no is sent out of system. A graphical interpretation of this case is present in Figure 2.Figure 2
Negative answer. With rules from 4 and 5, an object no is sent to the environment in the last step of the computation.Case 2.
Membranert′ from configuration Cn+1 does not contain any object noi. In this case, the answer must be affirmative. In fact, at the n+2th step, by applying rule 5.4, object α0 evolves to α1 inside membrane rt′. Then, membrane rt′ from configuration Cn+2 will contain objects α1,#,yes1, and yes2. Next, by applying rule 5.5, object YES reaches membrane rt. Finally, an object yes is sent out to the environment by applying rule 5.6. A graphical interpretation of this case is present in Figure 3.Figure 3
Affirmative answer. With rules from 4 and 5, an object yes is sent to the environment in the last step of the computation.Remark 1.
Concerning to the proof of Theorem1, we would like to draw attention to two aspects: (a) recognizer membrane systems from class ℛ are required to allow the use of dissolution rules, object evolution rules, and communication rules (in both directions: send-in and send-out) and (b) an explicit solution of the product problem product is provided from two solutions of the problems involved in that operation.Corollary 1.
Letℛ be a presumably efficient computing model of recognizer cell-like P systems allowing dissolution rules, object evolution rules, and communication rules (send-in and send-out). Then, DP ∪ co-DP ⊆ PMCℛ.Proof.
It suffices to note that ifX is an NP complete problem such that X∈PMCℛ, then the product problem X⊗X¯ is a DP complete problem such that X⊗X¯∈PMCℛ. Since the complexity class PMCℛ is closed under complement and under polynomial-time reduction, DP ∪ co-DP ⊆ PMCℛ follows.


## 5. Applying the Methodology to MAJORITY

In this section, we detail the application of the methodology through a simple example. For the sake of simplicity, a simple problemX will be selected so the focus can be on the application of the problem. The application of the methodology to an NP-complete problem will be applied in [16].LetMfA be the set of all finite multisets over A, and let fux be the number of appearances of symbol x in the multiset u. Let sizeu be the number of elements of u.LetX=IX,θX be the MAJORITY problem. Let IX=xx∈Mf0,1 and θXu=1 if and only if fu1>fu0, that is, if fu1≥1+n/2.A uniform family of polarizationless P systems with dissolution rules can be designed for this purpose (the MAJORITY problem falls under the classP; therefore, it could be enough to use the cod function to encode the input as yes in the affirmative case and no in the negative case, but for the application of the methodology, we will make that codu will encode a 1 as an object t and a 0 as an object f).Letn>0 be the number of elements of the input instance. We define the recognizer polarizationless P system with dissolution rules:(3)Πn=Γ,Σ,μ,ℳ1,…,ℳ3+n/2,ℛ,iin,iout,where(1)
Γ=Σ∪yes,no,y,#∪dk0≤k≤3+n/2.(2)
Σ=f,t.(3)
μ=…3+n/2…32]1.(4)
ℳ3+n/2=y,ℳ2=d0,ℳi=∅,i∉2,3+n/2.(5)
The setℛ of rules is formed by the following rules:(a)
These rules will carry the objecty to the membrane labelled by 1 if and only if there are at least 1+n/2 objects 1:(4)ti⟶#,for3≤i≤3+n2.(b)
These rules will make the objectn0 evolve to nn/2+2:(5)dk⟶dk+12,for0≤k≤2+n2.(c)
Rules for returningyes if object y has arrived the membrane labelled by 1 in the configuration n/2+1:(6)y2⟶y2,y2⟶yes,yes1⟶yes1.(d)
Rules for returning an objectno in case the object y is not in membrane 1 in configuration n/2:(7)dn/2+22⟶no2,no1⟶no1.(6)
iin=2+⌈n/2⌉ and iout=env.The system works are as follows: the instance is introduced in the input membrane as a multiset of objectst and f (codu will encode a 1 as an object t and a 0 as an object f). Objects t will start dissolving membranes starting from the membrane labelled by ⌈n/2⌉ to the membrane labelled by 3. If there are enough objects t (that is, if there is a majority of 1 in the instance), then object y will be in the membrane labelled by 1 in configuration Cn/2+1. Therefore, object y will go into membrane 2 and will dissolve it, avoiding object d⌈n/2⌉+3 evolving into an object no. While dissolving, object y will be transformed into an object yes, that will go to the environment in the last step of the computation. If object y is not present in the membrane 1, then object d3+⌈n/2⌉ will be transported to membrane 1 as an object no in the membrane 1 and will be sent to the environment in the last step of the computation. The system will take 5+⌈n/2⌉ steps in the affirmative case, and 6+⌈n/2⌉ steps in the negative case. With this solution to the MAJORITY problem, we can proceed to apply the methodology.LetMAJORITY¯ be the complementary problem of MAJORITY, that is, IMAJORITY¯=IMAJORITY and θMAJORITY¯u=1−θMAJORITYu. A solution to this problem could be given simply changing the role of objects yes and no.Let(8)Π1n=Γ1,Σ1,μ1,ℳ11,…,ℳ3+n/21,ℛ1,iin1,iout1,be recognizer polarizationless P systems with dissolution rules that solves the instances of MAJORITY of size n as described above. We can define a recognizer polarizationless P system with dissolution rules:(9)Π2n=Γ2,Σ2,μ2,ℳ4+n1/22,…,ℳ6+n1/2+n2/22,ℛ2,iin2,iout2,which solves the instances of MAJORITY¯ of size n as follows. For doing Γini disjoint, Γ2t2 will consist on the symbols from Γ1t1 in capital letters. All the rules are changed according to this. To make H1 and H2 disjoint, given n1,n2>0, we change the label i of H2 to 3+n1/2+i. In Πi, we change objects yes and no by yesi and noi, respectively.From here, we are going to define P system that will solve the problemMAJORITY⊗MAJORITY¯, which is defined as follows. Let u1,u2∈Mf0,1.θMAJORITY⊗MAJORITY¯u1,u2=1 if and only if θMAJORITYu1=1 and θMAJORITY¯u2=1. Let codu1,u2=cod1u1+cod2u2. Let ti=sizeui, and t=t1,t2. Let qi=ti and di=3+ti/2. Let piui=6+ti/2. Let mi=qi+di+2=ti+4+ti/2 and n=maxdi+qi+piui=maxt1+8+2⋅t1/2,t2+8+2⋅t2/2. We define a recognizer polarizationless P system with dissolution rules:(10)Πt=Γ,Σ,μ,ℳ1,…,ℳ6+t1/2+t2/2,ℳrt,ℳr′t,ℳr″t,ℳh1t1,ℳh2t2,ℛ,iin,iout,where(i)
Γ=Γ1∗t∪Γ2∗t∪Γ3t∪Γ4t∪Γ5t∪Γ6t, where(11)Γ1∗t=Σ1t1∪yes1,no1,y,#∪dk0≤k≤3+t12,Γ2∗t=Σ2t2∪yes2,no2,Y,#∪Dk0≤k≤3+t22,Γ3t=#,YES,NO∪t′,f′,T′,F′,Γ4t=yes1j,no1j,yj0≤j≤m1∪dkj0≤k≤3+t12,0≤j≤m1∪yes2j,no2j,Yj0≤j≤m2∪Dkj0≤k≤3+t12,0≤j≤m2∪,Γ5t=α0,α1∪βj0≤j≤n,Γ6t=γj0≤j≤maxm1,m2.(ii)
Σt=Σ1t1∪Σ2t2, being Σ1t1=t,f and Σ2t2=T,F.(iii)
Ht=H1∪H2∪rt,rt′,rt″,h1t1,h2t2, wherert,rt′,rt″,h1t1,h2t2 are different from each other, and(12)rt,rt′,rt″,h1t1,h2t2∉H1∪H2.(iv)
μ=μ=…h1t13+t1/2…1…h2t26+⌈t1/2⌉+t2/2…4+t1/2trt″rt′rt.(v)
ℳ3+t1/2=y0,ℳ6+t1/2+t2/2=Y0,ℳ2=d00,ℳ2+t1/2=D00,ℳrt″t=α0,β0 and ℳhitit=γ0, for i=1,2 and ℳj=∅ for the rest of membranes.(vi)
Set of rules. The set of rules is ℛΠ1t1∪ℛΠ2t2∪ℛt∗, where ℛΠiti is the set of rules of Πiti, for i=1,2, obtained through the replacement of objects yes and no by objects yesi and noi, respectively, in each rule. ℛt∗ is the following set of rules:(1)
Rules for simultaneously transportingcodiui from rt″ to hiti, for i=1,2 and transforming it into codiui′:(13)a1⟶a′1A4+t1/2⟶A′4+t1/2,fora∈t,f,A∈T,F,a′i⟶a′1a′h1t1⟶a′h1t1A′j⟶A′jA′h2t2⟶A′h2t2,fora∈t,f,3≤i≤3+n12,A∈T,F,6+n12≤j≤+n22,(2)
Rules for simultaneously transportingcodiui′fromhitito the input membraneinΠiti, by transforming it intocodiui, fori=1,2: (14)γj→γj+1hiti,fori∈1,2,0≤j≤mi−1,γmihiti⟶#,fori∈1,2,a′⟶ah1t1A′⟶Ah2t2,fora∈t,f,A∈T,F.(3)
Rules for synchronizing the simulation ofΠiti+codiuiin order to start at themi+2th transition step, fori=1,2,(15)d0→d0j+12,yi→yj+13+t1+2,for0≤j≤m1,D0j→D0j+12t1+2,Yi→Yj+16+t1+2+t2+2,for0≤h≤m2,d0m1→d02,D0m2→D02+t1+2,ym1→y3+t1+2,Ym2→Y6+t1+2+t2/2.(4)
Rules for synchronizing the instann=2+maxdi+qi+piui:1≤i≤2. in which the answers ofΠ1t1+cod1u1andΠ2t2+cod2u2reach the membranert″: βj⟶βj+1rt″, for0≤j≤n−1.(5)
Rules for the output of the systemΠt+codu1,u2:(16)βnrt″⟶#noirt′⟶NOα0⟶α1rt′α1rt′⟶YESrt′YESrt⟶yesrt,fori∈1,2,iin=rt″,iout=env.This system will return an objectyes or an object no, but not both, only in the last step of the computation. The computation will take n+4 computational steps in the affirmative case and n+3 steps in the negative case.


## 6. Conclusions

Given a computing modelℛ of recognizer membrane systems with the ability to provide polynomial-time solutions to NP complete problems (presumably efficient computing model), the time complexity class PMCℛ contains the complexity classes NP and co-NP, since PMCℛ is closed under complement and under polynomial-time reductions [2]. In this paper, a lower bound thinner than NP ∪ co-NP is provided for the class PMCℛ associated with a presumably efficient computing model ℛ of recognizer P systems allowing object evolution rules, dissolution rules, and communication rules. Specifically, for such kind of computing models, the following result has been obtained: DP ∪ co-DP ⊆ PMCℛ, where DP is the set of languages which can be expressed as the difference of two languages in NP or, equivalently, as the intersection of a language in NP and a language in co-NP.In this paper, we have applied the methodology to the MAJORITY problem. We have chosen such a simple problem for the sake of simplicity. An efficient solution to the SAT-UNSAT problem, aDP-complete problem, is given in [16].In this research line, it would be interesting to analyze the possibility of extending the main theorem to other presumably efficient computing models of recognizer membrane systems; for instance, cooperative cell-like membrane systems without dissolution rules, tissue-like P systems with symport/antiport rules or spiking neural P systems.



---

*Source: 6765097-2020-08-30.xml*