# Solution to PSPACE-Complete Problem Using P Systems with Active Membranes with Time-Freeness

Authors: Bosheng Song; Yuan Kong
Journal: Mathematical Problems in Engineering
 (2019)

---

## Abstract

P systems with active membranes are powerful parallel natural computing models, which were inspired by cell structure and behavior. Inspired by the parallel processing of biological information and with the idealistic assumption that each rule is completed in exactly one time unit, P systems with active membranes are able to solve computational hard problems in a feasible time. However, an important biological fact in living cells is that the execution time of a biochemical reaction cannot be accurately divided equally and completed in one time unit. In this work, we consider time as an important factor for the computation in P systems with active membranes and investigate the computational efficiency of such P systems. Specifically, we present a time-free semiuniform solution to the quantified Boolean satisfiability problem (QSAT problem, for short) in the framework of P systems with active membranes, where the solution to such problem is correct, which does not depend on the execution time for the used rules.


---

## Body

## 1. Introduction

Membrane computing is a member of natural computing that seeks to discover new computational models from the study of biological cells [1, 2]. Since the first computational model was proposed in 1998, many variants of models were constructed [3–7], and all computational models considered in such framework are calledP systems. Inspired by the biological structure of cells, there are two kinds of P systems:neural-like P systems [8, 9] ortissue-like P systems [10, 11] (arbitrary graph structure) andcell-like P systems [2, 12] (tree structure). For more information about the area of membrane computing, we refer the reader to [13–18].AP system with active membranes is one of basic cell-like P systems; all membranes are embedded in a skin membrane [19, 20]. In such P systems, each membrane delimits aregion (also calledcompartment), which containsmultisets of objects andevolution rules. If a membrane does not contain any other membrane, then it is calledelementary; if a membrane contains at least an inner membrane, then it is callednonelementary. An interesting feature of P systems with active membranes is that there exists one of electrical charge (positive (+), negative (-), or neutral (0)) on each membrane, and such P systems are evolved according to the following types of rules: (a)send-in communication rules, (b)send-out communication rules, (c) evolution rules, (d) division rules, and (e) dissolving rules. When one of such rules is applied, the charge on the involved membrane may be changed.There are many interesting results obtained by P systems with active membranes and their variants [19, 21, 22]. Because P systems with active membranes contain membrane division rules, which can generate arbitrary numbers of membranes, that is, an exponential workspace in polynomial time has been generated, they provide a way to theoretically solveNP-complete problems orPSPACE-complete problem in feasible time (in polynomial time or in linear time) by a time-space trade-off [23–27]. In [28], the QSAT problem is solved in linear time by P systems with restricted active membranes; however, in [29], the QSAT problem is solved in polynomial time by P systems with active membranes and without polarizations.Inspired by biological fact that the execution time of a biochemical reaction cannot be accurately divided equally and completed in one time unit, in [30],timed P systems were proposed such that a natural number representing the execution time is associated with each rule. The notion oftime-free is also proposed in [30], which is considered to solve hard computational problems [31–37]. In all these time-free solutions to hard computational problems, the correct computation results are obtained when any execution time is given for each rule. Note that, in [32, 36], the QSAT problem was solved by P systems in a time-free uniform way.In this work, the notion of time-freeness is incorporated into P systems with active membranes, and a time-free semiuniform solution to thePSPACE-complete problem, QSAT problem, is presented, where the solution to such problem is correct, which does not depend on the execution time for the used rules.


## 2. Preliminary and Model Description

