An efficient time-free solution to QSAT problem using P systems with proteins on membranes

An efficient time-free solution to QSAT problem using Psystems with proteins on membranes Bosheng Song a, Mario J. Pérez-Jiménez c, Linqiang Pan a,b,∗ a Key Laboratory of Image Information Processing and Intelligent Control of Education Ministry of China, School of Automation, Huazhong University of Science and Technology, Wuhan 430074, Hubei, China b School of Electric and Information Engineering, Zhengzhou University of Light Industry, Zhengzhou 450002, China c Research Group on Natural Computing, Department of Computer Science and Artificial Intelligence, University of Sevilla, Avda. Reina Mercedes s/n, 41012 Sevilla, Spain a b s t r a c t Keywords: Bio-inspired computing Membrane computing P system Time-free solution QSAT problem P systems are a class of distributed parallel computing devices inspired by some basic behaviors of biological membranes, which have the restriction that each rule is executed in exactly one time unit. However, it is natural to consider the systems without the time restriction on each rule since biochemical reactions in biological systems are inherently parallel and have different reaction rates, and the execution time of biochemical reactions is unpredictably sensitive to environmental factors. In this work, we construct a family of Psystems with proteins on membranes and membrane division that are “robust” against the execution time of rules. Specifically, we present a time-free uniform solution to the QSAT problem by using Psystems with proteins on membranes and membrane division in the sense that the execution time of the involved rules has no influence on the correctness of the solution. 1. Introduction Membrane computing is a naturally inspired computational paradigm, abstracting computational ideas (e.g., computational models, data structures, data operations) from the structure and the functioning of living cells. The aim of membrane computing is to produce a family of coherent, robust and efficient computational models. This direction of research area was initiated in 1998 and it has developed quickly on both theoretical results [2,37,39,40,42] and application of solving real problems [29,30,43,44]. All classes of computational models considered in the framework of membrane computing are called Psystems, which are parallel and distributed computational models. Three main types of Psystems have been considered until now from the point of biological motivation: cell-like Psystems (inspired by the living cell with its compartments arranged in a hierarchical structure) [26], tissue-like Psystems (inspired by cell inter-communication in tissues and in certain environment) [15], neural-like Psystems (inspired by the way the neurons communicate by means of electrical impulses of identical shape) [12]. One may refer to the handbook of membrane computing for general information [28], and the most up-to-date information for this area, please refer to the Psystems webpage: http :/ /ppage .psystems .eu. In this work, we deal with a class of cell-like P systems: Psystems with objects on membranes. *Corresponding author at: Key Laboratory of Image Information Processing and Intelligent Control of Education Ministry of China, School of Automation, Huazhong University of Science and Technology, Wuhan 430074, Hubei, China. E-mail addresses: [email protected] (B. Song), [email protected] (M.J. Pérez-Jiménez), [email protected] (L. Pan). Psystems with objects (also called proteins) on membranes are motivated by the biological reality that some biochemical reactions taking place in a cell involve proteins bound on membranes such as transportation of substrates and even are regulated by proteins on membranes [1]. Membrane proteins can be divided into two major types with respect to the way they are associated to the lipid bilayer: peripheral proteins, placed on one side of a membrane, internal or external, and integral (also called transmembrane) proteins, which have parts of the molecule on both sides of the membrane (it is estimated that in the animal cells, the proteins constitute about half of the mass of the membranes [1]). In general, there are three main types of Psystems with objects on membranes investigated: (1) (mem)brane systems (inspired by brane calculi), objects evolve together with membranes by operations of pino, exo, phago calculus and mate, drip, bud calculus [4,5,27]; (2) Ruston models, objects placed on membranes control the evolution of objects in the neighboring regions [13,22–25]; (3) Trento models, objects are placed both on membranes and in regions, and they can change their places [3,7–9]. The present work deals with Psystems with proteins on membranes, specifically, Ruston models, which are the models combining membrane systems and brane calculi as introduced in [23]. AP system with proteins on membranes consists of a hierarchical arrangement of membranes, each membrane delimiting a compartment (also called region). A membrane with no compartments inside is called elementary, otherwise it is called non-elementary. The outmost membrane is called a skin membrane, the space outside the skin membrane is called the environment. In such P systems, we have objects both in compartments, as usual in P systems, and on membranes (called proteins), the proteins are fixed to the membranes and used mainly to control the evolution of other objects. The evolution rules used in Psystems with proteins on membranes are inspired from the symport/antiport rules (symport rules move objects across a membrane together in one direction, whereas antiport rules move objects across a membrane in opposite directions) [20], but the objects can evolve under the control of proteins placed on membranes (the proteins can also change). Moreover, Psystems with proteins on membranes always use minimal rules, that is, dealing with only one protein, one object inside the region and/or one object outside of it. The computational power of Psystems with proteins on membranes was investigated in [23], where many universal results of such Psystems are obtained by combining several various types of rules. Aparticular class of Psystems with proteins on membranes, called flip-flop membrane systems with proteins, was also investigated in [13,25], where each protein has at most two states, and flip-flop membrane systems with proteins are proved to be universal by simulating register machines. If membrane division is introduced in Psystems with proteins on membranes, computationally hard problems can be solved in a feasible time by a time–space trade-off. In [24], the SAT problem was solved by a uniform family of Psystems with proteins on membranes and membrane division in polynomial time. Psystems with proteins on membranes were also used to solve PSPACE-complete problems. In [41], an efficient solution to the QSAT problem was given by a family of recognizer Psystems with proteins on membranes in a semi-uniform way, moreover, it was shown that the polynomial complexity class (semi-uniform version) associated with recognizer Psystems with proteins on membranes coincides with the class of PSPACE-complete problems. All the above mentioned Psystems with proteins on membranes work in a synchronized and parallel way, that is, there exists a global clock which marks the time for the whole system, in each time unit, all the rules evolve synchronously and the execution time of each rule takes exactly one time unit (one step). From a biological point of view, amore realistic way is to consider the system without the time restriction on each rule, because the execution time of biochemical reactions is typically exponentially distributed, at least for well-mixed mass-action systems, and it is sensitive to environmental factors that could affect reaction rates in an unpredictable way. With this biological motivation, Psystems that use time as support for the computation are proposed (called timed Psystems), in such P systems, a natural number (represented the execution time of the rule) is associated to each rule [6]. Aparticular class of timed P systems, called time-free Psystems, was also formulated in [6], by simulating non-synchronized P systems, time-free Psystems were proved Turing universal when using bi-stable catalysts and priority. Time-free solutions to computationally hard problems as open problems were formulated in [11]. The first attempt in this topic was done in [34], where a family of Psystems with active membranes was designed for a time-free solution to the SAT problem in the sense that correctness of the solution does not depend on the execution time of the involved rules. Since then, several variants of Psystems were used to solve NP-complete problems in a time-free manner [35,38]. However, it remains open whether PSPACE-complete problems can be solved by Psystems with proteins on membranes in the time-free context. In this work, we design a family of Psystems with proteins on membranes and membrane division, which solves PSPACE-complete problem, the QSAT problem, in a time-free uniform manner in the sense that a Psystem constructed can solve a family of instances with the same size and correctness of the solution does not depend on the execution time of the involved rules. 2. P systems with proteins on membranes and membrane division 2.1. Psystems with proteins on membranes and membrane division The Psystems considered in this work use two types of objects: proteins and simple objects [23]. The proteins are placed on the membranes, which never leave their places during the evolution process (but they can evolve) and are used mainly to control the evolution of other objects; the simple objects are placed in the regions delimited by membranes, which can leave from the regions to the neighboring regions during the evolution. If a protein pis placed on a membrane (with label) iand an object ais placed in the region delimited by that membrane, then it is denoted by [ p |a ]i(note that if a membrane is divided by a division rule, then the new membranes resulting from division have the same label with the divided membrane; that is, duplicate labels are possible; of course, membranes with a same label are subject to the same set of rules). The regions of a membrane structure and the membranes themselves can contain multisets of objects and of proteins, respectively. Psystems with proteins on membranes and membrane division are used for solving decision problems, where an exponential workspace can be generated in polynomial or linear time, and computationally hard problems can be solved by trading off space for time (see [24,41]). Before introducing the definition of Psystems with proteins on membranes and membrane division, we first give some basic notions and notations from formal language theory [33]. An alphabet is a finite and non-empty set of symbols. An ordered finite sequence of symbols form a string or word. Astring over is obtained by juxtaposing symbols of . The empty string is denoted by λ. The set of all strings over an alphabet is denoted by ∗and by +=∗\{λ}we denote the set of non-empty strings. A multiset m over an alphabet is a pair (, f)where f:→Nis a mapping, Nis the set of non-negative integers. If m =(, f)is a multiset then its support is defined as supp(m) ={x ∈| f(x) >0}. If m =(, f)is a finite multiset over , and supp(m) ={a1, ..., ak}, then it will be denoted as m ={af(a1) 1, ..., af(ak) k}. We usually represent mby the string af(a1) 1...af(ak) kor by any permutation of this string. The union and relative complement of two multisets are defined as follows. Let m1=(, f1), m2=(, f2)be multisets over , then the union of m1and m2, denoted by m1+m2, is the multiset (, g), where g(x) =f1(x) +f2(x)for each x ∈. The relative complement of m2in m1, denoted by m1\m2, is the multiset (, g), where g(x) =f1(x) −f2(x)if f1(x) ≥f2(x), and g(x) =0otherwise. Definition 1. A Psystem with proteins on membranes and membrane division of degree m ≥1is a tuple Π=(O, P, μ, w1/z1, ...,wm/zm, E, R1, ..., Rm, iout), where: •Oand Pare finite non-empty alphabets such that O ∩P=∅. •μis a singly-rooted tree with mnodes labeled by 1, ..., m. •wi, 1 ≤i ≤m, are multisets over O. •zi, 1 ≤i ≤m, are multisets over P. •E⊆Ois a finite alphabet. •iout ∈{0, 1, ..., m}is the output region. •Ri, 1 ≤i ≤m, are finite sets of rules of the following types: –Evolution rules of the types: (1)[ p |a ]i→[ p|b ]i, p, p∈P, a, b ∈O, 1 ≤i ≤m; (The rule is applicable when protein pis bounded on membrane iand object aappears in membrane i. The application of the rule means that object aevolves to bunder the control of the protein p, and at the same time the protein pis modified to p. Other proteins on membrane iand other objects in membrane ikeep unchanged.) (2)a [ p |] i→b [ p|] i, p, p∈P, a, b ∈O, 1 ≤i ≤m; (The rule is applicable when protein pis bounded on membrane iand object aappears in the father of membrane i. The application of the rule means that object aevolves to bunder the control of the protein p, and at the same time the protein pis modified to p.) (3)[ p |a ]i→b [ p|] i, p, p∈P, a, b ∈O, 1 ≤i ≤m; (The rule is applicable when protein pis bounded on membrane iand object aappears in membrane i. The application of the rule means that object ais sent out of membrane ievolving to bunder the control of the protein p, and at the same time the protein pis modified to p.) (4)a [ p |] i→[ p|b ]i, p, p∈P, a, b ∈O, 1 ≤i ≤m; (The rule is applicable when protein pis bounded on membrane iand object aappears in the father of membrane i. The application of the rule means that object ais sent into membrane ievolving to bunder the control of the protein p, and at the same time the protein pis modified to p.) (5)a [ p |b ]i→c[ p|d ]i, p, p∈P, a, b, c, d ∈O, 1 ≤i ≤m. (The rule is applicable when protein pis bounded on membrane iand object aappears in the father of membrane iand object bappears in membrane i. The application of the rule means that object ais sent into membrane i evolving to d, object bis sent out of membrane ievolving to c, and at the same time the protein pis modified to p.) –Division rules: (6)[ p |] i→[ p|] i[ p |] i, p, p, p ∈P, 1 ≤i ≤m, i = iout, and icannot be the root of the tree μ. (The rule is applicable when protein pis bounded on membrane i. The application of the rule means that membrane iis divided into two copies of membrane with the same label and the same contents (except for pand p) duplicated from the original membrane: objects, proteins and other possible embedded membranes. Note that membrane ican be non-elementary, that is, membrane imay contain other membranes inside.) The rules of Psystems with proteins on membranes and membrane division are used in a non-deterministic maximally parallel way. There has only one restriction: when a membrane is divided, other membrane cannot be applied at that step. The new membranes resulting from division could participate in the interaction with other membranes or the environment by means of evolution rules at the next step if they are not divided once again. The label of a membrane identifies the rules which can be applied to it precisely. A configuration of a Psystem with proteins on membranes and membrane division is described by the current membrane structure, together with all multisets of objects contained in all membranes, and all multisets of proteins presented on all membranes. The system passes from one configuration to another by a maximally parallel application of rules as described above. Each passage from a configuration to a next configuration is called a transition. A configuration is a halting one if no rule of the system is applicable to it. Acomputation is a (finite or infinite) sequence of transitions starting in the initial configuration. Only a halting computation gives a result, encoded by the multiset of objects present in the output region. 2.2. Recognizer Psystems with proteins on membranes and membrane division In this subsection, in order to investigate the computational efficiency of membrane systems, the notions from classical computational complexity theory are adapted for membrane computing. Recognizer Psystems with proteins on membranes and membrane division are introduced for solving decision problems, which is slightly different from the usual recognizer Psystems proposed in [31]. Definition 2. A recognizer Psystem with proteins on membranes and membrane division of degree m ≥1is a tuple Π= (O, P, , μ, w1/z1, ..., wm/zm, E, R1, ..., Rm, iout, iin)such that: •the tuple (O, P, μ, w1/z1, ..., wm/zm, E, R1, ..., Rm, iout), is a Psystem with proteins on membranes and membrane division of degree msuch that the output zone is the environment (iout =0), and in this case, iout is usually omitted from the tuple; •is an (input) alphabet strictly contained in Osuch that E∩=∅; •the initial multisets w1, ..., wmare over O \; •iin ∈{1, ..., m}is the label of a distinguished (input) membrane; •the working alphabet contains two distinguished elements yes and no; •for each multiset wover the input alphabet , the computation of the system with input wstarts from the configuration of the form (w1/z1, ..., (wiin +w)/ziin , ..., wm/zm, μ), when the system halts, then either object yes or object no (but not both) must appear in the environment. 2.3. Recognizer timed Psystems with proteins on membranes and membrane division In this subsection, we start by giving the definition of timed Psystems with proteins on membranes and membrane division, and then the notion of recognizer timed Psystems with proteins on membranes and membrane division is introduced. Definition 3. A timed Psystem with proteins on membranes and membrane division of degree m ≥1is a pair (Π, e), where Πis a Psystem with proteins on membranes and membrane division of degree m, and eis a time-mapping of Π, that is, eis a mapping from the finite set of rules R1∪···∪ Rminto the set of natural numbers N, where the numbers in Nrepresent the execution time for the rules. We denote by Π(e)the timed Psystem with proteins on membranes and membrane division. A timed Psystem with proteins on membranes and membrane division Π(e)works in the following way: an external clock is assumed, which marks time-units of equal length, starting from instant 0. According to this clock, the step tof computation is defined by the period of time between instant t−1 and instant t. If a membrane icontains a rule r (evolution rule or division rule) selected to be executed, then the execution of such rule takes e(r)time units to complete. Therefore, if the execution of a rule ris started at instant j, then such rule is completed at instant j +e(r)and the resulting objects, proteins and membranes (generated by the division rule) become available only at the beginning of step j +e(r) +1. If an evolution rule is started, then the occurrences of objects and proteins subject to this rule cannot be subject to other rules until the implementation of the rule completes; if the division rule is started, then the occurrences of proteins and membranes subject to this rule cannot be subject to other rules until the implementation of the rule completes. Definition 4. A recognizer timed Psystem with proteins on membranes and membrane division of degree m ≥1is a tuple (Π, e)where Πis a recognizer Psystem with proteins on membranes and membrane division of degree mand eis a time-mapping of Π. 2.4. Time-free uniform solutions to decision problems by Psystems with proteins on membranes and membrane division Psystems with active membranes have been used to solve the SAT problem in a time-free manner, where rule starting steps (RS-steps, for short) are considered as the computation steps [34], and the number of RS-steps is used to characterize how “fast” a timed Psystem with active membranes solves a decision problem. In this work, the notion of rule starting steps is also used in timed Psystems with proteins on membranes and membrane division. Definition 5. In timed Psystems with proteins on membranes and membrane division, a computation step is called an RS-step if at this step at least one rule starts its execution, that is, steps in which some objects and proteins “start” to evolve or membranes “start” to divide. A decision problem, X, is a pair (IX, X) such that IXis a language over a finite alphabet (whose elements are called instances) and Xis a total Boolean function (that is, predicate) over IX. Definition 6. [35] A decision problem X=(IX, X)is solvable in polynomial RS-steps by a family ={Πn|n ∈N}of recognizer Psystems with proteins on membranes and membrane division in a time-free manner, if the following holds: •the family is polynomially uniform by Turing machines; •there exists a pair (cod, s)of polynomial-time computable functions over IXsuch that: –for each instance u ∈IX, s(u)is a natural number and cod(u)is an input multiset of the system Πs(u); –the family is time-free sound, time-free complete and time-free polynomially bounded with respect to (X, cod, s). We also say that the family provides an efficient time-free uniform solution to the decision problem X. 3. An efficient time-free solution to QSAT problem using P systems with proteins on membranes and membrane division The QSAT problem (satisfiability of quantified propositional formulas) is a well-known PSPACE-complete problem [19], it is defined as follows: Given the fully quantified formula ϕ∗associated with a Boolean formula ϕ(x1, ..., xn)in conjunctive normal form, determine whether or not ϕ∗is satisfiable. A formula as above is of the form ϕ∗=Q1x1Q2x2...Qnxn(C1∧C2∧···∧Cm), where each Qj, 1 ≤j ≤n, is either ∀or ∃, and each Ci, 1 ≤i ≤m, is a clause of the form of a disjunction Cj=y1∨y2∨···∨ yr, with each ykbeing either a propositional variable, xs, or its negation, ¬xs. For example, let us consider the propositional formula ϕ∗=Q1x1Q2x2[(x1∨x2)∧(¬x1∨¬x2)]. It is easy to check that formula ϕis true when Q1=∀ and Q2=∃, but it is false when Q1=∃ and Q2=∀. Theorem 3.1. QSAT problem can be solved in polynomial RS-steps by a family of Psystems with proteins on membranes and membrane division with rules of types (a), (c), (d), (e), (f) in a time-free uniform manner, that is, aPsystem constructed can solve a family of instances with the same size and correctness of the solution does not depend on the execution time of the involved rules. Proof. Let a propositional formula ϕ∗=Q1x1Q2x2...Qnxn(C1∧C2∧···∧Cm), Ci=yi,1∨···∨yi,pi, for some m ≥1, pi≥1, where yi,j∈{xk, ¬xk|1 ≤k ≤n}, for each 1 ≤i ≤m, 1 ≤j ≤pi; Qk∈{∀, ∃}, for each 1 ≤k ≤n; ¬xkis the negation of a propositional variable xk, the two connections ∨, ∧are or, and, respectively. Let us consider the polynomial time computable function m, n =((m +n)(m +n +1)/2) +n. It is primitive recursive and bijective from N2onto N. In what follows, we construct a family ={Πt|t∈N}, and give the appropriate input multisets, then each system Πtwill solve all instances of QSAT with nvariables and mclauses, where t=m, n. We use the following notations to encode the propositional formula ϕ∗: cod(ϕ∗) =α1,1...α1,nα2,1...α2,n...αm,1...αm,n, where for 1 ≤i ≤m, 1 ≤j ≤nwe have: αi,j=⎧ ⎪ ⎨ ⎪ ⎩ bi,jif xjappears in Ci; b i,jif ¬xjappears in Ci; b i,jif xjand ¬xjdo not appear in Ci. For each m, n ∈N, we construct the recognizer Psystem with proteins on membranes and membrane division Πm,n=(O,P,,μ,w1/z1,...,w2n+3/z2n+3,∅,R1,...,R2n+3,iin), Fig. 1. The initial membrane structure of the P system. with the following components: O=∪{aj,a(1) j,a(2) j,a(3) j,tj,fj|1≤i≤n} ∪{ di|1≤i≤m}∪{an+1,an+2,c,t,t0,u,yes,no}, P={p+ j,p− j,qj,q j,q j,rm+1,j|1≤j≤n}∪{pk|0≤k≤n+m+1} ∪{ ri,j|1≤i≤m,1≤j≤n}∪{˜ p0,¯ p0,pt,r1,n+1,s,s,s}, μ=[[[[...[[[ ] 2n+1]n[] 2n]n−1[] 2n−1...]2[] n+2]1[] n+1]2n+2]2n+3 (each membrane with label i(1≤i≤n−1)contains a membrane with label i+1 and a membrane with label n+i+1,see Fig. 1), w1=a1,w2n+3=no,wi=λ,2≤i≤2n+2, z1=p1,z2n+1=r1,1,z2n+2=p0,z2n+3=s,zi=p0,2≤i≤n, zn+i=qi,1≤i≤n, iin =2n+1(objectsbi,j,b i,j,b i,jare added into this membrane), and the rules contained in the set R =1≤i≤2n+3Riare defined as follows. We divide the computation process into the following four phases: generation phase (G1,j–G22,j), checking phase (C1–C3), quantifier phase (Q1,1–Q2,j), output phase (O1–O4). We also give explanations about the role of these rules in the computation of solving the QSAT problem. Let ebe an arbitrary time-mapping from Rto N, where the numbers represent the execution time of the rules from R. Generation phase. In generation phase, the system assigns truth-assignment of each variable xj(1 ≤j ≤n) as well as looking for the clauses satisfied by the truth-assignment of this variable xj. Specifically, the computation process of assigning truth-assignment of variable xjas well as looking for the clauses satisfied of this variable is described as follows. The protein pj(1 ≤j≤n) on membrane jcorresponds to variable xi. With the appearance of protein pjon membrane j, a non-elementary membrane with label jis divided into two membranes with the same label, the truth values true (represented by tj) and false (represented by fj) assigned to variable xjare produced in two separate copies of membrane j. The objects tjand fjare sent to membrane n, the clauses which are satisfiable by the corresponding truth-assignment are checked in membranes with label 2n +1. After that, objects a(1) jand a(2) jare produced and sent to membrane j +1, and the protein pj+1is produced on membrane j +1. Hence the system starts to assign truth-assignment of variable xj+1as well as looking for the clauses satisfied by the truth-assignment of variable xj+1. In the initial configuration of the system, there is object a1in membrane 1 and protein p1on membrane 1; protein p0 on membrane 2n +2 and on membranes i(2 ≤i ≤n), protein qion membrane n +i(1 ≤i ≤n); input multiset cod(ϕ)in membrane 2n +1 and protein r1,1on membrane 2n +1, object no in membrane 2n +3 and protein son membrane 2n +3. Rules G1,j–G5,j,kare used to generate 2ncopies of membrane with label n, object ti(resp., fi) is sent into membrane n. G1,j:[pj|]j→[p+ j|]j[p− j|]j,1≤j≤n. G2,j:[p+ j|aj]j→[p+ j|tj]j,1≤j≤n. G3,j:[p− j|aj]j→[p− j|fj]j,1≤j≤n. G4,j,k:tj[p0|] k→[p0|tj]k,1≤j≤n−1,j+1≤k≤n. G5,j,k:fj[p0|] k→[p0|fj]k,1≤j≤n−1,j+1≤k≤n. At step 1, division rule G1,1is applied, under the influence of protein p1, membrane 1 is divided into two copies of membrane 1, with protein p1replaced by p+ 1and p− 1, respectively. For any given time-mapping e, the execution of rule G1,1completes in e(G1,1)steps. Exception for the application of rule G1,1, at step 1, rule O2is also used, where object no is sent out of membrane 2n +3, and changing the protein from sto s. From step 2 to step e(G1,1), there is no rule starting. So, during the execution of rule G1,1(i.e., from step 1 to step e(G1,1)), there is one RS-step. Note that the number of RS-steps during the execution of rule G1,1is independent on the time-mapping e. After the execution of rule G1,1finishes, under the control of proteins p+ 1and p− 1placed on two separate copies of membrane 1, the applications of rules G2,1and G3,1start at the same step, but they may complete at different steps due to the fact that the execution time associated with rules G2,1and G3,1can be different. By applying rule G2,1(resp., G3,1), object a1is evolved to t1(resp., f1). With the object t1(resp., f1) in membrane 1 and the protein p0on membrane 2, rule G4,1,2(resp., G5,1,2) is enabled and used, object t1(resp., f1) is sent into membrane 2. When the execution of rule G4,1,2(resp., G5,1,2) finishes, under the control of protein p0on membrane 3, the application of rule G4,1,3(resp., G5,1,3) starts, object t1(resp., f1) is sent into membrane 3. In this way, under the influence of protein p0on membranes i(2 ≤i ≤n), rules G4,1,k(resp., G5,1,k) (2 ≤k ≤n) are applied one by one, where object t1is transferred into the membrane n. Note that the executions of rules G4,1,2and G5,1,2may start at different steps since rules G2,1and G3,1may complete at different steps; rules G4,1,kand G5,1,k(3 ≤k ≤n) may start at different steps because the executions of rules G4,1,k−1and G5,1,k−1may finish at different steps. Rules G6,i,j–G9,i,jare used to check the clauses which are satisfiable by the corresponding truth-assignment. G6,i,j:{tj[ri,j|bi,j]2n+1→di[ri+1,j|tj]2n+1, tj[ri,j|b i,j]2n+1→c[ri+1,j|tj]2n+1, tj[ri,j|b i,j]2n+1→c[ri+1,j|tj]2n+1|1≤i≤m,1≤j≤n}. G7,i,j:{fj[ri,j|bi,j]2n+1→c[ri+1,j|fj]2n+1, fj[ri,j|b i,j]2n+1→di[ri+1,j|fj]2n+1, fj[ri,j|b i,j]2n+1→c[ri+1,j|fj]2n+1|1≤i≤m,1≤j≤n}. G8,i,j:[ri,j|tj]2n+1→tj[ri,j|] 2n+1,2≤i≤m,1≤j≤n. G9,i,j:[ri,j|fj]2n+1→fj[ri,j|] 2n+1,2≤i≤m,1≤j≤n. When the execution of rule G4,1,n(resp., G5,1,n) completes, and with protein r1,1on membrane 2n +1, one of rules in G6,1,1(resp., G7,1,1) is enabled, which corresponds to checking whether the first clause is satisfied by the truth-assignment true (resp., false) of variable x1. By using one of rules in G6,1,1(resp., G7,1,1), object d1can be generated in membrane n if object b1,1(resp., b 1,1) appears in membrane 2n +1, otherwise, object cpresents in membrane n. Meanwhile, protein r1,1placed on membrane 2n +1is changed to r2,1. If object t1(resp., f1) appears in membrane 2n +1, and with protein r2,1on membrane 2n +1, the application of rule G8,2,1(resp., G9,2,1) starts, object t1(resp., f1) is sent out of membrane 2n +1. After the execution of rule G8,2,1(resp., G9,2,1) completes, under the control of protein r2,1on membrane 2n +1, one of rules in G6,2,1(resp., G7,2,1) is enabled, which corresponds to check whether the second clause is satisfied by the truth-assignment true (resp., false) of variable x1. By applying one of rules in G6,2,1(resp., G7,2,1), object d2can be generated in membrane nif object b2,1(resp., b 2,1) presents in membrane 2n +1, otherwise, object cappears in membrane n; protein r2,1placed on membrane 2n +1is changed to r3,1. With object t1(resp., f1) in membrane 2n +1 and protein r3,1on this membrane, the application of rule G8,3,1(resp., G9,3,1) starts, object t1(resp., f1) is sent out of membrane 2n +1. When the execution of rule G8,3,1(resp., G9,3,1) finishes, and with protein r3,1on membrane 2n +1, one of rules in G6,3,1 (resp., G7,3,1) is enabled, the system starts to check whether the third clause is satisfied by the truth-assignment true (resp., false) of variable x1. In this way, rules G6,i,1(1 ≤i ≤m) and G8,i+1,1(1 ≤i ≤m −1) (resp., G7,i,1(1 ≤i ≤m) and G9,i+1,1 (1 ≤i ≤m −1)) are applied one by one until the protein rm+1,1presents on membranes 2n +1. Rules G6,1,1and G7,1,1may start at different steps since the executions of rules G4,1,nand G5,1,nmay finish at different steps; rules G6,i,1and G7,i,1 (2 ≤i ≤m) may start at different steps since the executions of rules G8,i,1and G9,i,1may finish at different steps. Rules G10,j–G13,j,kare used to send object a(1) j(resp., a(2) j) to membrane j. G10,j:[rm+1,j|tj]2n+1→a(1) j[r1,j+1|] 2n+1,1≤j≤n. G11,j:[rm+1,j|fj]2n+1→a(2) j[r1,j+1|] 2n+1,1≤j≤n. G12,j,k:[p0|a(1) j]k→a(1) j[p0|] k,1≤j≤n−1,j+1≤k≤n. G13,j,k:[p0|a(2) j]k→a(2) j[p0|] k,1≤j≤n−1,j+1≤k≤n. With the appearance of protein rm+1,1on membrane 2n +1, rule G10,1(resp., G11,1) is enabled and used, object t1 (resp., f1) is evolved to a(1) 1(resp., a(2) 1), and a(1) 1(resp., a(2) 1) is sent out of membrane 2n +1, changing the protein from rm+1,1to r1,2. If object a(1) 1(resp., a(2) 1) presents in membrane n, under the control of protein p0on membrane n, the application of rule G12,1,n(resp., G13,1,n) starts, object a(1) 1(resp., a(2) 1) is sent out of membrane n. With object a(1) 1(resp., a(2) 1) in membrane n −1 and protein p0on membrane n −1, rule G12,1,n−1(resp., G13,1,n−1) is enabled and applied, object a(1) 1 (resp., a(2) 1) is sent out of membrane n −1. In this way, rules G12,1,k(resp., G13,1,k) (2 ≤k ≤n) are used one by one, object a(1) 1(resp., a(2) 1) is transferred to the membrane 1. Rules G10,1and G11,1may start at different steps since the executions of rules G6,m,1and G7,m,1may finish at different steps; rules G12,1,nand G13,1,nmay start at different steps since the executions of rules G10,1and G11,1may finish at different steps; the executions of rules G12,1,kand G13,1,k(2 ≤k ≤n −1) may start at different steps since rules G12,1,k+1and G13,1,k+1may finish at different steps. Rules G14,j–G16,jare used to make the system synchronization. G14,j:[p+ j|a(1) j]j→a(1) j[p− j|]j,1≤j≤n. G15,j:[p− j|a(2) j]j→a(2) j[p+ j|]j,1≤j≤n. G16,j:a(2) j[p− j|]j→[p− j|a(3) j]j,1≤j≤n. When the execution of rule G12,1,2(resp., G13,1,2) finishes, with protein p+ 1(resp., p− 1) on membrane 1, the application of rule G14,1(resp., G15,1) starts, object a(1) 1(resp., a(2) 1) is sent out of membrane 1, changing protein from p+ 1(resp., p− 1) to p− 1(resp., p+ 1). The executions of rules G14,1and G15,1may start at different steps due to the fact that rules G12,1,2and G13,1,2may finish at different steps. Rule G16,1is enabled only when object a(2) 1appears in membrane 2n +2 and there is a membrane 1 having protein p− 1on membrane 1, that is, rule G16,1can be used only when the applications of both rules G14,1and G15,1have completed. By using rule G16,1, object a(2) 1evolves to a(3) 1, and object a(3) 1is sent into membrane 1. Note that rule G16,1has a synchronization function because e(G2,1) +2≤k≤ne(G4,1,k) +1≤i≤me(G6,i,1) +2≤i≤me(G8,i,1) + e(G10,1) +2≤k≤ne(G12,1,k) +e(G14,1)may not equal to e(G3,1) +2≤k≤ne(G5,1,k) +1≤i≤me(G7,i,1) +2≤i≤me(G9,i,1) + e(G11,1) +2≤k≤ne(G13,1,k) +e(G15,1). In any case, when the execution of rule G16,1completes, the computation takes at most 4n +4m +1 RS-steps, which is independent on any time-mapping e. Rules G17,j–G22,jare used to generate object aj+1in membrane j +1. G17,j:[p− j|a(3) j]j→a(3) j[p+ j|]j,1≤j≤n. G18,j:a(3) j[qj|] n+j→[q j|aj+1]n+j,1≤j≤n. G19,j:[q j|] n+j→[q j|] n+j[q j|] n+j,1≤j≤n. G20,j:[q j|aj+1]n+j→aj+1[q j|] n+j,1≤j≤n. G21,j:aj+1[p+ j|]j→[p0|aj+1]j,1≤j≤n. G22,j:aj[p0|]j→[pj|aj]j,2≤j≤n. With object a(3) 1in membrane 1 and protein p− 1on membrane 1, rule G17,1is enabled and applied, object a(3) 1is sent out of membrane 1, changing protein from p− 1to p+ 1. When the execution of rule G17,1finishes and with protein q1on membrane n +1, the application of rule G18,1starts, object a(3) 1is evolved to a2, and object a2is sent into membrane n +1, changing protein from q1to q 1. With the appearance of protein q 1on membrane n +1, rule G19,1is enabled and applied, membrane n +1is divided into two copies of membrane n +1, protein q 1is replaced by q 1on each copy of membrane n +1. The function of rule G19,1is used to double the number of object a2. If protein q 1presents on membrane n +1, the application of rule G20,1in all membranes n +1starts at the same time and completes at the same time due to the fact that the execution of rule G20,1in all membranes n +1takes the same time e(G20,1)for a given time-mapping e. By using rule G20,1, object a2is sent out of membrane n +1. When the execution of rule G20,1finishes, with object a2in membrane 2n +2 and protein p+ 1on membrane 1, the application of rule G21,1starts, each object a2is sent into a membrane with label 1, changing protein from p+ 1to p0(there are two copies of object a2in membrane 2n +2 and two membranes 1 with protein p+ 1placed on, and the system works in a maximally parallel manner). With object a2in membrane 1 and protein p0on membrane 2, rule G22,2is enabled and applied, object a2is sent into membrane 2, changing protein from p0to p2. Note that the application of rule G22,2in all membranes 2 starts and completes at the same time due to the fact that the execution of rule G22,2in all membranes 2 takes the same time e(G22,2)for a given time-mapping e. Fig. 2. The membrane structure at the moment when protein p2appears on membrane 2. In general, when protein p2presents on membrane 2 (the object a2appears in membrane 2), the computation takes at most 4n +4m +7 RS-steps (see Fig. 2). With protein p2presents on membrane 2, rule G1,2is enabled, which means that the system starts to assign truthassignment of variable x2, and look for the clauses satisfied by the truth-assignment of variable x2. Note that the application of rule G1,2in all membranes 2 starts at the same time and completes at the same time since the execution of rule G1,2 in all membranes 2 takes the same time e(G1,2)for a given time-mapping e. The executions of rules G2,2and G3,2start at the same step, but they may complete at different steps. Furthermore, the applications of rules G4,2,k, G5,2,k, G12,2,k, G13,2,k (3 ≤k ≤n), G6,i,2(1 ≤i ≤m), G7,i,2(1 ≤i ≤m), G8,i,2(2 ≤i ≤m), G9,i,2(2 ≤i ≤m), G10,2, G11,2, G14,2, G15,2may start and complete at different steps. However, rule G16,2is enabled only when all rules that have started and completed their executions. Similar with the case of variable x1, the processes of assigning truth-assignment of variable x2as well as looking for the clauses satisfied by the truth-assignment of variable x2take at most 4n +4m +3 RS-steps. Comparing with the processes of assigning truth-assignment of variable x1as well as looking for the clauses satisfied by the truth-assignment of variable x1, where the computation takes at most 4n +4m +7 RS-steps, this is because during the computation, objects t1 and f1enter the membranes from membrane 1 to membrane n, and objects a(1) 1and a(2) 1are sent out of membranes from membrane nto membrane 1; however, the processes of assigning truth-assignment of variable x2as well as looking for the clauses satisfied by the truth-assignment of variable x2, objects t2and f2are sent into membranes from membrane 2 to membrane n, and objects a(1) 2and a(2) 2are sent out of membranes from membrane nto membrane 2. Analogously, we can deduce that if we consider the processes of assigning truth-assignment as well as looking for the clauses satisfied by the truth-assignment of variables x1, x2, ..., xnin the worse case, then with the increasing of the system assigns truthassignment as well as looks for the clauses satisfied by the truth-assignment of variable from xito xi+1(1 ≤i ≤n −1), the number of RS-steps decreases by 4. Hence, it is easy to see that the processes of assigning truth-assignment of variable xn as well as looking for the clauses satisfied by the truth-assignment of variable xntake at most 4m +11 RS-steps. Therefore, after at most 2n2+4nm +9nRS-steps, 2nseparate copies of membrane with label nare generated, each membrane with label ncontains a membrane with label 2n +1. Moreover, membrane 2n +2 contains two copies of membrane with label n +1 and each membrane with label j(1 ≤j ≤n −1) contains two copies of membrane with label n +j +1 (these membranes with labels n +j(1 ≤j ≤n) are idle in the subsequent phases, thus, we do not show them in Fig. 3). All the membranes are placed in the membrane with label 2n +3(see Fig. 3 for the main membrane structure at the moment when the generation phase completes). Checking phase. When the generation phase completes, each membrane with label ncontains some of the objects from the set {d1, d2, ..., dm}whose elements denote the corresponding clauses satisfied by the truth assignment of the variables. If there is at least one membrane with label nthat contains all the objects d1, d2, ..., dm, which means the formula ϕwithout quantifiers is satisfied by the corresponding truth assignment in that membrane; if there are no membranes with label n that contain all the objects d1, d2, ..., dm, the formula ϕwithout quantifiers is not satisfied. C1:[p0|an+1]n→[pn+1|an+2]n. C2,i:[pn+i|di]n→di[pn+i+1|] n,1≤i≤m. C3:[pn+m+1|an+2]n→[ ˜ p0|t]n. When the execution of rule G20,ncompletes, with protein p+ non membrane n, all objects an+1in each membrane n −1 are sent into membrane n, changing protein from p+ nto p0at the same step (there are two copies of object an+1and two