Abstract
It is known that polarizationless P systems with active membranes can solve \(\mathrm {PSPACE}\)complete problems in polynomial time without using incommunication rules but using the classical (also called strong) nonelementary membrane division rules. In this paper, we show that this holds also when incommunication rules are allowed but strong nonelementary division rules are replaced with weak nonelementary division rules, a type of rule which is an extension of elementary membrane divisions to nonelementary membranes. Since it is known that without incommunication rules, these P systems can solve in polynomial time only problems in \(\mathrm {P}^{\text {NP}}\), our result proves that these rules serve as a borderline between \(\mathrm {P}^{\text {NP}}\) and \(\mathrm {PSPACE}\) concerning the computational power of these P systems.
Introduction
The investigation of the computational power of variants of P systems with active membranes [26] is a widely studied research area in membrane computing. It is well known that these P systems can solve \(\mathrm {PSPACE}\)complete problems in polynomial time if they can use nonelementary membrane division rules of the form \([[\,\,]^+_{h_1}[\,\,]^_{h_2}]^0_{h_0}\rightarrow [[\,\,]^+_{h_1}]^0_{h_0}[[\,\,]^_{h_2}]^0_{h_0}\), where \(h_0\), \(h_1\), and \(h_2\) are labels of the membranes [3, 31]. Following the literature, we call these rules strong nonelementary membrane division rules in this paper. It is also known that P systems with active membranes can solve \(\mathrm {NP}\)complete problems in polynomial time without employing any nonelementary membrane division rules [12, 26, 35]. Solving \(\mathrm {NP}\)complete problems by P systems with active membranes has a huge literature in membrane computing (from now on, by a solution we mean a polynomialtime solution). The \(\mathrm {NP}\)complete SAT problem, i.e., the satisfiability problem of Boolean formulas was solved, for example, without polarizations but using membrane label changing [4] or using separation rules instead of division rules [23, 24]. In [7], the authors solved SAT using a method different from the one commonly used in the literature (see also [5, 6]). In fact, it is known that P systems with active membrane employing no nonelementary membrane division rules characterise the complexity class \(\mathrm{P}^{{\#\text {P}}}\), that is, the class of all problems solved by polynomialtime deterministic Turing machines with polynomialtime counting oracles [13]. We note here that in [17], the authors presented a characterization of \(\mathrm {PSPACE}\) by P systems employing no nonelementary membrane division rules, but the P systems used there were nonconfluent (i.e., strongly nondeterministic). In this paper, we consider only confluent P systems.
It is also known that without any membrane division rules, P systems with active membranes can solve only problems in P [35]. It is natural to ask what components other than membrane division rules are necessary for these P systems to solve computationally hard problems. Păun conjectured already in 2005 that P systems without nonelementary membrane division rules can solve only problems in P if we remove the polarizations of the membranes [25]. So far, this conjecture was confirmed only in some special cases, for example, when dissolution rules are not used [11], when the division rules are symmetric [18], or when dissolution and elementary membrane division rules are allowed but both the use of other types of rules and the initial membrane structure are restricted [9, 15, 34]. The aim to prove Păun’s conjecture initiated a research line in membrane computing where the computational power of restricted variants of polarizationless P systems is investigated (see, e.g., [19,20,21], where these P systems with no dissolution rules were studied and [8], where it is shown that these systems can simulate Turing machines efficiently using only evolution and dissolution rules). For a recent survey on exploring the boundary between \(\mathrm {P}\) and \(\mathrm {NP}\) in terms of membrane computing, see, e.g., [22].
Polarization, on the other hand, is known to be not necessary to solve computationally hard problems when the use of nonelementary membrane division rules is allowed. For example, the \(\mathrm {PSPACE}\)complete QSAT problem (QSAT is the problem of deciding if a fully quantified Boolean formula is true or not) was solved in [1] without using polarizations. In fact, the construction presented in [1] does not employ incommunication rules either, and outcommunication rules are used only in the last step of the computation to send the answer of the system out to the environment. Moreover, the employed strong nonelementary membrane division rules are also restricted as they have the form \([[\,\,]_{h_1}[\,\,]_{h_1}]_{h_0}\rightarrow [[\,\,]_{h_1}]_{h_0}[[\,\,]_{h_1}]_{h_0}\), that is, the inner membranes in the lefthand side of these rules have the same labels.
It is known [11] that dissolution rules are necessary to solve QSAT in the P systems considered in [1]. To the best of our knowledge, it is still open whether evolution rules are necessary, too. Notice that in [1], the evolution rules had an essential role in selecting those clauses of the input formula that are satisfied by a truth assignment of the variables. Although dissolution and elementary membrane division rules can evolve objects, it is not clear how they could be used to take over the roles of evolution rules in [1].
In [16], the Q3SAT problem, a \(\mathrm {PSPACE}\)complete restriction of QSAT was solved with polarizationless P systems using no evolution and communication rules. The presented P systems used however not only strong nonelementary membrane division rules, but socalled weak division rules for nonelementary membranes. These rules are in fact generalisations of the wellknown elementary membrane division rules to nonelementary membranes and thus have the form \([a]^{e_0}_h\rightarrow [b]^{e_1}_h[c]^{e_2}_h\), where \(e_0,\,e_1,\,e_2\) are polarizations (see also [2, 36], where the space complexity of P systems employing weak nonelementary membrane division rules is discussed). Let us note here that, to the best of our knowledge, it is not known whether weak nonelementary membrane division rules are indeed weaker than strong nonelementary membrane division rules. More precisely, it is not known whether we can find a set C of types of active membrane rules containing weak nonelementary membrane divisions but excluding strong divisions such that polynomialtime P systems using rules of types in C can decide presumably less problems than those P systems that can use strong division rules in addition to rules of types in C.
Recently, monodirectional P systems were introduced and investigated [14]. These are P systems with active membranes that have no incommunication rules and have weak nonelementary membrane division rules instead of the strong ones. It is easy to see that in these P systems the information can flow only towards the skin membrane. It turned out in [14] that this syntactical restriction is enough to restrict the computational power of these P systems. More precisely, it was shown in [14] that monodirectional P systems working in polynomial time characterize the class \(\mathrm {P}^{\text {NP}}\), that is, the class of problems solved by polynomialtime Turing machines with NP oracles. Interestingly, it turned out also that removing weak nonelementary membrane division rules or dissolution rules does not affect the computational power of these P systems. On the other hand, if both of these rules are removed, then the P systems characterise only \(\mathrm {P}_{\parallel }^{\text {NP}}\). For a recent survey on the relation of classical complexity classes beyond \(\mathrm {NP}\) and classes of problems solvable by various families of P systems with active membranes, see [32].
In this paper, we show that weak nonelementary membrane division is enough to solve \(\mathrm {PSPACE}\)complete problems in polarizationless P systems if dissolution and incommunication rules are allowed. More precisely, we show that the QSAT problem can be solved with polarizationless P systems with active membranes where the applicable types of rules are weak nonelementary membrane division, dissolution, and incommunication. As we will not use outcommunication rules, the answer of the system will appear in the skin membrane in the last step of the computation. All types of rules used in our P systems are presumably necessary to solve the QSAT problem. Indeed, as we have already discussed, without incommunication, dissolution, or weak nonelementary division these systems can solve presumably less problems due to [11], [14], and [35], respectively (notice that although in [11] the P systems employ strong nonelementary membrane divisions, their result can easily be adopted to those P systems which have weak nonelementary divisions instead of the strong ones).
Our proof resembles the one given in [1]. That solution of QSAT first builds a binary tree of membranes starting from a linearly nested membrane structure. Each elementary membrane in this tree corresponds to a truth assignment of the variables of the input. Our solution builds a similar tree of membranes, but a truth assignment is associated with a set of elementary membranes instead of one. However, in [1], this binary tree is built in a bottom–up manner, that is, the strong nonelementary division rules divide the innermost membrane first and the division is propagated towards the skin membrane. Meanwhile, the mentioned truth assignments are created using elementary membrane division rules, that is, they appear at the leaves of the created binary tree. On the other hand, the weak nonelementary division rules used in our paper create a binary tree of the membranes in a top–down manner: first, one of the upper membranes of the tree is divided and the division continues towards the elementary membranes. The weak nonelementary divisions are used to create the objects representing the truth assignments as well. These objects then are sent to the elementary membranes using incommunication rules. This means that incommunication rules play an important role in our result. In fact, as we have discussed above, QSAT cannot be solved without incommunication rules with our P systems unless \(\mathrm {PSPACE}=\text {P}^{\text {NP}}\).
The rest of the paper is organised as follows. In the next section, we present the necessary notions and notations. Then, in Sect. 3, we give the main result of the paper. In Sect. 4, we give some concluding remarks.
Preliminaries
Here, we recall the necessary notions used in the paper. However, we assume that the reader is familiar with the basic concepts of formal language theory, propositional logic, and membrane computing techniques (for a comprehensive guide to these topics, see e.g. [10, 27, 30], respectively). We denote by \(\mathbb {N}\) the set of natural numbers including zero. For \(n,i\in \mathbb {N}\) with \(0\le i\le n\), [i, n] denotes the set \(\{i,i+1,\ldots , n\}\), and we use the notation [n] for the set [1, n].
P systems and membrane configurations. In this paper, we examine polarizationless P systems with active membranes, that is, such P systems where no electrical charge is associated with any membrane. Before giving a formal definition of these P systems, we define first membrane configurations based on the notion of membrane structures. Intuitively, a membrane structure consists of membranes hierarchically embedded in the outermost membrane, called the skin membrane, and membranes delimit regions. Let O be an alphabet of objects and H be a finite set of membrane labels. We assume that H always contains the special label \(\mathsf {skin}\). Formally, a membrane structure is a triple (V, E, L) where (V, E) is a nonempty, finite, rooted, directed tree (with its edges directed towards the root) and \(L:V\rightarrow H\) assigns labels to each node, such that only the root is labeled by the symbol \(\mathsf {skin}\), and it has to be labeled by \(\mathsf {skin}\). Nodes are called membranes of the structure. A membrane \(x\in V\) with label \(\ell\) is called an \(\ell\)membrane. We can assume that initially, each membrane has its unique label. A membrane that has only an outgoing edge is called an elementary membrane.
A membrane configuration is a tuple \((V,E,L,\omega )\), where (V, E, L) is a membrane structure and \(\omega :V\rightarrow O^*\) is a function which assigns a finite word of objects to each membrane. We view these words as multisets of O. The empty word is denoted by \(\varepsilon\). If \(x\) is a membrane and \(a\in \omega (x)\), then we say that the region of \(x\) contains \(a\), or just that x contains a. Let \(C=(V,E,L,\omega )\) be a membrane configuration. The membrane configuration \(C'=(V',E',L',\omega ')\) is a subconfiguration of C if \((V',E')\) is a subtree of \((V,E)\), and \(L'\) and \(\omega '\) are restrictions of L and \(\omega\) to \(V'\), respectively.
A polarizationless P system with active membranes is a construct of the form \(\varPi =(O,H,\mu ,R)\), where O is the alphabet of objects, H is a finite set of membrane labels, \(\mu =(V,E,L,\omega )\) is the initial membrane configuration with L and \(\omega\) mapping nodes of \(\mu\) to H and \(O^*\), respectively, and R is a finite set of rules. We allow the following types of rules:

(a)
\([a \rightarrow v]_h\), for some \(h \in H, a\in O, v \in O^*\) (object evolution rules);

(b)
\(a[\,\,\,]_h \rightarrow [b]_h\), for some \(h\in H\), \(a,b\in O\) (incommunication rules);

(c)
\([a]_h\rightarrow [\,\,\,]_hb\), for some \(h\in H\), \(a,b \in O\) (outcommunication rules);

(d)
\([a]_h\rightarrow b\), for some \(h \in H\), \(a,b \in O\) (membrane dissolving rules);

(e)
\([a]_h\rightarrow [b]_h [c]_{h}\), for some \(h\in H\), \(a, b, c \in O\) (weak division rules for elementary or nonelementary membranes).
Rules of type (e) are generalisations of the classical elementary membrane division rules to nonelementary membranes with the following semantics. Consider a membrane configuration \(C=(V,E,L,\omega )\), a rule r of type (e), and an edge \((x,y)\in E\) such that x is a subject of r (that is, \(L(x)=h\)) and \(a\in \omega (x)\). Let \((V',E')\) be that subtree of (V, E) which has x as the root. The application of r to x duplicates the subtree \((V', E')\) into two disjoint trees \((V_1',E_1')\) and \((V_2',E_2')\) with roots \(x_1\) and \(x_2\), respectively, and replaces the edge (x, y) with edges \((x_1,y)\) and \((x_2,y)\). Each node n of \(V_1'\) (resp. of \(V_2'\)) is associated with the same label as that of the corresponding node in \(V'\). Moreover, \(x_1\) (resp. \(x_2\)) is associated with \((\omega (x)\{a\})\cup \{b\}\) (resp. with \((\omega (x)\{a\})\cup \{c\}\)), and the rest of the nodes in \(V'_1\) (resp. in \(V'_2\)) are associated with the same object multiset as that of the corresponding node in \(V'\).
As it is usual in membrane computing, P systems with active membranes work in a maximally parallel manner: at each step, the system first nondeterministically assigns appropriate rules to the occurrences of objects of the current membrane configuration such that the assigned multiset S of rules satisfies the following properties: (i) at most one rule from S is assigned to any occurrence of an object in the membrane configuration, (ii) a membrane can be the subject of at most one rule of types (b)–(e) in S, and (iii) S is maximal among the multisets of rules satisfying (i) and (ii). Then, the rules in S are applied in the usual bottom–up manner during the computation step: when a weak division rule is applied to a membrane x, then all the rules assigned to the objects in the subtree with root x are assumed to be applied already.
Uniform families of recognizer P systems. Recognizer P systems [28, 29] were introduced to provide a framework to be able to consider P systems as deciders of decision problems.
Definition 1
A P system \(\varPi\) is a recognizer P system if it satisfies the following properties:

1.
\(\varPi\) has a designated input membrane,

2.
the alphabet of objects has two designated elements yes and no,

3.
all computations of \(\varPi\) halt, and

4.
each computation of \(\varPi\) must send out to the environment the output of the system which is either yes or no (but not both), and these objects are produced exactly in the last step of the computation.
Recognizer P systems, being nondeterministic computation models, can have different computations with different output on the same input. However, to use them as deciders, confluent recognizer P systems are usually considered. In these P systems all halting computations on the same input must produce the same output.
Decision problems in membrane computing are usually solved by polynomially uniform families of recognizer P systems. A family \(\mathbf {\varPi }=\{\varPi (n)\mid n\in \mathbb {N}\}\) of P systems is polynomially uniform if there is a polynomialtime deterministic Turing machine that computes \(\varPi (n)\) whenever it is started with \(1^n\), that is, with the unary representation of \(n\in \mathbb {N}\) on its input tape.
Let L be a decision problem and \(\mathbf {\varPi }=\{\varPi (n)\mid n\in \mathbb {N}\}\) be a polynomially uniform family of recognizer P systems. We say that \(\mathbf {\varPi }\) solves L in polynomial time if there is a polynomialtime computable encoding cod that transforms instances of L into multisets of objects and there exists an integer \(k\in \mathbb {N}\) such that the following holds. For every instance x of L with size n, each computation of \(\varPi (n)\) starting with cod(x) in its input membrane halts in at most \(n^k\) steps and sends out yes to the environment if and only if x is a positive instance of L.
In this paper, we will consider P systems with no outcommunication rules. Therefore, we alter Condition 4 in Definition 1 as follows:
4 each computation of \(\varPi\) must produce in the \(\mathsf {skin}\)membrane the output of the system which is either yes or no (but not both), and these objects are produced exactly in the last step of the computation.
The QSAT problem. In this paper, we are going to construct P systems that can decide if a Quantified Boolean formula (QBF) is true or not. QBFs extend propositional logic by allowing universal and existential quantifiers over propositional variables. It is assumed that each variable is under the bound of at most one quantifier. We consider fully quantified QBFs in prenex normal form, that is, in the form \(F=Q_1x_{1}\ldots Q_nx_{n}\varPhi (x_1,\ldots ,x_n)\), where \(n\ge 1\), \(Q_i\) (\(i\in [n]\)) is either \(\exists\) or \(\forall\), and \(\varPhi (x_1,\ldots ,x_n)\) is the quantifierfree part of F indicating that the variables of \(\varPhi\) are in \(\{x_1,\ldots , x_n\}\).
Let \(\varPhi (x_1,\ldots ,x_n)\) be a quantifierfree formula, \(i\in [n]\), and, for every \(j\in [i]\), \(v_j\in \{true, false\}\). Then \(\varPhi (v_1,\ldots ,v_i,x_{i+1},\ldots ,x_n)\) is that formula \(\varPhi '(x_{i+1},\ldots ,x_n)\) which we get from \(\varPhi\) by replacing, for every \(j\in [i]\), the variable \(x_j\) by \(v_j\). Clearly, the truth values true and false serve in \(\varPhi '\) as logical constants with the corresponding truth values.
In this paper, we consider the following PSPACEcomplete variant of the QSAT problem: the input is a fully quantified QBF
in prenex normal form, where \(n\ge 2\) and \(\varPhi\) is in conjunctive normal form. The task is to decide whether F is true or false. Clearly, F is true if and only if the following holds:
We will show that QSAT can be solved by polarizationless P systems with active membranes using only weak nonelementary division, incommunication and dissolution rules. Roughly, our P systems will implement a function \(\textsc{Eval}\) given in Algorithm 1 which is in fact a variant of the wellknown basic method of recursively evaluating Expression (1).
Results
This section is devoted to the proof of the main result of the paper which can be stated as follows:
Theorem 1
The QSAT problem can be solved in polynomial time by a polynomially uniform family \(\mathbf {\varPi }=\{\varPi (n,m)\mid n\ge 2,m\ge 1\}\) of polarizationless recognizer P systems with active membranes such that the members of \(\mathbf {\varPi }\) employ only rules of type (b), (d), and (e).
For \(n\ge 2\) and \(m\ge 1\), \(\text {QSAT}(n,m)\) denotes the set of those instances of \(\mathrm {QSAT}\) which have m clauses and variables in \(\{x_1,x_2,\ldots ,x_n\}\). We will use \(\varPi (n,m)\) to decide whether the instances of \(\mathrm {QSAT}(n,m)\) are true or not.
For the rest of this section, we fix an instance
of \(\text {QSAT}(n,m)\). Denote \(C_j\) \((j\in [m])\) the jth clause of \(\varPhi\). First, we define the encoding of F, denoted by cod(F), as a subset of \(\Sigma (n,m)=\{v_{i,j},v'_{i,j}\mid i\in [n], j\in [m]\}\) in the following way:
We now construct the P system \(\varPi (n,m)=(O,H,\mu ,R)\) as follows:

\(O=\{t_i,f_i,t'_i,f'_i,\hat{t_i},\hat{f_i}, \mid i\in [n]\}\cup \Sigma (n,m)\cup \{a,T,s,yes,no\},\)

\(H=\{x_i,x'_i,\alpha _i,\beta _i\mid i\in [n]\}\cup \{C_j\mid j\in [m]\}\cup \{p,l,h,x_{n+1},\mathsf {skin},\mathsf {halt},0\}\), and

the initial membrane configuration (\(\mu\)) and the set of rules (R) are defined below.
The initial membrane configuration \(\mu =(V,E,L,\omega\)) can be seen in Fig. 1. The labels of the membranes are placed beside the nodes, and the multisets associated with the nodes are written in the nodes. Notice that some nodes denote subconfigurations that are explained separately. The root of the membrane structure is the \(\mathsf {skin}\) which has an only child with label \(\mathsf {halt}\). Below \(\mathsf {halt}\) there are two subconfigurations called the working subtree and the countdown subtree, respectively (see Fig. 1a). The working subtree (Fig. 1b) will be used to decide if the input formula F is true. More precisely, this part will produce at least one object T in the \(\mathsf {halt}\)membrane if and only if F is true. Then T triggers the dissolution of the \(\mathsf {halt}\)membrane resulting \(yes\) in the \(\mathsf {skin}\). The countdown subtree (Fig. 1c) will be used to produce an object s in the \(\mathsf {halt}\)membrane if and only if F is false, that is, no object T was produced in the \(\mathsf {halt}\)membrane by the working subtree. Then, s triggers the dissolution of the \(\mathsf {halt}\)membrane resulting no in the \(\mathsf {skin}\). The countdown subtree has \(7n+2m+5\) linearly nested lmembranes and an elementary hmembrane in the innermost lmembrane. Initially, all the lmembranes are empty, and for the only hmembrane x, \(\omega (x)=s\).
The working subtree is divided into three parts: the quantification, the clause evaluation, and the assignment parts. We now describe the structure of these parts and give a brief, general description of their role in the whole computation. A more detailed explanation about their operation will be given later.
The quantification part will be used to create exponentially many subtrees of the membrane structure, each of them containing objects that encode a possible valuation of the variables of F. In this part, we have membranes with unique labels in \(\{x_i,x'_i\mid i\in [n]\}\cup \{x_{n+1}\}\) and several further membranes with label p. The membrane structure of the quantification part can be seen in Fig. 2a. It is a single path with a root that is labeled by \(x_1\), and a leaf that is the innermost pmembrane. Figure 2a shows the labels of the other nodes in this part. Notice that there is a regularity in the labelling below the \({x_2}\)membrane: for nodes x, y, z with \((z,y),(y,x)\in E\) and \(i\in [3,n]\), if \(L(x)=x_i\), then \(L(y)=p\) and \(L(z)=x'_i\). Labels in \(\{x_i,x'_i\mid i\in [n]\}\) refer to the corresponding variables of F, while the label p refers to the word “prison”, because the object a which is initially placed in the pmembranes cannot trigger any rule — so it is imprisoned — until another object sets it free by using a dissolution rule. The membranes of the quantification part are associated with initial multisets of objects as follows. Let x be a node of this part. If x is the \(x_2\)membrane or it is a pmembrane, then \(\omega (x)=a\), and \(\omega (x)=\varepsilon\) otherwise.
The clause evaluation part will be used to check if a valuation of the variables satisfies all the clauses. In this part, we have membranes with unique labels in \(\{C_1,\ldots ,C_m\}\). These labels refer to the corresponding clauses of F. The membrane structure of this part can be seen in (Fig. 2b). It is a single path with a root labeled by \(C_1\) and descendants of this root labeled by \(C_2,\ldots ,C_m\), respectively. Initially, these membranes are all empty, that is, for each node x in this part \(\omega (x)=\varepsilon\).
The assignment part (Fig. 2c) will be used to select those objects from the input which represent literals that can make a clause true according to the corresponding valuation. This part of the working subtree is a tree with height one. Its root is labeled by 0, and below the root there are 2n membranes labelled by \(\alpha _1,\ldots ,\alpha _n\) and \(\beta _1,\ldots ,\beta _n\), respectively. Notice that these membranes are the only elementary membranes of the working subtree. Initially, these elementary membranes are empty, while for the root x of the assignment part, \(\omega (x)=\{T\}\).
With this, we have finished the description of the initial membrane configuration of \(\varPi (n,m)\). Now, we set the root of the assignment part, that is the node x with \(L(x)=0\), to be the input membrane of \(\varPi (n,m)\).
Next, we present the rules of R. We group them so that we can explain how the whole computation of \(\varPi (n,m)\) goes. In particular, the correctness of \(\varPi (n,m)\) will also be justified. Therefore, we assume that the input membrane contains not only its initial multiset, but also cod(F), the encoding of the input formula F. We distinguish the following two main stages of the computation, the generation stage and the verification stage.
First, we give the rules applied in the generation stage. Here, the P system generates all the possible valuations of the variables of F and sends the objects encoding them down in the membrane structure. This is carried out in the working subtree of the initial membrane structure using several groups of rules presented below.
The following rules divide the \(x_{i+1}\)membranes (\(i\in [n]\)), that is, duplicate those subtrees of the quantification part which have an \(x_{i+1}\)membrane as the root.
After the division, the root of the first new subtree contains either \(\hat{t}_i\) with \(i\in [n1]\) or \(t'_n\), while the root of the other one contains either \(\hat{f}_i\) with \(i\in [n1]\) or \(f'_n\), representing that \(x_i\) is set to true and to false, respectively. In fact, the duplication of these subtrees corresponds to the recursive calls in lines 4 and 6 in Algorithm 1 where the first and second calls use \(\varPhi\) with \(x_i\) set to true and to false, respectively. The reason why we handle the case \(i=n\) differently by introducing \(t'_n\) and \(f'_n\) instead of \({\hat{t}}_n\) and \({\hat{f}}_n\) will be discussed later.
Initially, only the \({x_2}\)membrane can be divided, since the objects that could divide the \(x_k\)membranes with \(k\in [3,n+1]\) are imprisoned in the pmembranes. The P system uses the following rules triggered by \({\hat{t}}_i\) and \({\hat{f}}_i\), respectively, to dissolve the pmembranes and, in turn, to set objects a free:
Notice that an \(x_{i+2}\)membrane can be divided only after that its ancestor \(x_{i+1}\)membrane is already divided. Indeed, as we have discussed above, to divide an \({x_{i+2}}\)membrane, an object \({\hat{t}}_{i}\) or \({\hat{f}}_{i}\) is necessary and these objects are introduced during the division of an \(x_{i+1}\)membrane.
The evolution of \(\hat{t}_i\) to \(t'_i\) and \(\hat{f}_i\) to \(f'_i\) in the dissolution rules above is necessary since we want to send the objects encoding the valuations down to the leaves. Without evolving these objects there would occur undesired nondeterminism: we would have incommunication and dissolution rules triggered by the same objects. Notice moreover that the rule \([a]_{x_{n+1}} \rightarrow [t'_n]_{x_{n+1}} [f'_n]_{x_{n+1}}\) given in rules \((\dagger )\) needs to introduce no objects marked with \(\hat{~}\) since when it is applied there are no membranes left to divide. This is why it introduces \(t'_n\) and \(f'_n\) directly.
The following rules are used to send the objects that represent the valuations towards the leaves.
By the application of these rules, objects \(t'_i\) and \(f'_i\) will reach the innermost pmembranes which are in fact the innermost membranes of the quantification part of the working subtree (see Fig. 2a). The system is set up so that when the \(x_{i+1}\)membranes are divided, the objects \(t'_j\) and \(f'_j\) with \(j<i\) have been already passed through the \(x_{i+1}\)membranes. Therefore, these objects are duplicated with the division of the \(x_{i+1}\)membranes. This means that after that the \(x_{n+1}\)membranes are divided, the working subtree of the P system has \(2^{n}\) subtrees with \(x_{n+1}\)membranes at the roots (see Fig. 3). Moreover, each of these subtrees contains a set of objects encoding a possible valuation of the variables. Furthermore, all of the possible valuations are represented in these subtrees.
In parallel to the computation carried out in the quantification part, objects in cod(F) are sent from the input membrane to the \(\alpha _i\) and \(\beta _i\)membranes, respectively, using the following rules.
Recall that object \(v_{i,j}\) (resp. \(v'_{i,j}\)) encode that \(x_i\) (resp. \(\lnot x_i\)) occurs in \(C_j\). Therefore, there are at most m objects representing that the ith variable occurs in a clause (with or without negation). This means that in at most m steps, all the input objects get into the corresponding \(\alpha _i\) or \(\beta _i\)membranes. The role of sending these objects into these membranes will be discussed later.
The following rules send the objects representing the valuations through the clause evaluation part of the working subtree. Notice that the actual evaluation of the clauses does not happen in this part of the computation but in a later stage of it.
When objects \(t'_i\) and \(f'_i\) reach the input membrane, they go inside the \(\alpha _i\) and \(\beta _i\)membranes, respectively. Note that reaching the leaves for \(t'_1\) and \(f'_1\) takes more than m steps (hence for any of the \(t'_i,f'_i\) objects), thus by the time they do so, all the input objects in cod(F) are already separated into the \(\alpha _i\) and \(\beta _i\)membranes, respectively. The next rules are used to dissolve certain \(\alpha _i\) and \(\beta _i\)membranes.
After an object \(t'_i\) (resp. an \(f'_i\)) gets into an \(\alpha _i\)membrane (resp. a \(\beta _i\)membrane), the P system dissolves such membrane using the above rules. Notice that, for each \(i\in [n]\) and \(x,y\in V\) with \(L(x)=\alpha _i\) and \(L(y)=\beta _i\), if x and y are siblings, then either x or y is dissolved but not both. Moreover, since \(t'_n\) and \(f'_n\) are the last objects that reach the leaves, the last membrane that is dissolved in this part of the computation is either an \(\alpha _n\) or a \(\beta _n\)membrane. After the dissolution, 0membranes contain exactly those objects from cod(F) that correspond to literals that are true under the corresponding evaluation of the variables. Clearly, these literals satisfy the clauses they occur in under this evaluation. During the dissolution of the \(\alpha _i\) and \(\beta _i\)membranes, objects \(t'_i\) and \(f'_i\) evolve to \(t_i\) and \(f_i\), respectively, which is necessary to avoid undesired nondeterminism in the remaining part of the computation. After dissolving all of the \(\alpha _i\) and \(\beta _i\)membranes, \(t_n\) or \(f_n\) dissolves the 0membrane and all objects contained in this membrane, including an object T initially placed in it, get to the \(C_1\)membrane.
We now give the rules that are used in the verification stage of the computation. Here, the P system checks first whether a valuation satisfies all the clauses then it combines the information about the different valuations appropriately. To evaluate the clauses, it uses the following rules.
With these rules, \(\varPi (n,m)\) in fact implements lines 9–14 of Algorithm 1 by searching, for each clause C of \(\varPhi\), a literal that occurs in C and is true under the corresponding valuation. Let \(x\in V\) be an \(x_{n+1}\)membrane and \({{\mathcal {A}}}\) denote a valuation represented by objects \(t_i\) and \(f_i\) occurring in the subtree with root x. The subcomputation here starts with an attempt to apply a rule of the form \([v_{i,1}]_{C_1}\rightarrow v_{i,1}\) or \([v'_{i,1}]_{C_1}\rightarrow v'_{i,1}\). If no object can trigger any of these rules, then the computation halts in this subtree. Assume now that \(v_{i,1}\) occurs in a \(C_1\)membrane y. Then \(t_i\) occurs in y, too, and thus \({{\mathcal {A}}}\) assigns true to \(x_i\). Moreover, by the definition of cod(F), \(x_i\) occurs in the clause \(C_1\) of F which yields that \({\mathcal {A}}\) satisfies \(C_1\). If, on the other hand, \(v'_{i,1}\) occurs in y, then \(f_i\) should occur here, too. This means that \({{\mathcal {A}}}\) assigns false to \(x_i\) and thus, since in this case \(\lnot x_i\) should occur in \(C_1\), \({{\mathcal {A}}}\) satisfies \(C_1\) in this case, too. That is, the \(C_1\)membrane y is dissolved if and only if \({{\mathcal {A}}}\) satisfies \(C_1\). Generalising this argumentation to the rest of the \(C_j\)membranes one can see that \(\varPi (n,m)\) dissolves all the \(C_j\)membranes \((j\in [m])\) if and only if \({{\mathcal {A}}}\) satisfies \(\varPhi\). Thus, at the end of this part of the verification stage (corresponding to the clause evaluation part, see Fig. 3), the following statement holds.
(1) An \(x_{n+1}\)membrane either contains no objects, or contains objects \(t_i\) and \(f_i\) (for each \(i\in [n]\), exactly one of \(t_i\) or \(f_i\)) encoding a satisfying valuation of \(\varPhi\) (with \(t_i\) and \(f_i\) encoding \(x_i=true\) and \(x_i=false\), respectively) along with an object T.
In the next part of the verification stage, the P system evaluates F using the following rules.
and
We now describe the computation of \(\varPi (n,m)\) using these rules and at the same time show that \(\varPi (n,m)\) evaluates F correctly. First, all the \(x_{n+1}\)membranes which contain an object T are dissolved. Let \(i\in [n]\) and \(\tau \in \{t_i,f_i\}\), and let us denote by \(v(\tau )\) the truth value represented by \(\tau\). To see that \(\varPi (n,m)\) evaluates F correctly, we first show the following statement.
\((\ddagger )\) If an \(x_i\)membrane \((i\in [n+1])\) x is dissolved by \(\varPi (n,m)\), then
$$\begin{aligned} Q_ix_iQ_{i+1}x_{i+1}\ldots Q_nx_n\varPhi (v(\tau _1),\ldots ,v(\tau _{i1}),x_i, x_{i+1},\ldots ,x_n)=true, \end{aligned}$$where \(Q_i,Q_{i+1},\ldots ,Q_n\) are the corresponding quantifiers of F and, for every \(j\in [i1]\), \(\tau _j\) is either \(t_j\) or \(f_j\) according to the objects occurring in x.
Due to the following observation, \(\tau _j\) in \((\ddagger )\) is well defined.
(2) For any \(x_i\)membrane \((i\in [n+1])\) x and \(j\in [i1]\), x cannot contain both \(t_j\) and \(f_j\) during the whole computation of \(\varPi (n,m)\).
We now show \((\ddagger )\) by induction on i. If \(i=n+1\), then \((\ddagger )\) follows from Statement (1). Assume now that \((\ddagger )\) holds for \(1< i\le n+1\). We show it for \(i1\). Consider an \(x_{i1}\)membrane x. We distinguish the following two cases.

1.
\(i1\) is even. By looking at the rules above, one can see that to dissolve x, this membrane has to contain \(t_{i1}\). This object can occur in x only if the \(x_{i1}'\)membrane y below x contains both \(t_{i1}\) and \(f_{i1}\). The only way to introduce these objects in y is to dissolve some of the \(x_{i}\)membranes below y. Since by Statement (2) \(x_i\)membranes cannot contain both \(t_{i1}\) and \(f_{i1}\), to introduce these objects in y, both of the \(x_{i}\)membranes below y have to be dissolved. Then, by the induction hypothesis,
$$\begin{aligned} Q_{i}x_{i}Q_{i+1}x_{i+1}\ldots Q_nx_n\varPhi (v(\tau _1),\ldots ,v(\tau _{i2}),\nu , x_{i},\ldots ,x_n), \end{aligned}$$is true, for every truth value \(\nu \in \{true,false\}\). Therefore,
$$\begin{aligned} \forall x_{i1}Q_{i}x_{i}\ldots Q_nx_n\varPhi (v(\tau _1),\ldots ,v(\tau _{i2}),x_{i1}, x_{i},\ldots ,x_n), \end{aligned}$$is true as well.

2.
\(i1\) is odd. In this case, both \(t_{i1}\) and \(f_{i1}\) can dissolve the \({x_{i1}}\)membranes as well as the \({x'_{i1}}\)membranes. Using this and following the argumentation given in the previous case, we can conclude that in this case at least one of the \(x_{i}\)membranes below x has to be dissolved. Then, by the induction hypothesis, there is \(\nu\) in \(\{true, false\}\) such that
$$\begin{aligned} Q_{i}x_{i}\ldots Q_nx_n\varPhi (v(\tau _1),\ldots ,v(\tau _{i2}),\nu , x_{i},\ldots ,x_n), \end{aligned}$$is true. Therefore,
$$\begin{aligned} \exists x_{i1}Q_{i}x_{i}\ldots Q_nx_n\varPhi (v(\tau _1),\ldots ,v(\tau _{i2}),x_{i1}, x_{i},\ldots ,x_n), \end{aligned}$$is true as well.
This concludes the proof of \((\ddagger )\). Reversing the argumentation used in this proof, it can be seen that if an \(x_i\)membrane is not dissolved during the computation of \(\varPi (n,m)\), then \(Q_{i}x_{i}\ldots Q_nx_n\varPhi (v(\tau _1),\ldots ,v(\tau _{i1}),x_i, x_{i+1},\ldots ,x_n)\) must be false. Consequently,
\((\star )\) an \(x_i\)membrane \((i\in [n+1])\) x is dissolved by \(\varPi (n,m)\) if and only if \(Q_ix_iQ_{i+1}x_{i+1}\ldots Q_nx_n\varPhi (v(\tau _1),\ldots ,v(\tau _{i1}),x_i, x_{i+1},\ldots ,x_n)\) is true.
Using \((\star )\), it can be seen that, for every \(i\in [n]\), if i is even (resp. odd), then the return value in Line 4 (resp. in Line 6) of Algorithm 1 is true if and only if the corresponding \(x_i\)membrane is dissolved. Consequently, F is true if and only if the \(x_1\)membrane is dissolved. Therefore, an object T can reach the \(\mathsf {halt}\)membrane if and only is F is true.
Using the following, final set of rules, \(\varPi (n,m)\) introduces the answer of the system in the \(\mathsf {skin}\)membrane.
The first two rules are used in the countdown subtree (Fig. 1c). From the very beginning of the computation, an lmembrane containing an object s gets dissolved in each computational step. Since the countdown subtree contains \(7n+2m+5\) lmembranes, it takes \(7n+2m+6\) steps for s to dissolve the hmembrane and all the lmembranes. On the other hand, it can be seen that if F is true, then exactly \(7n+2m+5\) steps are necessary for an object T to reach the \(\mathsf {halt}\)membrane.
If F is true and thus an object T reaches the \(\mathsf {halt}\)membrane, then the system uses \([T]_{\mathsf {halt}} \rightarrow yes\) to introduce yes in the \(\mathsf {skin}\)membrane. In this case, s arrives from the countdown subtree into the \(\mathsf {skin}\)membrane and the computation halts.
If F is false and thus none of the objects T reaches the \(\mathsf {halt}\)membrane, then s arrives from the countdown subtree to the \(\mathsf {halt}\)membrane. Then s dissolves this membrane introducing no in the \(\mathsf {skin}\)membrane as the last step of the computation. With this, we have finished the description of \(\varPi (n,m)\), and the correctness of the family \(\mathbf {\varPi }\) has also been justified. To conclude the proof of Theorem 1, observe that

the P systems in \(\mathbf {\varPi }\) can be constructed by a logarithmic space Turing machine,

the input encoding cod can be constructed by a logarithmic space Turing machine, and

for each input formula F with n variables and m clauses, \(\varPi (n,m)\) halts in linear time \(O(n+m)\).
Hence, as logarithmic space Turing machines are guaranteed to halt within a polynomial number of steps, our construction is indeed a polynomially uniform, polynomialtime family of polarizationless recognizer P systems, employing only incommunication, membrane dissolving and weak division rules, solving the PSPACEcomplete QSAT problem.
Conclusion
In this paper, we have investigated the computation power of polarizationless P systems with active membranes employing only incommunication, dissolution, and weak nonelementary membrane division rules. We have shown that these P systems can solve PSPACEcomplete problems in polynomial time. It is well known that P systems with active membranes defined in [26] can solve exactly the problems in PSPACE in polynomial time [33]. Using our result and generalising the proof of the PSPACE upper bound given in [33], we get that the computational power of polynomialtime P systems investigated in this paper characterises PSPACE, too.
The term “weak nonelementary membrane division” suggests that this kind of membrane division is weaker than the classical strong nonelementary division introduced in [26]. According to our knowledge, it is open whether weak nonelementary division is indeed weaker than the strong one. In fact, we suspect that this is not the case and probably the computational power of P systems employing either weak or strong nonelementary membrane division is incomparable. The comparison of these nonelementary membrane division rules in terms of computational power is a topic of our further research plans. For more open problems in the vast landscape of membrane computing, the interested reader is referred to [32].
References
 1.
Alhazov, A., PérezJiménez, M.J. (2007). Uniform solution of QSAT using polarizationless active membranes. International Conference on Machines, Computations and Universality, 122–133.
 2.
Alhazov, A., Leporati, A., Manzoni, L., Mauri, G., & Zandron, C. (2021). Alternative space definitions for P systems with active membranes. Journal of Membrane Computing, 3, 87–96.
 3.
Alhazov, A., MartínVide, C., & Pan, L. (2003). Solving a \(\rm PSPACE\)complete problem by P systems with restricted active membranes. Fundamenta Informaticae, 58, 67–77.
 4.
Alhazov, A., Pan, L., & Păun, Gh. (2004). Trading polarizations for labels in P systems with active membranes. Acta Informatica, 41(2–3), 111–144.
 5.
Buño, K., & Adorna, H. (2020). Distributed computation of a kP system with active membranes for SAT using clause completion. Journal of Membrane Computing, 2(2), 108–120.
 6.
Gazdag, Zs. (2014). Solving SAT by P systems with active membranes in linear time in the number of variables. In: A. Alhazov, S. Cojocaru, M. Gheorghe, Y. Rogozhin, G. Rozenberg, A. Salomaa (Eds.), Membrane Computing: 14th International Conference, LNCS (vol. 8340, pp. 189–205)
 7.
Gazdag, Zs., Kolonits, G. (2013). A new approach for solving SAT by P systems with active membranes. In: E. CsuhajVarjú, M. Gheorghe, G. Rozenberg, A. Salomaa, G. Vaszil (Eds.), Membrane Computing: 13th International Conference, LNCS (vol. 7762, pp. 195–207)
 8.
Gazdag, Zs., Kolonits, G. (2017). Remarks on the computational power of some restricted variants of P systems with active membranes. In: A. Leporati, G. Rozenberg, A. Salomaa, C. Zandron (Eds.), Membrane Computing, 17th International Conference, LNCS (vol. 10105, pp. 209–232)
 9.
Gazdag, Zs., & Kolonits, G. (2019). A new method to simulate restricted variants of polarizationless P systems with active membranes. Journal of Membrane Computing, 1(4), 251–261.
 10.
Gensler, H. J. (2002). Introduction to logic. Routledge.
 11.
GutierrezNaranjo, M.A., PerezJimenez, M.J., RiscosNúñez, A., RomeroCampero, F.J. (2006). On the power of dissolution in P systems with active membranes. In: R. Freund, Gh. Păun, G. Rozenberg, A. Salomaa (eds.), Membrane computing: 6th international workshop, LNCS (vol. 3850, pp. 224–240)
 12.
Krishna, S. N., & Rama, R. (1999). A variant of P systems with active membranes: Solving NPcomplete problems. Romanian Journal of Information Science and Technology, 2(4), 357–367.
 13.
Leporati, A., Manzoni, L., Mauri, G., Porreca, A.E., Zandron, C. (2014). Simulating elementary active membranes, with an application to the P conjecture. In: M. Gheorghe, G. Rozenberg, A. Salomaa, P. Sosík, C. Zandron (Eds.), Membrane computing – 15th international conference, CMC15, LNCS (vol. 8961, pp. 284–299)
 14.
Leporati, A., Manzoni, L., Mauri, G., Porreca, A.E., Zandron, C. (2016). Monodirectional P systems. Natural Computing, 15, 551–564
 15.
Leporati, A., Manzoni, L., Mauri, G., Porreca, A.E., Zandron, C. (2017). Solving a special case of the P conjecture using dependency graphs with dissolution. In: M. Gheorghe, G. Rozenberg, A. Salomaa, C. Zandron (eds.), Membrane computing: 18th international conference, LNCS (vol. 10725, pp. 196–213)
 16.
Leporati, A., Ferretti, C., Mauri, G., PérezJiménez, M. J., & Zandron, C. (2009). Complexity aspects of polarizationless membrane systems. Natural Computing, 8(4), 703–717.
 17.
Leporati, A., Manzoni, L., Mauri, G., Porreca, A. E., & Zandron, C. (2019). Characterizing PSPACE with shallow nonconfluent P systems. Journal of Membrane Computing, 1, 75–84.
 18.
Murphy, N., Woods, D. (2007). Active membrane systems without charges and using only symmetric elementary division characterise P. In: G. Eleftherakis, P. Kefalas, Gh. Păun, G. Rozenberg, A. Salomaa (eds.), Membrane computing: 8th international workshop, LNCS (vol. 4860, pp. 367–384)
 19.
Murphy, N., Woods, D. (2009). On acceptance conditions for membrane systems: Characterisations of \(\mathbf{L}\) and \(\mathbf{NL}\). In T. Neary, D. Woods, T. Seda, N. Murphy (eds.), Proceedings international workshop on the complexity of simple programs, Cork, Ireland, Volume 1 of Electronic Proceedings in Theoretical Computer Science., Open Publishing Association (pp. 172–184)
 20.
Murphy, N., & Woods, D. (2011). The computational power of membrane systems under tight uniformity conditions. Natural Computing, 10(1), 613–632.
 21.
Murphy, N., & Woods, D. (2014). Uniformity is weaker than semiuniformity for some membrane systems. Fundamental Information, 134(1–2), 129–152.
 22.
OrellanaMartín, D., & RiscosNúnez, A. (2020). Seeking computational efficiency boundaries: The Păun’s conjecture. Journal of Membrane Computing, 2, 323–331.
 23.
Pan, L., & Alhazov, A. (2006). Solving HPP and SAT by P systems with active membranes and separation rules. Acta Informatica, 43(2), 131–145.
 24.
Pan, L., Alhazov, A., & Ishdorj, T.O. (2004). Further remarks on P systems with active membranes, separation, merging, and release rules. Soft Computing, 9(9), 686–690.
 25.
Păun, Gh. (2005). Further twenty six open problems in membrane computing. In: Third Brainstorming Week on Membrane Computing, (pp. 249–262). Fénix Editora, Sevilla
 26.
Păun, Gh. (2001). P systems with active membranes: Attacking NPcomplete problems. Journal of Automata, Languages and Combinatorics, 6(1), 75–90.
 27.
Păun, Gh., Rozenberg, G., & Salomaa, A. (Eds.). (2010). The Oxford Handbook of Membrane Computing. Oxford University Press.
 28.
PérezJiménez, M. J., RomeroJiménez, Á., & SanchoCaparrini, F. (2003). Complexity classes in models of cellular computing with membranes. Natural Computing, 2(3), 265–285.
 29.
PérezJiménez, M. J., RomeroJiménez, Á., & SanchoCaparrini, F. (2006). A polynomial complexity class in P systems using membrane division. Journal of Automata, Languages and Combinatorics, 11(4), 423–434.
 30.
Salomaa, A. (1973). Formal languages. Academic Press.
 31.
Sosík, P. (2003). The computational power of cell division in P systems. Natural Computing, 2(3), 287–298.
 32.
Sosík, P. (2019). P systems attacking hard problems beyond NP: A survey. Journal of Membrane Computing, 1, 198–208.
 33.
Sosík, P., & RodríguezPatón, A. (2007). Membrane computing and complexity theory: A characterization of PSPACE. Journal of Computer and System Sciences, 73(1), 137–152.
 34.
Woods, D., Murphy, N., PérezJiménez, M.J., RiscosNúñez, A. (2009). Membrane dissolution and division in P. In: C.S. Calude, J.F.G. da Costa, N. Dershowitz, E. Freire, G. Rozenberg (Eds.), Unconventional computation: 8th international conference, LNCS (vol. 5715, pp. 262–276)
 35.
Zandron, C., Ferretti, C., Mauri, G. (2001). Solving NPcomplete problems using P systems with active membranes. In: Unconventional models of computation, UMC’2K: Proceedings of the second international conference on unconventional models of computation (pp. 289–301). Springer London, London
 36.
Zandron, C. (2020). Bounding the space in P systems with active membranes. Journal of Membrane Computing, 2, 137–145.
Acknowledgements
This research was supported by Grant NKFIH12792/2020 of the Ministry for Innovation and Technology, Hungary.
Funding
Open access funding provided by University of Szeged.
Author information
Affiliations
Corresponding author
Ethics declarations
Conflict of interest
On behalf of all authors, the corresponding author states that there is no conflict of interest.
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
About this article
Cite this article
Gazdag, Z., Hajagos, K. & Iván, S. On the power of P systems with active membranes using weak nonelementary membrane division. J Membr Comput (2021). https://doi.org/10.1007/s41965021000822
Received:
Accepted:
Published:
Keywords
 Membrane computing
 P systems with active membranes
 Nonelementary membrane division
 PSPACEcompleteness