In this section, we first give the basic conception of formal language theory and the notion of P systems with active membranes [20, 38].For an alphabetΓ (a finite nonempty set of symbols), we denote by Γ∗ the set of all strings over Γ, and by Γ+=Γ∗\{λ} we denote the set of nonempty strings. Thelength of a string u, denoted by u, is the total number of symbols in the string.We denote by(Γ,f) amultisetm over an alphabet Γ, where f is a mapping from Γ onto N (the set of natural numbers). If Γ={a1,…,ak}, then the multiset of m is denoted by m={a1f(a1),…,akf(ak)}, which can also be represented by m=a1f(a1)…akf(ak) or by any permutation of this string.Definition 1.
A P system with active membranes is a tuple(1)Π=O,H,μ,w1,…,wm,R,where (i)
O is an alphabet which includes all objects used in the system;(ii)
H is a label set which marks for each membrane;(iii)
μ is an initial membrane structure;(iv)
wi,1≤i≤m, are multisets of objects that are placed in m membranes at the initial configuration;(v)
R is a finite set of rules with the following forms:
(a)
Object evolution rules:a→vhe, for h∈H,e∈C,a∈O,v∈O∗.(b)
Send-in communication rules: ahe1→bhe2, for h∈H,e1,e2∈C,a,b∈O.(c)
Send-out communication rules: ahe1→he2b, for h∈H,e1,e2∈C,a,b∈O.(d)
Dissolving rules:ahe→b, for h∈H,e∈C,a,b∈O.(e)
Division rules for elementary membranes or nonelementary membranes:ahe1→bhe2che3, for h∈H,e1,e2,e3∈C,a,b,c∈O.The current membrane structure (including polarization associates with each membrane) and the multisets of objects in each membrane at a moment are considered aconfiguration of the P system. A P system starts from the initial configuration; using rules in a maximally parallel manner, a sequence of consecutive configurations is archived. If there is no rule used in the system, thenhalting configuration is reached. The result of a system is encoded by the objects present in the output membrane or emitted from the skin membrane when the system reaches halting configuration.Next we give the definitions of timed P systems with active membranes and the corresponding recognizer version of such model; time-free solutions to decision problems by such P systems are also introduced [33, 39].Definition 2.
A timed P system with active membranes is a pair(Π,e), where Π is a P system with active membranes and e is a mapping from the finite set of rules in the system into the set of natural numbers N (representing the execution times for rules in such system).A timed P system with active membranesΠ(e) works in the following way: an external clock is assumed, which marks time-units of equal length; the step t of computation is defined by the period of time that goes from instant t-1 to instant t. If a membrane contains a rule r from types (a)-(e) selected to be executed, then execution of such rule takes e(r) time units to complete. Therefore, if the execution is started at instant j, the rule is completed at instant j+e(r) and the resulting objects and membranes become available only at the beginning of step j+e(r)+1. When a rule r from types (b) – (e) is started, then the occurrences of symbol-objects and the membrane subject to this rule cannot be subject to other rules from types (b)–(e) until the implementation of the rule completes. At one step, a membrane can be subject to several rules of type (a).In timed P systems with active membranes, the evolution rules and division rules also follow the “bottom-up" manner (one can refer to [33, 39] for more details).Definition 3.
A recognizer timed P system with active membranes of degreem≥1 is a tuple Π=(O,H,μ, w1,…,wm,R,e,iout), such that (i)
the tuple(O,H,μ,w1,…,wm,R) is a P system with active membranes, where alphabet O includes two elements, yes and no;(ii)
iout=0: the output zone is the environment;(iii)
e is a time-mapping of Π;(iv)
all the computations halt;(v)
either objectyes or object no (but not both) must appear in the output region (environment) when the system reaches the halting configuration.The present work also uses rule starting steps (RS-steps, for short) as the computation steps; a computation step is called aRS-step if at this step at least one rule starts its execution [33, 39].Adecision problemX is a pair (IX,ΘX) such that IX is a language over a finite alphabet (whose elements are calledinstances) and ΘX is a total Boolean function (i.e., predicate) over IX.Definition 4.
LetX=(IX,ΘX) be a decision problem. We say that X is solvable in time-free polynomial RS-steps by a family of recognizer P systems with active membranes Π={Πu:u∈IX} if the following items are true: (i)
the familyΠ is polynomially uniform by a Turing machine; that is, there exists a deterministic Turing machine working in polynomial time which constructs the system Πu from the instance u∈IX.(ii)
the familyΠ is time-free sound (with respect to X); that is, for any time-mapping e, the following property holds: if for each instance of the problem u∈IX such that there exists an accepting computation of Πu(e), we have ΘX(u)=1.(iii)
the familyΠ is time-free complete (with respect to X); that is, for any time-mapping e, the following property holds: if for each instance of the problem u∈IX such that ΘX(u)=1, every computation of Πu(e) is an accepting computation.(iv)
the familyΠ is time-free polynomially bounded; that is, there exists a polynomial function p(n) such that, for any time-mapping e and for each u∈IX, all the computations in Πu(e) halt in, at most, p(u) RS-steps.We also say that the familyΠ provides an efficienttime-free semiuniform solution to the decision problem X.


## 3. A Time-Free Solution toQSAT Problem by P Systems with Active Membranes

Quantified Boolean formula problem (QBF, in short) is a well-knownPSPACE-complete problem [40]; it asks whether a quantified sentential form over a set of Boolean variables is true or false. For more details about QBF, one can refer to [28].Theorem 5.
A family of P systems with active membranes using rules of types (a), (b), (c), and (e′) can solve the QSAT problem in polynomial RS-steps in a time-free manner, where the solution to such problem is correct, which does not depend on the execution time for the used rules.Proof.
Let us consider a quantified Boolean formula:(2)φ=∃x1∀x2…∃x2n-1∀x2nC1∧C2∧⋯∧Cm,Ci=yi,1∨⋯∨yi,li,1≤i≤m,where(3)yi,k∈xj,¬xj∣1≤j≤2n,1≤i≤m,1≤k≤li.
We construct the following P system with active membranes:(4)Π=O,H,μ,w1,w2,…,w2n+m+1,R,iout,with the following components: (5)O=ai,ai1,ai2,ai3,ti,fi1≤i≤2n∪ci,ci′,ri,ri′1≤i≤m∪yes,no,a2n+1,cm+1,s,t.H=1,2,…,2n+m+1,μ=…2n+10…2n+m02n02n-10…20102n+m+10,w1=a1,wi=λ,2≤i≤2n+m,w2n+m+1=no,iout=0,
The rules designed for solving theQSAT problem are divided into four parts: generation phase, checking phase, quantifier phase, and output phase. In what follows, we give the set R and its explanation. Let e be any time-mapping from R to N (set of natural numbers representing the execution times for the rules).
Generation Phase G 1 , i : a i i 0 → t i i 0 f i i 0, 1≤i≤2n. G 2 , i , j : t i j 0 → t i j 0, 1≤i≤2n-1,i+1≤j≤2n. G 3 , i , j : f i j 0 → f i j 0, 1≤i≤2n-1,i+1≤j≤2n. G 4 , i : t i → r h i , 1 … r h i , j i a i ( 1 ) 2 n 0, 1≤i≤2n, and the clauses Chi,1,…,Chi,ji contain the literal xi. G 5 , i : f i → r h i , 1 … r h i , j i a i ( 2 ) 2 n 0, 1≤i≤2n, and the clauses Chi,1,…,Chi,ji contain the literal ¬xi. G 6 , i , j : a i ( 1 ) j 0 → j 0 a i ( 1 ), 1≤i≤2n-1,i+1≤j≤2n. G 7 , i , j : a i ( 2 ) j 0 → j 0 a i ( 2 ), 1≤i≤2n-1,i+1≤j≤2n. G 8 , i : a i ( 1 ) i 0 → i + a i ( 1 ), 1≤i≤2n. G 9 , i : a i ( 2 ) i 0 → i - a i ( 2 ), 1≤i≤2n. G 10 , i : a i ( 1 ) i - → a i ( 3 ) i +, 1≤i≤2n. G 11 , i : a i ( 3 ) i + → i + a i ( 3 ), 1≤i≤2n. G 12 : a 1 ( 3 ) → a 2 a 2 2 n + m + 1 +. G 13 , i : a i ( 3 ) → a i + 1 a i + 1 i - 1 0, 2≤i≤2n. G 14 , i : a i i - 1 + → a i i - 1 0, 2≤i≤2n+1. G 15 , i : a i i 0 → a i i 0, 2≤i≤2n.
Initially, we have objecta1 in membrane 1, which corresponds to variable x1, and object no in membrane 2n+m+1. At step 1, rules G1,1 and O1 start to be used at the same step, but they may complete at different steps. By using G1,1, membrane 1 is divided, objects t1 (representing the true valuetrue) and f1 (representing the true valuefalse) are generated, and each of the new produced membranes will obtain one of these two objects. Besides, object no exits the membrane 2n+m+1 by using rule O1; polarization of membrane 2n+m+1 is changed to positive. During the execution of rule G1,1, the system takes one RS-step.
RulesG2,1,2 and G3,1,2 start to be used at the same step only when rule G1,1 completes; however, due to the fact that execution for rules G2,1,2 and G3,1,2 may take different times, these two rules may complete at different steps. By using rule G2,1,2 (resp., G3,1,2), object t1 (resp., f1) enters membrane 2. After the execution of rule G2,1,2 (resp., G3,1,2), system starts to use rule G2,1,3 (resp., G3,1,3); object t1 (resp., f1) enters membrane 3. In this way, rules G2,1,j (resp., G3,1,j) (2≤j≤2n) will be applied one by one, and object t1 (resp., f1) will be transferred to membrane 2n.
If membrane2n has object t1 (resp., f1), rule G4,1 (resp., G5,1) starts to apply; these rules are used to look for the clauses satisfied by the truth-assignmenttrue (resp.,false) of variable x1. Note that rules G4,1 and G5,1 may start to be used at different steps.
If membrane2n contains object a1(1) (resp., a1(2)), then rule G6,1,2n (resp., G7,1,2n) is used; object a1(1) (resp., a1(2)) exits membrane 2n. When membrane 2n-1 contains object a1(1) (resp., a1(2)), rule G6,1,2n-1 (resp., G7,1,2n-1) starts to apply; object a1(1) (resp., a1(2)) exits membrane 2n-1. In this way, rules G6,1,j (resp., G7,1,j) (2≤j≤2n) will be applied one by one, and object a1(1) (resp., a1(2)) will be transferred to membrane 1. Note that rules G6,1,2n and G7,1,2n may start at different steps; rules G6,1,j and G7,1,j (2≤j≤2n-1) may start at different steps.
When membrane 1 contains objecta1(1) (resp., a1(2)), system starts to use rule G8,1 (resp., G9,1), object a1(1) (resp., a1(2)) exits membrane 1, and the polarization of membrane i is changed from neutral to positive (resp., negative). Note that rules G8,1 and G9,1 may start to be used at different steps. Rule G10,1 can be applied only when membrane 2n+m+1 has object a1(1), and there is a membrane 1 having polarization negative; rule G10,1 can be applied only when both rules G8,1 and G9,1 are completed. By applying rule G10,1, object a1(1) evolves to a1(3), and object a1(3) enters membrane 1; polarization of membrane 1 is changed to positive. Hence, rule G10,1 has a synchronization function because Σ2≤j≤2ne(G2,1,j)+e(G4,1)+Σ2≤j≤2ne(G6,1,j)+e(G8,1) may not be equal to Σ2≤j≤2ne(G3,1,j)+e(G5,1)+Σ2≤j≤2ne(G7,1,j)+e(G9,1). Hence, after the execution of rule G10,1, the system takes at most 8n+1 RS-steps.
After the execution of ruleG10,1, the system starts to use rule G11,1; object a1(3) exits membrane 1. Now we have the following two cases: (i)
The execution of ruleO1 has completed; in this case, rule G12 starts to be used, the polarization of membrane 2n+m+1 changes to positive, and two copies of object a2 are produced. Each membrane 1 will obtain one copy of object a2, and polarization of the corresponding membrane is changed to neutral.(ii)
The system is still at the execution of ruleO1; rules G12 and G14,2 will be applied after the execution of rule O1. After the execution of rule O1, the system starts to use rules G12 and G14,2.
After the execution of ruleG14,2, rule G15,2 starts to apply; object a2 enters membrane 2. In all membranes 1, the system starts to use rule G15,2 at the same step, so rule G15,2 in all membranes 1 completes at the same step; that is, in each membrane 2, object a2 is generated at the same step. In general, when membrane 2 has object a2, the system takes at most 8n+5 RS-steps.
When membrane 2 has objecta2, the system starts to assign truth-assignment of variable x2 and looks for clauses satisfied by such variable.
If membrane 2 has objecta2, rule G1,2 starts to be used; the system starts to assign truth valuestrue andfalse to variable x2. In all membranes 1, the system starts and completes rule G1,2 at the same step. The system starts to use rules G2,2,3 and G3,2,3 at the same step, but these rules may complete at different steps. Besides, the system starts and completes rules G2,2,j (4≤j≤2n), G3,2,j (4≤j≤2n), G4,2, G5,2, G6,2,j (3≤j≤2n), G7,2,j (3≤j≤2n), G8,2, and G9,2 at different steps. Note that rule G10,2 can be used only when all the above rules have completed their executions. Thus, this process takes at most 8n+1 RS-steps. So we can deduce that if we consider this process in the worse case, then the system assigns from xi to xi+1 (1≤i≤2n-2); the number of RS-steps decreases by 4. Hence, the system assigns truth-assignment of variable x2n-1 and looks for the clauses satisfied by this variable; this process takes at most 13 RS-steps. Therefore, the system takes at most 8n2+14n-9 RS-steps for this process.
When membrane2n contains object a2n, the system starts to execute rule G1,2n. By using rule G1,2n, objects t1 and f1 are generated, which will be placed in two separate copies of membrane 2n. Note that rule G1,2n in all membranes 2n-1 starts and completes at the same step. Rules G4,2n and G5,2n start to be used at the same step, but they may complete at different steps. Rules G8,2n and G9,2n may start and complete at different steps. When both rules G8,2n and G9,2n have been completed, rule G10,2n starts to apply. So, rule G10,2n has a synchronization function as e(G4,2n)+e(G8,2n) may not be equal to e(G5,2n)+e(G9,2n). If rule G10,2n completes, rules G11,2n, G13,2n, and G14,2n+1 start to apply one by one. Hence, the system assigns truth-assignment of variable x2n and looks for the clauses satisfied for such variable, this process takes at most 8 RS-steps.
So this phase takes at most8n2+14n-1 RS-steps.
The membrane structure is described in Figure1 when generation phase finishes.
Checking Phase C 1 : a 2 n + 1 → c 1 2 n 0. C 2 , j : c j 2 n + j 0 → c j ′ 2 n + j +, 1≤j≤m. C 3 , j : r j 2 n + j + → r j ′ 2 n + j 0, 1≤j≤m. C 4 , j : c j ′ 2 n + j 0 → 2 n + j 0 c j + 1, 1≤j≤m. C 5 : c m + 1 → t 2 n 0.
After the execution of ruleG13,2n, all objects a2n+1 in each membrane 2n-1 enter membrane 2n; polarization for this membrane is changed to neutral at the same step. At that moment, rule C1 is applied; object a2n+1 evolves to object c1 in membrane 2n. After the execution of rule C1, the system starts to check whether each membrane 2n has object r1 or not.
By applying ruleC2,1, object c1 evolves to c1′ and object c1′ enters membranes 2n+1; polarization of such membrane is changed from neutral to positive. After the execution of rule C2,1, rule C3,1 starts to be used, object r1 evolves to r1′, and object r1′ enters membrane 2n+1; polarization of such membrane is changed from positive to neutral. When the charge of membrane 2n+1 changes to neutral, rule C4,1 is used, object c1′ evolves to c2, and object c2 exits membrane 2n+1. When membrane 2n has object c2, it means clause C1 is satisfied, and the system starts to check whether membrane 2n has object r2 or not.
If membrane2n has object c2, rule C2,2 starts to be used. When membrane 2n has object r2, object c3 will be obtained. If a membrane 2n does not contain an object rj, then this membrane will stop evolving when C3,j is supposed to be used. In general, the system takes at most 3m+1 RS-steps.
If there exists a membrane2n which contains all objects r1,r2,…,rm, then rule C5 starts to apply; object cm+1 evolves to t in membrane 2n.
This phase takes at most3m+2 RS-steps.
Quantifier Phase Q 1 : t 2 n 0 → 2 n 0 t. Q 2 : t i 0 → i + t, i=2k,1≤k≤n-1. Q 3 : t i 0 → i + s, i=2k-1,1≤k≤n. Q 4 : t i + → i 0 t, i=2k-1,1≤k≤n.
After the execution of ruleC5 (if membranes 2n have object cm+1), object t presents in membranes 2n at the same step. At that moment, rule Q1 starts to be used; object t (if it exists) exits membranes 2n. Note that in membranes 2n rule Q1 starts and completes at the same step.
The quantifier∃ is simulated by transferring only one copy of object t to an upper level membrane; that is, in membrane 2k (1≤k≤n-1), there exists at least one copy of object t. Specifically, if membranes 2k (1≤k≤n-1) have object t, rule Q2 starts to be used, object t exits membranes 2k, and the polarization of such membrane is changed from neutral to positive. Note that, in each of the immediately lower level membranes, if there exist two copies of object t in a membrane 2k (1≤k≤n-1), then in membranes 2k two copies of object t appear at the same step. Obviously, there are n-1 levels of membranes 2k (1≤k≤n-1), and rule Q2 starts to be used at different steps for each level of membranes 2k. Hence, the simulation of all quantifiers ∃ takes n-1 RS-steps.
The quantifier∀ is simulated by transferring only one copy of t to an upper level membrane; that is, there are two copies of object t in membrane 2k-1 (1≤k≤n). Specifically, if membranes 2k-1 (1≤k≤n) contain two copies of t, rule Q3 starts to apply, object t evolves to s, and object s exits membrane; the charge of such membrane is changed from neutral to positive. After the execution of rule Q3, rule Q4 starts to be used, object t exits this membrane, and the charge is changed from positive to neutral. Note that if each of the immediately lower level membranes of a membrane 2k-1 (1≤k≤n) has one copy of object t, then two copies of t appear in membranes 2k-1 at the same step. There are n levels of membranes 2k-1 (1≤k≤n), and rules Q3,Q4 start to be used at different steps for each level of the membranes 2k-1; thus, the simulation of all quantifiers ∀ takes 2n RS-steps.
In general, this phase takes3n RS-steps.
Output Phase O 1 : n o 2 n + m + 1 0 → 2 n + m + 1 + n o. O 2 : n o 2 n + m + 1 - → n o 2 n + m + 1 -. O 3 : t 2 n + m + 1 + → 2 n + m + 1 - y e s.
At step 1, objectno is sent out of the system by using rule O1. Note that this operation takes no RS-step. After the quantifier phase, we have the following two cases.
If positive membrane2n+m+1 does not contain object t, in this case, rules O3,O2 cannot be applied. Hence when computation halts, the environment has object no, which means the formula is not satisfiable.
If positive membrane2n+m+1 contains object t, in this case, rule O3 will be applied, object t evolves to yes, which will be sent to the environment, and the polarization of membrane 2n+m+1 is changed from positive to negative. After the execution of rule O3, rule O2 starts to be used; object no enters membrane 2n+m+1. Hence when computation halts, the environment has one copy of yes, which means the formula is satisfiable. The output phase takes two RS-steps.
According to the constructed P systems, for any time-mappinge:R→N, if the computation halts, object yes (resp., no) appears in the environment if and only if the formula φ is satisfiable (resp., not satisfiable). Thus, the system Π is time-free sound and time-free complete.
For any time-mappinge:R→N, the computation takes at most 8n2+17n+3m+3 RS-steps when formula φ is satisfiable, and the computation takes at most 8n2+17n+3m+1 RS-steps when formula φ is not satisfiable. Therefore, the family of P systems with active membrane is time-free polynomially bounded.
The familyΠ={Πφ∣φisaninstanceoftheQSATproblem} is polynomially uniform: (i)
total number of objects:12n+4m+6;(ii)
number of initial membranes:2n+m+1;(iii)
cardinality of the initial multisets:2n+m+1;(iv)
total number of rules:8n2+19n+3m+4;(v)
maximal length of a rule:m+4.
Therefore, P systems with active membranes can solve theQSAT problem in polynomial RS-steps in a time-free manner; this concludes the proof.Figure 1
The membrane structure of the systemΠ at the moment when the generation phase completes.


## 4. Conclusions and Future Work

In this work, a time-free way of using rules is considered into P systems with active membranes, and a time-free solution to theQSAT problem by using P systems with active membranes has been given, where the solution to such problem is correct, which does not depend on the execution time for the used rules.P systems with active membranes presented in this work are semiuniform; that is, the P systems are designed from the instances of the problem. It remains open how we can construct a family of P systems to solve theQSAT problem in a time-free manner in the sense that P systems are designed from the size of instances.The P system constructed in Section3 has the polarization on membranes. It is of interest to investigate whether P systems with active membranes without polarization on membranes can still solve the QSAT problem in a time-free context.QSAT problem is one of the most important issues in many application areas, such as artificial intelligence aspect (e.g., planning, nonmonotonic reasoning, scheduling, model checking, and verification formal verification can be reduced to QSAT [41–45]) and fault localization in digital circuits aspect [46–51]. It is interesting to design new algorithms based on QSAT which can be used in the above-mentioned areas and other areas.



---

*Source: 5793234-2019-06-27.xml*